USACO Section 1.4.3 The Clocks

Nov 28, 2013 3 分钟阅读时间 usc, csdn

此页面通过工具从 csdn 导出，格式可能有问题。

题目

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

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

思路

这份题解，算是一边coding一边写出来的，一是好久没码过了，更重要的是这个题目很复杂。。

第一想到的方法就是枚举所有表，或者叫搜索。不管叫啥，反正都不现实，4^9 = 2^18 ,貌似也不错~

但是既然想得瑟，就说一下应该怎么搞。

枚举题目优化的思路都有一点，枚举的各个变量之间能否用一定的关系式推出来。

这个题目里，很显然，如果表A可以通过操作1 2进行，如果操作1执行了1次，那表A离12点还差几次就必须把操作2也进行几次。

先列一下钟表与矩阵的关系图：

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

把上面的关系式反过来，就能在已知 c[i] 通过枚举部分 pi 求出其它 pi

我枚举的是123三个操作，然后剩下6个操作就可以就确定了。

代码

/*
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;
}

USACO Algorithm ACM

huiren

Code Artisan

问渠那得清如许，为有源头活水来