tookunn’s diary

主に競技プログラミング関係

Codeforces #333 Div2 A

問題

codeforces.com

bx進数で表された値Xby進数で表された値Yが与えられるので、
値としてXYは等しいか等しくないかを求める。等しくない場合はXYがどちらが大きいか小さいかを求める。
XYが等しい場合は "="
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という式で成り立つと思います。


今回のソースコードではXYを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();
	}
}