# USACO Section 1.4.3 The Clocks

## 题目

The Clocks
IOI'94 - Day 2
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;
}`