SRM570 Div1 Easy - RobotHerb
問題
無限に広いグリッド上にロボットがいる
長さnのプログラムが組み込まれており、i番目は「正面にa[i]マス進んでからa[i]*90度右に回れ」という内容
このプログラムをt回実行した後に辿り着くマスと最初にいたマスのマンハッタン距離を求めよ
1 <= n <= 50
1 <= a[i] <= 10^7
1 <= t <= 10^9
解法
プログラム実行時の向きによってプログラム実行による座標の変化が変わってくるから、単純にプログラムを1回実行したときの座標変化をt倍するだけではダメ
最初の向きを上方向だとする
プログラムを1回実行し終わった時点での向きが上方向なら1回、下なら2回、左右なら4回、それぞれプログラムを実行すると向きが元に戻る
つまり4回プログラムを実行すれば必ず元の向きに戻る
よってプログラムを4回セットにしたものをfloor(t/4)回実行して、残りt%4回は普通にシミュレーションすればok
class RobotHerb { public: ll getdist(int t, vector<int> a) { ll x = 0, y = 0, dir = 0; rep(k,4) each(i,a){ x += dx[dir]*i, y += dy[dir]*i; (dir += i) %= 4; } x *= t/4, y *= t/4; rep(k,t%4) each(i,a) { x += dx[dir]*i, y += dy[dir]*i; (dir += i) %= 4; } return abs(x) + abs(y); } };
https://community.topcoder.com/stat?c=problem_statement&pm=12427&rd=15490