7th Contest of Newbies D, UVa-12400 : 3, 2, 1, 0
問題概要
3とかかれたカードがN枚、2とかかれたカードがM枚ある。これらからK枚選んで一列に並べて数を作る。その際に、出来上がった数は2進数表記で末尾に0がK以上ないといけない。そのような数のうち、最小のものを求める問題。ない場合はその旨出力する。
解法
10^k=2^k*5^kなのと2,3の偶奇が異なることから、下の位から一意に定めることができる(最小は関係ない)。多倍長があれば割とやるだけ。JavaのBigIntegerって実装は10進ベースなんだろうか(shift演算やビット演算って効率いいのか?)
acceptされたコード
import java.math.BigInteger; import java.util.*; public class Main { void run(){ Scanner in = new Scanner(System.in); for(;in.hasNextInt();){ solve(in.nextInt(), in.nextInt(), in.nextInt()); } } void solve(int N, int M, int K){ if(K==0){ System.out.println("Impossible."); return ; } if(K > M + N){ System.out.println("Impossible."); return ; } BigInteger MOD = BigInteger.ONE; for(int i=0; i<K; i++){ MOD = MOD.multiply(BigInteger.valueOf(2)); } BigInteger MASK = MOD.subtract(BigInteger.ONE); char cs[] = new char[K]; int p = K; BigInteger base = BigInteger.valueOf(1); BigInteger cur = BigInteger.ZERO; for(int i=0; i<K; i++){ if(cur.and(BigInteger.ONE.shiftLeft(i)).equals(BigInteger.ZERO)){ cs[--p] = '2'; if(--M < 0){ System.out.println("Impossible."); return ; } cur = cur.add(base.multiply(BigInteger.valueOf(2))); if(cur.compareTo(MOD) > 0){ cur = cur.and(MASK); } } else{ cs[--p] = '3'; if(--N < 0){ System.out.println("Impossible."); return ; } cur = cur.add(base.multiply(BigInteger.valueOf(3))); if(cur.compareTo(MOD) > 0){ cur = cur.and(MASK); } } base = base.multiply(BigInteger.valueOf(10)); } System.out.println(String.valueOf(cs)); } public static void main(String[] args) { new Main().run(); } }