2013年4月30日

UVa 10669 - Three powers


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

public class Main {

  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    BigInteger n;
    while (cin.hasNext()) {
      n = cin.nextBigInteger();
      if (n.compareTo(BigInteger.ZERO) == 0) break;
      n = n.subtract(BigInteger.ONE);
      Vector<BigInteger> ans = new Vector<BigInteger>();
      while (n.compareTo(BigInteger.ZERO) != 0) {
        BigInteger two = BigInteger.ONE, three = BigInteger.ONE;
        while (two.compareTo(n) < 0) {
          two = two.shiftLeft(1);
          three = three.multiply(BigInteger.valueOf(3));
        }
        if (two.compareTo(n) != 0) {
          two = two.shiftRight(1);
          three = three.divide(BigInteger.valueOf(3));
        }
        n = n.subtract(two);
        ans.add(three);
      }
      System.out.print("{");
      for (int i = ans.size() - 1; i >= 0; i--)
        System.out.print(" " + ans.elementAt(i) + (i == 0 ? "" : ","));
      System.out.println(" }");
    }
  }
    
}

沒有留言:

張貼留言