問題
http://community.topcoder.com/stat?c=problem_statement&pm=11607&rd=14549
n個のダイヤモンドを運びたい。
1度に最大n個運ぶことができるが、nが素数だった場合消滅してしまう。
このとき、消滅せずに全てのダイヤを運べる最小の回数を求める。
解き方
nが最大10^12のためDFS等では解くことができない。
そこで法則がないかシミュレーションしてみる。
すると、n=3(3回)のときを除いて、以下がわかる。
①素数でない場合は、1回で運べる
②素数の場合は、「素数ー1」個&「1」個の2回で運べる
あとは素数判定関数を作って実装するだけでよい。
コード
class MagicDiamonds {
public:
bool isprimary(long long x){
if(x==2)return true;
if(x==1||x%2==0)return false;
for(long long i=3;i*i<=x;i+=2)if(x%i==0)return false;
return true;
}
long long minimalTransfer(long long n) {
if(n==3)return 3;
return isprimary(n) ? 2 : 1;
}
};