Codeforces #104とかリフレクプラスとか

今日は16時にcodeforcesがありましたので参加しました。

A問題
4と7だけ含むチケットをラッキーとする。
前半の半分の数値と後半の半分の数値の合計が一致する条件を付け加えて、
そのチケットがラッキーかどうかを判別しろという問題。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
input.nextLine();
String s = input.nextLine();
System.out.println(lucky(n,s));
}

public static String lucky(int n,String s){
for(int i = 0 ; i < s.length(); i++){
if(!(s.charAt(i) == '4' || s.charAt(i) == '7'))return "NO";
}
String front = s.substring(0,n/2+1);
String last = s.substring(n/2,s.length());
int fsum = 0;
int lsum = 0;
for(int i = 0 ; i < n/2 ; i++){
fsum += Character.digit(front.charAt(i),10);
lsum += Character.digit(last.charAt(i),10);
}
if(fsum == lsum)return "YES";
return "NO";
}
}

B問題
ある数aとラッキーナンバーbが与えられている。
マスクという法則があり、3403790などの数字から4と7だけとってきたものである。(例は47)
a以上の数値でマスクしてbというラッキーナンバーになる最小の値を求めるプログラムを作る。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
System.out.println(lucky(a,b));
}

public static int lucky(int a,int b){
a+=1;
while(true){
StringBuilder sb = new StringBuilder();
String s = String.valueOf(a);
for(int i = 0 ; i < s.length() ; i++){
if(s.charAt(i) =='4' || s.charAt(i) == '7'){
sb.append(s.charAt(i));
}
}
if(sb.length() != 0 && Integer.parseInt(sb.toString()) == b)return a;
a++;
}
}
}

C問題
ラッキーナンバーaとbが与えられている。
aに操作を加えbにする。
aにできる操作は、4を7にしたり7を4にしたり、aのある桁とある桁の数をチェンジするといったことである。
これらの操作を加えてbにするときの最少の回数を求める。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
String a = input.nextLine();
String b = input.nextLine();
System.out.println(lucky(a,b));
}

public static int lucky(String a,String b){
int a4sum = 0;
int a7sum = 0;
int b4sum = 0;
int b7sum = 0;
int f47 = 0;
int f74 = 0;
for(int i = 0 ; i < a.length() ; i++){
if(a.charAt(i) == '4'){
a4sum++;
}else{
a7sum++;
}
if(b.charAt(i) == '4'){
b4sum++;
}else{
b7sum++;
}
if(a.charAt(i) == '4' && b.charAt(i) == '7'){
f47++;
}
if(a.charAt(i) == '7' && b.charAt(i) == '4'){
f74++;
}
}
int gosa = Math.abs(a4sum-b4sum);
return Math.min(f47, f74)+gosa;
}
}

D問題(時間内は失敗し、その後提出)

4の数、7の数、47の数、74の数が与えられている。
これらを満たす最少のラッキーナンバーを求めよ。存在しない場合は-1を返せ。

条件分岐の問題です。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
int c = input.nextInt();
int d = input.nextInt();
System.out.println(lucky(a,b,c,d));
}

public static String lucky(int a,int b,int c,int d){
if(c == d){
if(Math.min(a, b) >= (c+1)){//ok
StringBuilder s = new StringBuilder();
int r47 = c-1;
int pkt4 = a-2-r47;
int pkt7 = b-2-r47+1;
for(int i = 0 ; i < pkt4 ; i++){
s.append(4);
}
for(int i = 0 ; i < r47 ; i++){
s.append(47);
}
s.append(47);
for(int i = 0 ; i < pkt7 ; i++){
s.append(7);
}
s.append(4);
return s.toString();

}else if(Math.min(a, b) == c){
if(a == b)return "-1";
StringBuilder s = new StringBuilder();
if(a == c){
s.append(7);
for(int i = 0 ; i < c ; i++){
s.append(47);
}
int res7 = b-c-1;
for(int i = 0 ; i < res7 ; i++){
s.append(7);
}
return s.toString();
}else if(b == c){
int res4 = a-c-1;
for(int i = 0 ; i < res4 ; i++){
s.append(4);
}
for(int i = 0 ; i < c ; i++){
s.append(47);
}
s.append(4);
return s.toString();
}
return "-1";
}else{
return "-1";
}
}

if((a+b) <= (c+d) || Math.abs(c-d) >= 2 || Math.min(a, b) < Math.max(c, d)){
return "-1";
}else{
if(c > d){
int pkt4 = a-c;
int pkt7 = b-c;
StringBuilder s = new StringBuilder();
for(int i = 0 ; i < pkt4 ; i++){
s.append(4);
}
for(int i = 0 ; i < c ; i++){
s.append(47);
}
for(int i = 0 ; i < pkt7 ; i++){
s.append(7);
}
return s.toString();
}else{
int pkt4 = a-d;
int pkt7 = b-d;
StringBuilder s = new StringBuilder();
for(int i = 0 ; i < d ; i++){
if(i != d-1){
s.append(74);
if(i == 0){
for(int j = 0 ; j < pkt4 ; j++){
s.append(4);
}
}
}else{
s.append(7);
for(int j = 0 ; j < pkt7 ; j++){
s.append(7);
}
s.append(4);
}
}
return s.toString();
}
}
}
}

3問解けたので、レーティングは上昇しました。

後はリフレクを少々。
f0019846_1771643.png

  by ddrer-yossi | 2012-01-22 16:57 | codeforces | Comments(0)

<< アルゴリズムの勉強 Facebook Hacker... >>

SEM SKIN - DESIGN by SEM EXE