# 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;
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;
bool found = false;
for ( p = 0; p < 4; p++ ){
for ( p = 0; p < 4; p++ ){
for ( p = 0; p < 4; p++ ){
p = cal(c, p, p);
p = cal(c, p, p, p);
p = cal(c, p, p);
p = cal(c, p, p, p);
p = cal(c, p, p);
p = cal(c, p, p);
if (((c + p + p + p + p + p) % 4 == 0) &&
((c + p + p + p + p ) % 4 == 0) &&
((c + p + p + p + p ) % 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;
}` 