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

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


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-22 00:27
中南大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-06 22:26
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议