POJ 1023 - The Fun Number System

http://poj.org/problem?id=1023

概要

k ビットの値で整数を表すことを考える． i ビット目は negabit か posbit のいずれかであり， i ビット目が立っている場合，negabit のときは -2^i ，posbit のときは +2^i を意味する．

例えば k = 3 で，0, 2 ビット目が posbit，1 ビット目が negabit だとすると， 110 は 2^2 - 2^1 = 3 という整数を表している．

与えられた posbit, negabit の情報に基き，十進数で与えられる整数 N に対応するビット列を答える． ただし，N を表現できないときは「Impossible」と答える．

例えば N = -1 のときの答えは 011 (- 2^1 + 2^0 = -1) だが，N = 6 のときの答えは「Impossible」である．

制約

解法

N の正負に関係無く，i ビット目に影響を与えられるのは j (<= i) ビット目だけなので，下位ビットから順に決めていけばいい．

N の i ビット目が立っているときは答えの i ビット目も立っている必要がある． もし i ビット目が posbit のときはそれだけで良いが，negabit のときは N に 2 * 2^i を足すことで帳尻を合わせる．

posbit がすべて立っているような数を H とし，negabit がすべて立っているような数を L とすると， L <= N <= H なる N に限りこのシステムで表すことができる． 逆に N がこの範囲に入っていなければ「Impossible」である．

k <= 64 なので気をつければ long long でできそうだけど，結局うまく実装できなかったので Java の BigInteger に逃げた…

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main {
 5   public static void main(String[] args) {
 6     Scanner cin = new Scanner(System.in);
 7     int T = cin.nextInt();
 8     BigInteger two = BigInteger.valueOf(2);
 9     while (T-- > 0) {
10       int K = cin.nextInt();
11       char[] pn = cin.next().toCharArray();
12       BigInteger N = cin.nextBigInteger();
13       BigInteger lo = BigInteger.ZERO, hi = BigInteger.ZERO;
14       for (int i = 0; i < K; i++) {
15         lo = lo.multiply(two);
16         hi = hi.multiply(two);
17         if (pn[i] == 'n') {
18           lo = lo.subtract(BigInteger.ONE);
19         } else {
20           hi = hi.add(BigInteger.ONE);
21         }
22       }
23       if (N.compareTo(lo) < 0 || hi.compareTo(N) < 0) {
24         System.out.println("Impossible");
25       } else {
26         char[] ans = new char[K];
27         for (int i = 0; i < K; i++) {
28           if (N.testBit(i)) {
29             ans[K-i-1] = '1';
30             if (pn[K-i-1] == 'n') {
31               N = N.add(BigInteger.ONE.shiftLeft(i+1));
32             }
33           } else {
34             ans[K-i-1] = '0';
35           }
36         }
37         System.out.println(ans);
38       }
39     }
40   }
41 }
poj/1023.java