2010年6月6日日曜日

TopCoder SRM 472

SRM472(6/6 3:00~5:00)
久しぶりの参戦.

・PotatoGame(DIV1 Easy)
N個のポテトが積んである.太郎と花子は,交互にポテトをとっていく.ポテトをとる個数は,4のべき乗(1,4,16,64,…)になっている.ポテトを取れなくなった方が負け.お互いが最善を尽くした場合,どちらが勝つか.

しばらく考える.
→解法が思いつかないので,適当に再帰解法もどきを作る
→でも,これだとスタックオーバーフローになるので断念
→実は,単純な規則があるかも?と思って,↑のコードでN=100までの出力見てみる
→周期5のパターンになってる事が判明
→mod 5をとり場合分けして提出

import java.util.*;
import java.lang.*;
import java.math.*;
public class PotatoGame {
public String theWinner(int n) {
int a=n%5;
if(a==1||a==3||a==4)
return "Taro";
else
return "Hanako";
}
}

// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
Result:Passed System Test(100.48p)

・TwoSidedCards(DIV1 Normal)
\(^o^)/
Result:Opend(0p)

・ColorfulTiles(DIV1 Hard)
\(^o^)/
Result:Unopened(0p)

・Challenges
あるコードを見て,間違っているなとは思ったんですが,撃墜できる入力を与えられず失敗.
-25p

・Score
75.48p

・Rating
1226->1276
意外にもレーティング上昇.それだけに,Easyをもっと早く解ければ…と思いました.

0 件のコメント: