Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-02SRM390 (Practice)

SRM 390 ConcatenateNumber

|  SRM 390 ConcatenateNumber - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 390 ConcatenateNumber - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8589

  • わぁい数論ゲー あかり数論ゲー大好き
  • 方針を検討
    • 同じ数を繋げるということは、10^桁数 * (元の数) を足すということだ
      • 愚直にシミュレーションし、0にならず同じ状態にたどり着いたら -1
      • 0になったらその数を返せばいい
    • kは最大でも100,000だから、シミュレーション回数も高々100,000のはず
      • 自信はないが、なんとなくそんな気がする
  • 実装
    • 特に問題なくサクサク
  • サンプル通った。
  • 追加ケーステスト。
  • 大丈夫だろう。提出

import java.util.HashSet;
import java.util.Set;

public class ConcatenateNumber {

	public int getSmallest(int number, int k) {
		int keta = 0;
		int nn = number;
		while (nn >= 1) {
			keta++;
			nn /= 10;
		}
		
		long current = number % k;
		long base = (long)Math.pow(10, keta);
		long now = (base % k);
		int cnt = 1;
		boolean[] done = new boolean[1000000];
		while (current % k != 0) {
			if (done[(int)(current % k)]) {
				cnt = -1;
				break;
			}
			done[(int)(current % k)] = true;
			current += (now * number) % k; 
			now = (now * base) % k;
			cnt++;
		}
		return cnt;
	}
}