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();
	}

}