SRM-427 600pt: LocateTreasure

TopCoder

keyword

シミュレーション　C++

問題概要

(0,0)の地点に北を向いた人がいる。C=1とする。その人はK(<10^9)回次の様な動きをする。

  • 向きにしたがってCだけ歩き、右を向く。
  • C = digitRoot(C*multi)とする。

最終的な座標を求める問題。

解法

状態は向きとCで考えても9*4通りしかないのでループが出てくる。その間は適当にスキップする。

感想

これで600？それはともかく、実装の遅さが本格的に痛い。

bool visited[20];
int64 py[20];
int64 px[20];
int dist[20];
int next[20];
char ans[100];

string location(int K, int multi) {
    int start=-1, cur=1, dd=0;
    int64 gx=0, gy=0;
    visited[1] = true;
    dist[1] = dd++;
    py[1] = gy;
    px[1] = gx;
    while(1){
        int tmp = cur;
        gy += cur; cur = (cur*multi+8)%9+1;
        if(!(--K)) break;
        gx += cur; cur = (cur*multi+8)%9+1;
        if(!(--K)) break;
        gy -= cur; cur = (cur*multi+8)%9+1;
        if(!(--K)) break;
        gx -= cur; cur = (cur*multi+8)%9+1;
        if(!(--K)) break;
        if(visited[cur]){
            int period = 4*(dd - dist[cur]);
            gy += (gy - py[cur])*(K/period);
            gx += (gx - px[cur])*(K/period);
            K %= period;
            if(!K) break;
        }
        else{
            visited[cur] = true;
            py[cur] = gy;
            px[cur] = gx;
            dist[cur] = dd++;
        }
    }

    sprintf(ans, "%lld %lld", gx, gy);
    return string(ans);
}