SRM 524 DIV1 Easy - MagicDiamonds (復習×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11607&rd=14549
ｎ個のダイヤモンドを運びたい。
１度に最大ｎ個運ぶことができるが、ｎが素数だった場合消滅してしまう。
このとき、消滅せずに全てのダイヤを運べる最小の回数を求める。
解き方
ｎが最大１０＾１２のためＤＦＳ等では解くことができない。
そこで法則がないかシミュレーションしてみる。
すると、ｎ＝３（３回）のときを除いて、以下がわかる。
①素数でない場合は、１回で運べる
②素数の場合は、「素数ー１」個＆「１」個の２回で運べる
あとは素数判定関数を作って実装するだけでよい。
コード
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;
}
};
