解題區/解題區 - UVa

UVa 11184 - Joyful Ride

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

Suppose you want to own a roller coaster. Before you start, you might be interested in designing the course. The course is circular when seen from above, with n towers of equal distances on it. The figure below shows a course with n=7 (numbers inside circles are heights of towers).

To make the towers look interesting, their heights should be distinct positive integers not greater than n+1. To let customers enjoy a large variety of excitement, the height differences between neighboring towers should be all different. Since there are n height differences, each integer value between 1 and n must appear exactly once. In the example above, the height differences are: 8-1=7, 8-2=6, 7-2=5, 7-3=4, 5-3=2, 5-4=1, 4-1=3. You can check that every integer between 1 and 7 appears exactly once.

Write a program to design the ride.

Input

The input consists of several test cases. Each case contains a single integer n (2 £ n £ 1000), the number of towers. 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 n numbers if the design is possible, ‘-1’ otherwise.

Sample Input

1
2
3
7
234
0

Output for Sample Input

1
2
Case 1: 1 4 5 3 7 2 8
Case 2: -1

Solution

題目描述：

找到一個擺放 N + 1 個數字的環狀，數字彼此之間的差值恰好可以湊出所有 1 到 N 之間的整數。

題目解法：

先窮舉前幾項的可能

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Case 1: -1
Case 2: 1 2 4
Case 3: 1 3 2 5
Case 4: -1
Case 5: -1
Case 6: 1 4 5 3 7 2 8
Case 7: 1 5 4 6 3 8 2 9
Case 8: -1
Case 9: -1
Case 10: 1 6 7 5 8 4 10 3 11 2 12
Case 11: 1 7 6 8 5 9 4 11 3 12 2 13
Case 12: -1
Case 13: -1
Case 14: 1 8 9 7 10 6 11 5 13 4 14 3 15 2 16
Case 15: 1 9 8 10 7 11 6 12 5 14 4 15 3 16 2 17
Case 16: -1
Case 17: -1
Case 18: 1 10 11 9 12 8 13 7 14 6 16 5 17 4 18 3 19 2 20
Case 19: 1 11 10 12 9 13 8 14 7 15 6 17 5 18 4 19 3 20 2 21

可以發現，對於 mod 4 餘 3、0 會沒有解。
仔細觀察一下規律，起頭 1，並且分別是 +-+-+- 從 -1+2-3+4 … 類推。

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
#include <stdio.h>
int main() {
    int n, cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        printf("Case %d:", ++cases);
        if(n%4 != 3 && n%4 != 0)
            puts(" -1");
        else {
            int d = (n+1)/4*2-1 + (n%4 == 0);
            int sum = 1 + d;
            printf(" 1 %d", sum);
            for(int i = 1, j = 0; i < n; i++) {
                if(i == d)
                    continue;
                if(j%2 != d%2)
                    sum += i;
                else
                    sum -= i;
                printf(" %d", sum);
                j++;
            }
            puts("");
        }
    }
    return 0;
}