SRM 371 DIV1 Easy - SpiralRoute

問題


http://community.topcoder.com/stat?c=problem_statement&pm=8262&rd=10787

解き方


最大ケースの時は5000*5000なのでメモリが足りない。
そのため、なにかしら工夫する必要がある。

今回width,lengthともに3以上のときはwidth-2,lengh-2かつスタート位置(r,c)を(r+1,c+1)に
したものと等しくなる。

最後にwidth<=2もしくはlength<=2となるのでこれは簡単な場合分けで解ける。

コード


class SpiralRoute {

public: vector<int> thronePosition(int width, int length) {
int r=0,c=0;
while(width>=3 && length>=3){
width-=2,length-=2;
r++,c++;
}

if(length==1)r+=width-1;
else if(length==2)c++;
else if(width==1)c+=length-1;
else c++;

vector<int> ans(2);
ans[0]=r,ans[1]=c;

return ans;
}

};

Share this

Related Posts

Previous
Next Post »