問題
http://community.topcoder.com/stat?c=problem_statement&pm=10968&rd=15186
ボードの長さと高さが与えられる。
このとき、ナイトが動けるマスを返す。
解き方
１辺の最大の長さは４５０００のため、Ｏ（１０＾８）となり全探索では求められない。
そこで法則を探すことにする。
１）マスの１辺が１のとき
動くことができないので、答えは１
２）マスの１辺が２のとき
もう一つの辺の長さによって答えが変わる。
１マスのときは＋１、２マスの時は＋１、３マスのときは＋２、４マスのときは＋２
これが繰り返される。
３）マスが３*３のとき
３＊３のときは真ん中だけいけないので８．
４）それ以外
全てのマスに行くことができるので全てのマスの数が答え。
コード
class KnightCircuit2 {
public: int maxSize(int w, int h) {
if(w>h)swap(w,h);
if(w==1)return 1;
if(w==2)return (h+1)/2;
if(w==3 && h==3)return 8;
return w*h;
}
};
public: int maxSize(int w, int h) {
if(w>h)swap(w,h);
if(w==1)return 1;
if(w==2)return (h+1)/2;
if(w==3 && h==3)return 8;
return w*h;
}
};
Share this
Related Posts
SRM 677 DIV1 Easy - DoubleOrOneEasy
問題
https://community.topcoder.com/stat?c=problem_statement&pm=14101&rd=16627
解き方
２倍と１足す動作を単純に全通り試そうとする- SRM 604 DIV1 Easy - PowerOfThree
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12917&rd=15837
ロボットが座標（０，０）からスタートし、４方向に移動する。
- SRM 387 DIV1 Easy - FoxesOfTheRoundTable
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8527&rd=11121
解き方
全てのjoker boxの選び方について全探索
- SRM 385 DIV1 Easy - UnderscoreJustification
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8482&rd=10810
解き方
各スペースに挿入するアンダースコアの数の差は最