When a student is too tired, he can’t help sleeping in class, even if his favorite teacher is right here in front of him. Imagine you have a class of extraordinarily tired students, how long do you have to wait, before all the students are listening to you and won’t sleep any more? In order to complete this task, you need to understand how students behave.
When a student is awaken, he struggles for a minutes listening to the teacher (after all, it’s too bad to sleep all the time). After that, he counts the number of awaken and sleeping students (including himself). If there are strictly more sleeping students than awaken students, he sleeps for b minutes. Otherwise, he struggles for another a minutes, because he knew that when there is only very few sleeping students, there is a big chance for them to be punished! Note that a student counts the number of sleeping students only when he wants to sleep again.
Now that you understand each student could be described by two integers a and b, the length of awaken and sleeping period. If there are always more sleeping students, these two periods continue again and again. We combine an awaken period with a sleeping period after it, and call the combined period an awaken-sleeping period. For example, a student with a = 1 and b = 4 has an awaken-sleeping period of awaken-sleeping-sleeping-sleeping-sleeping. In this problem, we need another parameter c (1 ≤ c ≤ a + b) to describe a student’s initial condition: the initial position in his awaken-sleeping period. The 1st and 2nd position of the period discussed above are awaken and sleeping, respectively.
Now we use a triple (a, b, c) to describe a student. Suppose there are three students (2, 4, 1), (1, 5, 2) and (1, 4, 3), all the students will be awaken at time 18. The details are shown in the table below.
Write a program to calculate the first time when all the students are not sleeping.
Input
The input consists of several test cases. The first line of each case contains a single integer n (1 ≤ n ≤ 10), the number of students. This is followed by n lines, each describing a student. Each of these lines contains three integers a, b, c (1 ≤ a, b ≤ 5), described above. The last test case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the first time all the students are awaken. If it’ll never happen, output ‘-1’.
Sample Input
3
2 4 1
1 5 2
1 4 3
3
1 2 1
1 2 2
1 2 3
0
Sample Output
Case 1: 18
Case 2: -1
题目类型：简单模拟
算法分析：最大枚举的范围为所有成员周期之积，超出即输出-1，然后对于每个时间位置模拟每个人的操作即可
|
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
/************************************************** filename :c.cpp author :maksyuki created time :2017/12/22 20:10:53 last modified :2017/12/23 18:27:28 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; struct node { int a, b, c, p; int cur; }; node aa[66]; int main() { #ifdef LOCAL CFF; //CFO; #endif int n, id = 1; while(scanf("%d", &n) != EOF) { if(!n) break; int len = 1; for(int i = 1; i <= n; i++) { scanf("%d %d %d", &aa[i].a, &aa[i].b, &aa[i].c); aa[i].p = aa[i].a + aa[i].b; aa[i].cur = aa[i].c; len *= aa[i].p; } int ans = -1; int awk = 0, slp = 0; for(int i = 1; i <= n; i++) { if(aa[i].cur <= aa[i].a) awk++; else slp++; } int awk_pre = awk, slp_pre = slp; for(int i = 2; i <= len; i++) { // for(int j = 1; j <= n; j++) DB(aa[j].cur); for(int j = 1; j <= n; j++) { if(aa[j].cur == aa[j].a) { if(awk_pre >= slp_pre) aa[j].cur = 1; else { aa[j].cur++; awk--, slp++; } } else { if(aa[j].cur == aa[j].p) { aa[j].cur = 1, awk++, slp--; } else aa[j].cur++; } } awk_pre = awk, slp_pre = slp; // cout << i << endl; // DB(awk), DB(slp); // cout << endl; if(awk == n) { ans = i; break; } } printf("Case %d: %d\n", id++, ans); } return 0; } |
- « 上一篇：uva815
- uva1591：下一篇 »