POJ 1906 - Three powers

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

概要

3のべき乗からなる集合 S

S = {1, 3, 9, 27, 81, ... }

を考える．

S の部分集合 S' を「S' の要素の和」に関してソートしたとき，n 番目の S' を答える．

ただし，空集合の要素の和は 0 とする．

制約

解法

n を二進数とみて，ビットが立っているところの3のべき乗からなる集合が答え．

サンプルからもわかるように 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     BigInteger n;
 8     while (!(n = cin.nextBigInteger()).equals(BigInteger.ZERO)) {
 9       char[] cs = (n.subtract(BigInteger.ONE)).toString(2).toCharArray();
10       System.out.print("{ ");
11       BigInteger e = BigInteger.ONE;
12       boolean first = true;
13       for (int i = 0; i < cs.length; i++) {
14         if (cs[cs.length-i-1] == '1') {
15           if (!first) {
16             System.out.print(", ");
17           }
18           System.out.print(e);
19           first = false;
20         }
21         e = e.multiply(BigInteger.valueOf(3));
22       }
23       if (!first) {
24         System.out.print(" ");
25       }
26       System.out.println("}");
27     }
28   }
29 }
poj/1906.java