Codeforces #333 Div2 A
問題
bx進数で表された値Xとby進数で表された値Yが与えられるので、
値としてXとYは等しいか等しくないかを求める。等しくない場合はXとYがどちらが大きいか小さいかを求める。
XとYが等しい場合は "="
Xの方が大きい場合は ">"
Yの方が大きい場合は "<" を出力する。
解法
この問題の場合は2進数や8進数などから10進数などを求める方法を知っていれば、それを単純に実装することで解けると思います。
例えば、
2進数から10進数に変換する場合は
1 0 1 0 という2進数が渡されるとすると
1 × 2^3 + 0 × 2^2 + 1 × 2^1 + 0 × 2^0 という式になり、10進数では 10という結果になります。
そして、同じように
3進数から10進数に変換する場合は
1 0 1 0 という3進数が渡されるとすると
1 × 3^3 + 0 × 3^2 + 1 × 3^1 + 0 × 3^0 という式になり、10進数では 30という結果になります。
つまり、
| X |をXの値の桁数だとすると、10進数への変換は
X[0] × bx^( | X | - 1 ) + X[1] × bx^( | X | - 2 ) + ... + X[ | X | - 1] × bx^0という式で成り立つと思います。
今回のソースコードではXとYを10進数に変換して比較しています。
注意
10進数に変換する過程ではint型では収まらないので、long型などを使いましょう。
ソースコード
import java.util.Scanner; public class A { public long convert(int[] v,int base) { long ret = 0; for(int i = 0;i < v.length;i++) { long sum = v[i]; if(sum == 0)continue; int j = v.length - 1 - i; if(j == 0) { sum = 1; ret += v[i] * sum; continue; } while(j > 0) { sum *= base; j--; } ret += sum; } return ret; } public void solve() { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int bx = cin.nextInt(); int[] x = new int[n]; for(int i = 0;i < n;i++) { x[i] = cin.nextInt(); } int m = cin.nextInt(); int by = cin.nextInt(); int[] y = new int[m]; for(int i = 0;i < m;i++) { y[i] = cin.nextInt(); } long a = convert(x,bx); long b = convert(y,by); if(a == b) { System.out.println("="); }else if(a < b) { System.out.println("<"); }else { System.out.println(">"); } } public static void main(String[] args) { new A().solve(); } }