USACO The Clocks 一种O(1)的算法

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 according 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.]

PROGRAM NAME: clocks

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      

思路：9种操作中，没有一种是对单独一个钟进行旋转的，那么能否找到一种操作组合，这一操作组合使一个钟顺时针旋转90度？

设我们对操作i使用了a[i]次（0<=a[i]<=3，因为当a[i]=4时的效果和a[i]=0时一样），那么要只让时钟A顺时针旋转90度的话，由表知，有(a[1]+a[2]+a[4])%4=1,(a[1]+a[2]+a[3]+a[5])%4=0,...使用如下暴力代码可以得到全部的操作次数：

#include<cstdio>
#include<cstring>
#define For(x) for (a[x] = 0; a[x] < 4; ++a[x])
const char C[9][9] =
{
	"ABDE",
	"ABC",
	"BCEF",
	"ADG",
	"BDEFH",
	"CFI",
	"DEGH",
	"GHI",
	"EFHI"
};

bool clocks[9][9];
int a[9], cnt[9];

int main()
{
	puts("const int A[9][9] =\n{");
	int i, j, choose;
	for (i = 0; i < 9; ++i)
		for (j = 0; C[i][j]; ++j)
			clocks[i][C[i][j] - 'A'] = true;
	for (choose = 0; choose < 9; ++choose)
	{
		For(0)For(1)For(2)For(3)For(4)For(5)For(6)For(7)For(8)
		{
			memset(cnt, 0, sizeof(cnt));
			for (i = 0; i < 9; ++i)
				for (j = 0; j < 9; ++j)
					if (clocks[j][i]) cnt[i] += a[j];
			for (i = 0; i < 9; ++i)
			{
				if (i == choose)
				{
					if ((cnt[i] & 3) != 1) break;///x&3=x%4
				}
				else
				{
					if (cnt[i] & 3) break;
				}
			}
			if (i == 9)
			{
				putchar('{');
				for (i = 0; i < 8; ++i) printf("%d,", a[i]);
				printf("%d}%s", a[8], (choose == 8 ? "\n" : ",\n"));
				goto L;
			}
		}
L:
		;
	}
	puts("};");
	return 0;
}
           

随后使用之：

/*
ID: synapse cheng
PROG: clocks
LANG: C++
*/

/*
Executing...
   Test 1: TEST OK [0.000 secs, 3376 KB]
   Test 2: TEST OK [0.000 secs, 3376 KB]
   Test 3: TEST OK [0.000 secs, 3376 KB]
   Test 4: TEST OK [0.000 secs, 3376 KB]
   Test 5: TEST OK [0.000 secs, 3376 KB]
   Test 6: TEST OK [0.000 secs, 3376 KB]
   Test 7: TEST OK [0.000 secs, 3376 KB]
   Test 8: TEST OK [0.000 secs, 3376 KB]
   Test 9: TEST OK [0.000 secs, 3376 KB]

All tests OK.
*/

#include<cstdio>

const int A[9][9] =
{
	{3, 3, 3, 3, 3, 2, 3, 2, 0},
	{2, 3, 2, 3, 2, 3, 1, 0, 1},
	{3, 3, 3, 2, 3, 3, 0, 2, 3},
	{2, 3, 1, 3, 2, 0, 2, 3, 1},
	{2, 3, 2, 3, 1, 3, 2, 3, 2},
	{1, 3, 2, 0, 2, 3, 1, 3, 2},
	{3, 2, 0, 3, 3, 2, 3, 3, 3},
	{1, 0, 1, 3, 2, 3, 2, 3, 2},
	{0, 2, 3, 2, 3, 3, 3, 3, 3}
};

int main()
{
	freopen("clocks.in", "r", stdin);
	freopen("clocks.out", "w", stdout);
	int v[9] = {0}, i, j, k;
	for (i = 0; i < 9; i++)
	{
		scanf("%d", &k);
		for (j = 0; j < 9; j++) v[j] += (4 - k / 3) * A[i][j];
	}
	for (i = 0; i < 9; i++) v[i] &= 3;
	k = 0;
	for (i = 0; i < 9; i++)
		for (j = 0; j < v[i]; j++)
			if (!k) printf("%d", i + 1), k = 1;
			else printf(" %d", i + 1);
	putchar(10);
	return 0;
}