解題區/解題區 - UVa

UVa 239 - Tempus et mobilius. Time and motion

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有一個神秘的球時鐘，球時鐘會有三個堆疊位置，分別是存放每分鐘、每五分鐘、每一個小時的球球，軌道每一分鐘會將一個球釋出，並且滾入位置，放置的位置優先順序為每分鐘、每五分鐘、每小時。

如果滾入的位置分別滿了 5, 12, 12 個球，則該位置的球將會按照原本進入順序的反順序放入軌道隊列的最晚端。在剛好滿的那個瞬間，那個球將會到次優先的位置去。

假使球有各自的編號，請問在第幾天的同一個時刻後，會回到原本的位置。

Sample Input

1
2
3
30
45
0

Sample Output

1
2
30 balls cycle after 15 days.
45 balls cycle after 378 days.

Solution

先模擬一天下去後，得到每一天位置改變的情況，也就是會得到置換群的結果，根據這個結果，計算每一個置換週期，取最小公倍數即可。

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 <stdio.h> 
#include <stack>
#include <queue>
using namespace std;
long long gcd(long long x, long long y) {
    for(long long t; x%y; t = x, x = y, y = t%y);
    return y;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        // simulation
        queue<int> Q;
        stack<int> minute, five, hour;
        for(int i = 0; i < n; i++)
            Q.push(i);
        for(int i = 0; i < 24 * 60; i++) {
            int x = Q.front();
            Q.pop();
            if(minute.size() < 4) {
                minute.push(x);
            } else {
                while(!minute.empty())
                    Q.push(minute.top()), minute.pop();
                if(five.size() < 11)
                    five.push(x);
                else {
                    while(!five.empty())
                        Q.push(five.top()), five.pop();
                    if(hour.size() < 11)
                        hour.push(x);
                    else {
                        while(!hour.empty())
                            Q.push(hour.top()), hour.pop();
                        Q.push(x);
                    }
                }
            }
        }
        
        // permutation group
        int M[8192], visited[8192] = {};
        for(int i = 0; i < n; i++)
            M[i] = Q.front(), Q.pop();
        long long ret = 1;
        for(int i = 0; i < n; i++) {
            if(visited[i] == 0) {
                int j, len = 1;
                visited[i] = 1;
                for(j = M[i]; j != i; j = M[j]) {
                    visited[j] = 1, len++;
                }
                ret = ret / gcd(ret, len) * len;
            }
        }
        printf("%d balls cycle after %lld days.\n", n, ret);  
    }
    return 0;
}