kmjp's blog

競技プログラミング参加記です

TopCoder SRM 529 Div2 Hard MinskyMysteryDiv2

うーん、あまり面白くない問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11746

問題

0~4番の5個の袋があり、初期状態で0番にN個の石が入っており、他は空である。
また、別に沢山の石がある。
ここで以下のアルゴリズムを実行する。

1番の袋に石を1個加える。
以下無限ループする
  1番の袋に石を1個加える。
  4番の袋を空にする
  0番の袋に石がある間、以下を行う
     0番と1番に袋がある間、以下を行う
       0番と1番から石を1個ずつ取り除き、2番と3番に1個ずつ加える
     4番に石を1個加える。  
     0番と1番がともに空なら、3番の石を4番に移して終了
     3番の石を1番に戻す
   2番の石を0番に戻す

終了時に得られる4番の袋の石の中身を答えよ。

解法

少ない石の数でシミュレーションすると、各袋は以下の意図があることがわかる。
0番:処理対象であるN
1番:1から1ずつインクリメントし、0番を割り切れるまで繰り返す
2番と3番:0番と1番の処理中に取り除いた石を一時保存しておく場所。後で戻す。
4番:0番÷1番を保持。

厳密には、Nに対する2以上の最小の約数aに対し、N/a+aが答えとなる。

class MinskyMysteryDiv2 {
	public:
	long long computeAnswer(long long N) {
		if(N<=1) return -1;
		for(ll a=2;a*a<=N;a++) if((N%a)==0) return N/a+a;
		return N+1;
	}
};

まとめ

何がしたい問題だったんだろう…。

広告を非表示にする