Problem Solving►UVa

UVa 700 - Date Bugs

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

因為在達到 b 年時會跳回至 a 年，所以對於給定的年，有可能有多種真實的年分。

如果 y 在他們之間:

a … y … b

  1. y
  2. y -> b -> a -> y
    …

d = (y 到 b) + (a 到 y) = (b - y) + (y - a)
可能的真實年份可以這樣算 : y + d * x = year。
接著只需要從不同電腦裡面找一個最大的顯示年份(真實年份不會小於它)，從它開始窮舉，找可以使所有電腦情況皆符合得。
y + d * x = year => (year - y) % d

Code

UVa 700
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
#include<cstdio>
#define N 20
#define Y 10000

int main()
{
    int n, i, y[N], d[N], Case = 1;

    while (scanf("%d", &n) && n)
    {
        int a, b, max = 0, year;
        for (i = 0; i < n; i++)
        {
            scanf("%d%d%d", &y[i], &a, &b);
            d[i] = b - a;
            if (y[max] < y[i])
                max = i;
        }

        for (year = y[max]; year < Y; year++)
        {
            for (i = 0; i < n; i++)
                if ((year - y[i]) % d[i])//y[i] + d[i] * x = year
                    break;
            if (i == n)
                break;
        }

        printf("Case #%d:\n", Case++);
        if (year < Y)
            printf("The actual year is %d.\n\n", year);
        else
            puts("Unknown bugs detected.\n");
    }

    return 0;
}