USACO Section 1.4.3 The Clocks

## 题目

<center>
</center> <center style="font&#45;family&#58;STHeiti&#59;font&#45;size&#58;14px&#59;"> The Clocks
IOI'94 - Day 2
</center> Consider nine clocks arranged in a 3x3 array thusly:
```|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
G            H            I
```

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

 Move Affected clocks 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI

### Example

Each number represents a time accoring to following table:
```9 9 12       9 12 12       9 12 12        12 12 12      12 12 12
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12
```

[But this might or might not be the `correct' answer; see below.]

### INPUT FORMAT

 Lines 1-3: Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

### SAMPLE INPUT (file clocks.in)

```9 9 12
6 6 6
6 3 6
```

### OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

### SAMPLE OUTPUT (file clocks.out)

`4 5 8 9`

## 思路

Ci = C[i] / 3;
```clocks  operates
1 	1 2 4		( C1 + p1 + p2 + p4 ) % 4 == 0
2 	1 2 3 5		( C2 + p1 + p2 + p3 + p5 ) % 4 == 0
3 	2 3 6		...
4 	1 4 5 7 	...
5 	1 3 5 7 9	...
6 	3 5 6 9
7 	4 7 8
8	5 7 8 9
9 	6 8 9
```

## 代码

``````/*
ID:zhrln1
PROG:clocks
LANG:C++
*/
#include <cstdio>
#include <iostream>
using namespace std;
int c[11];
int cal(int a, int b, int c){
int t =  - a - b - c;
while ( t < 0 ) t += 4;
return t;
}
int cal(int a, int b, int c, int d){
int t =  - a - b - c - d;
while ( t < 0 ) t += 4;
return t;
}
int main(){
freopen("clocks.in","r",stdin);
freopen("clocks.out","w",stdout);
for (int i(1);i<=9;i++) {
cin >> c[i];
c[i] /= 3;
}
int p[11];
bool found = false;
for ( p[1] = 0; p[1] < 4; p[1]++ ){
for ( p[2] = 0; p[2] < 4; p[2]++ ){
for ( p[3] = 0; p[3] < 4; p[3]++ ){
p[4] = cal(c[1], p[1], p[2]);
p[5] = cal(c[2], p[1], p[2], p[3]);
p[6] = cal(c[3], p[2], p[3]);
p[7] = cal(c[4], p[1], p[4], p[5]);
p[8] = cal(c[7], p[4], p[7]);
p[9] = cal(c[9], p[6], p[8]);
if (((c[5] + p[1] + p[3] + p[5] + p[7] + p[9]) % 4 == 0) &&
((c[8] + p[5] + p[7] + p[8] + p[9] ) % 4 == 0) &&
((c[6] + p[3] + p[5] + p[6] + p[9] ) % 4 == 0 )){
found = 1;
break;
}
if ( found ) break;
}
if ( found ) break;
}
if ( found ) break;
}
int i = 1;
while ( p[i] == 0 ) i++;
printf("%d",i);
p[i--]--;
while ( ++i <= 9 ) while ( p[i]-- ) printf(" %d",i);
printf("\n");
return 0;
}``````

2022-12-07 19:38

2022-12-22 00:27

2022-12-29 13:09
Durham University_2022

2022-12-08 11:03

2022-12-13 23:34

2022-12-27 16:44

2022-12-12 17:48

2022-12-24 15:47

01-20 13:57

2022-12-06 22:26