Algoogle

Algorithm for Programming Contest

ONTAK 2007 Hyperclock

Category: ONTAK Tag: implementation

Hyperclock

問題概要


N個の針が1つだけある時計がある. それぞれ盤上には個の番号が1から振られている.
そのN個の時計の針の位置の組によって時刻を決定する時計Hyperclockを考える.
時計を1つ選んで針を1つ進めるか戻すかの操作ができるとき, ありうる全ての組をちょうど1度だけ示し, 初期状態に戻るような操作方法を示せ.
ただし全ての時計は始め1を指しているとし, そのような操作が存在しない場合はNIE(ポーランド語でNOの意)と表示せよ.

解法


ONTAKとはポーランドのOI系の合宿.
この問題は必ず条件を満たす操作方法が存在する.

2つの時計u, vについて2次元の表(縦軸をu, 横軸をv)で考える.
が偶数の場合
uを1からまでおろして, vを1進め, 今度はuをから1まで戻して…とやればよい.
これで最終的に初期状態に戻る.
が奇数の場合
uを1からまで動かして, vを1進め, 今度はuをから1まで戻して…とやる.
この時点で針はそれぞれを指している.
今表の一番下だけ一度も通っていない状態.
よってこれをさらに1つ下げてvの針をから1まで戻せば良い.
あとはuを1進めるだけで初期状態に戻る.

時計が2つでできたら, その操作列を1つの時計としてみる.
あとはそれを次の時計, 更に次の時計, と組み合わせていけば良い.

コード


(hyperclock.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n, k[32];
pii ans[1<<20], tmp[1<<20];

void merge_odd(int sz, int idx)
{
        vector<pii> ret;
        int cur = 0;
        for (int i = 0; i < k[idx]-1; i+=2) {
                for(int i = 0; i < sz-2; i++) tmp[cur++] = ans[i];
                tmp[cur++] = pii(idx,1);
                for (int i = sz-3; i >= 0; i--) tmp[cur++] = pii(ans[i].first,-ans[i].second);
                tmp[cur++] = pii(idx,1);
        }
        for (int i = 0; i < sz-1; i++) tmp[cur++] = ans[i];
        for (int i = 0; i < k[idx]-1; i++) tmp[cur++] = pii(idx,-1);
        tmp[cur++] = ans[sz-1];
        for (int i = 0; i < sz*k[idx]; i++) ans[i] = tmp[i];
}

int merge(int sz, int idx)
{
        if(k[idx]%2) {
                merge_odd(sz,idx);
                return sz*k[idx];
        }
        int cur = 0;
        for (int i = 0; i < k[idx]; i+=2) {
                for(int i = 0; i < sz-1; i++) tmp[cur++] = ans[i];
                tmp[cur++] = pii(idx,1);
                for (int i = sz-2; i >= 0; i--) tmp[cur++] = pii(ans[i].first,-ans[i].second);
                tmp[cur++] = pii(idx,1);
        }
        for (int i = 0; i < sz*k[idx]; i++) ans[i] = tmp[i];
        return sz*k[idx];
}

void solve()
{
        for (int i = 0; i < k[0]; i++) ans[i] = pii(0,1);
        int sz = k[0];
        for (int i = 1; i < n; i++) sz = merge(sz,i);
        for (int i = 0; i < sz; i++) printf("%d %d\n", ans[i].first+1,ans[i].second);
}

void input()
{
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", k+i);
}

int main()
{
        input();
        solve();
        return 0;
}

Comments