問題
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;
}
};
Share this
Related Posts
SRM 385 DIV1 Easy - UnderscoreJustification
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8482&rd=10810
解き方
各スペースに挿入するアンダースコアの数の差は最- SRM 460 DIV1 Easy - TheQuestionsAndAnswersDivOne
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10768&rd=14146
解き方
数が小さいので全探索可能。
すでに答えた人の
- SRM 436 DIV1 Easy - BestView
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10341&rd=13698
間隔１で一列に高層ビルが並んでいる。
高層ビルの上から他のビ
- SRM 188 DIV1 Easy - Percents
問題
http://community.topcoder.com/stat?c=problem_statement&pm=2386&rd=4760
あるアンケートに対して、yesと答えた人の割合が％で与えられる。