POJ 1894 - Alternative Scale of Notation

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

概要

普通，B 進数で表示された n 桁の数字 α は 0, 1, ..., B-1 の B 種類の数字から成り，

U_B(α) = Σα[n-i]*B^i

という数値を表している． 例えば U_3(1001) = 1*27 + 0*9 + 0*3 + 1*1 = 28．

しかし，この写像は例えば 28 = U_3(1001) = U_3(01001) = U_3(001001) = ... であるので全単射ではない．

そこで，別の表示方法として 1, 2, ..., B の B 種類の数字で表現する方法を考える．

V_B(α) = Σα[n-i]*B^i

ただし，空文字列 ε に対して V_B(ε) = 0 と定義する． この写像は全単射であるため，逆写像が存在する．

基数 B と十進法で表示された非負整数 x が与えられるので，V_B(α) = x となるような α を答える．

制約

• 2 <= B <= 9
• 0 <= x <= 10^100

解法

x を普通の意味の B 進数に変換し，下の位から見ていって 0 になっている位を見つけたら， そのひとつ上の位の数字を1減らし，その位を B にすることで求められる．

 1 import java.util.*;
 2 import java.io.*;
 3 import java.math.*;
 4 
 5 public class Main {
 6   public static void main(String[] args) {
 7     Scanner cin = new Scanner(System.in);
 8     int B = cin.nextInt();
 9     BigInteger x = cin.nextBigInteger();
10     char[] ans = x.toString(B).toCharArray();
11     int len = ans.length;
12     for (int i = len-1; i > 0; i--) {
13       if (ans[i] <= '0') {
14         --ans[i-1];
15         ans[i] = (char)(ans[i]+B);
16       }
17     }
18     String r = new String(ans);
19     System.out.println(r.replaceFirst("^0", ""));
20   }
21 }