2015-08-24

2016 Google APAC Test 小結

1. A. Googol String
2. B. gCube
3. C. gCampus
4. D. gSnake

不知道有這場比賽，無聊寫寫靜靜心。

A. Googol String

給定一個遞迴生成式，求 $S_{100}$ 的第 $n$ 位字符為何。

直接用遞迴返回去計算即可，狀態分別為 f(n, S_m, switch_flag)，如果超過 $S_{m-1}$ 的一半時，由於操作需要字串反轉，反向求位數和反轉操作即可。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 128;
unsigned long long b2[MAXN];
int f(long long n, int m, int s) {
    if (m == 1)	return s;
    if (n <= b2[m-1])
        return f(n, m-1, s);
    if (n == b2[m-1]+1)
        return s;
    return f(b2[m-1]-(n-b2[m-1]-1)+1, m-1, !s);
}
int main() {
    b2[0] = 0;
    for (int i = 1; i < MAXN; i++)
        b2[i] = (b2[i-1]<<1)+1;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        printf("Case #%d: ", ++cases);
        for (int i = 0; i < MAXN; i++) {
            if (b2[i] >= n) {
                printf("%d\n", f(n, i, 0));
                break;
            }
        }
    }
    return 0;
}

B. gCube

有一個 ? 維空間，要抓數列區間 [L, R]內的數字，構成 R-L+1 的超長方體，請問等體積下的超正方體的邊長為何。

簡單地說要把區間內的數字相乘起來，並且開 n 次根，由於乘數結果會 overflow，套用 log() 來完成。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 128;
unsigned long long b2[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, A[1024], x, y;
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            double sum = 0;
            for (int j = x; j <= y; j++)
                sum += log(A[j]);
            sum /= (y - x + 1);
            printf("%.9lf\n", exp(sum));
        }
    }
    return 0;
}

C. gCampus

辦公室之間有一些道路，每一個道路通過會消耗時間，請問那些沒效率的邊不在任兩個辦公室的最短路徑上。

看起來是能直接丟 floyd algorithm，由於 $|V| \le 100$，只需要窮舉邊兩個端點的經過的最短路徑，複雜度為 $O(V^3 + E V^2)$，仔細看一下還挺大的。

套用單源短路徑 SSSP 的做法，對每一個點都跑一次 dijkstra，檢查 shortest path DAG，複雜度需要 $O(V E \log V)$，點數有點太小 (再大也不方便處理)，大約在數秒內就能跑完。

#include <bits/stdc++.h> 
using namespace std;
const int MAXV = 32767;
const int MAXE = 32767;
const long long INF = 1LL<<62;
struct Edge {
    int to, eid;
    long long w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
long long dist[MAXV];
void addEdge(int x, int y, long long v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, long long dist[], int n) {
typedef pair<long long, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int main() {
    int testcase, cases = 0, n, m;
    int x, y, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        
        e = 0;
        for (int i = 0; i <= n; i++)
            adj[i] = NULL;
            
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            addEdge(x, y, w);
            addEdge(y, x, w);
        }
        
        int on[65536] = {};
        for (int i = 0; i < n; i++) {
            dijkstra(i, dist, n);
            for (int j = 0; j < n; j++) {
                for (Edge *p = adj[j]; p; p = p->next) {
                    if (dist[p->to] == dist[j] + p->w)
                        on[p->eid/2] = 1;
                }
            }
        }
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < m; i++) {
            if (!on[i])
                printf("%d\n", i);
        }
    }
    return 0;
}

D. gSnake

一個貪心蛇遊戲，一開始蛇在左上角長度為 1，並且面向右側。若盤面上黑白染色，所有的奇點都具有食物，每一秒蛇會執行一個動作，直到他咬到自己的身體為止。當蛇碰撞到牆壁時，他會從對稱的地方鑽出。而下一秒接觸到食物時，相當於頭往前直伸產生新的一節。

現在有一串指令，每一個指令告知蛇會在那一秒後，執行順時針或逆時針轉向，請問模擬指令直到死亡或者抵達 $10^9$ 秒，請問蛇的總長為何。

這一題看起來有點可怕，由於貪心蛇所在的棋盤大小偌大無比，導致模擬上複雜度難以估計，但仔細發現指令時間最多 $1 \le X_i \le 1000000$，意即 $10^6$ 秒將會固定方向，在這固定方向模擬，最多吃到 max(R, C) 的食物，接著進入鑽出鑽出的循環狀態，或者進入終盤死亡。

根據循環和模擬情況加總，最多 $O(1000000)$ 步。為了解決偵測，用一個 map< pair<X, Y>, int > 來記錄身體經過的時間點，只要時間點差小於身體總長，表示咬到自己。或者，實做一個 list，維護一個 set< pair<X, Y> > 將頭端插入，移動時將尾巴移除。前者時間複雜度 $O(n \log n)$ 其中 $n = 1000000$，後者跟自身長度有關，但實作稍微複雜。

#include <bits/stdc++.h> 
using namespace std;
const int MAXS = 100005;
const int MAXT = 10e9;
const int dx[4] = {0, 1, 0, -1};	// right, down, left, up
const int dy[4] = {1, 0, -1, 0};
int X[MAXS];
char CMD[MAXS][4];
int main() {
    int testcase, cases = 0, R, C, S;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &S, &R, &C);
        for (int i = 0; i < S; i++)
            scanf("%d %s", &X[i], &CMD[i]);
            
        int len = 1, x = 1, y = 1, dir = 0;
        int cmdIdx = 0, cnt = 0;
        
        set< pair<int, int> > F;
        map< pair<int, int>, int > PASS;
        
        for (int i = 1; i <= MAXT; i++) {
            if (cmdIdx == S && cnt > max(R, C)*2)	// cycle
                break;
            x += dx[dir], y += dy[dir];
            if (x == 0)	x = R;
            if (x > R)	x = 1;
            if (y == 0)	y = C;
            if (y > C)	y = 1;
            
            int &step = PASS[{x, y}]; 
            if (step == 0)	step = -0x3f3f3f3f;
            if (i - step < len)
                break;
            step = i;			
            
            if ((x+y)%2 == 1 && !F.count({x, y})) {
                F.insert({x, y});
                len++, cnt = 0;
            }
            
            if (cmdIdx < S && i == X[cmdIdx]) {
                if (CMD[cmdIdx][0] == 'R')
                    dir = (dir+1)%4;
                else
                    dir = (dir+3)%4;
                cmdIdx++, cnt = 0;
            }
            cnt++;
        }
        printf("Case #%d: %d\n", ++cases, len);
    }
    return 0;
}

Morris' Blog

2016 Google APAC Test 小結

contents

A. Googol String

B. gCube

C. gCampus

D. gSnake