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个数,每个数都只可能由3,6,9,12四个数字组成,代表时间。9个数由顺序A到 I 9个字母表示。题中给出9种选择方法,每种方法都有一串字母,代表要转动该字母位置上的钟,每次最多只能转90度。问如何选择方法来使全部钟都能为12。最后输出该方法数序列,若多个满足,则输出字典序最小的。
思路:
DFS。方案数一共有4^9种,一个钟最多只能转4次。一开始将点数定义为0,1,2,3来方便计算。
有两点必须清楚:
1.每种方法不止用一次,可以用多次;
2.每个钟都可以用多次,但事实上一个钟最多只能转4次,因为当转完4次后就回到了原来的位置了;最终生成的方法数序列与每种方法选的顺序无关。
AC:
/* TASK:clocks LANG:C++ ID:sum-g1 */ #include<stdio.h> #include<string.h> typedef struct { int p[4][4]; }node; node way[10]; int map[4][4],time[10]; int fin[50],num[50],minans=50,temp=0; void init() { memset(way,0,sizeof(way)); memset(time,0,sizeof(time)); way[1].p[1][1]=way[1].p[1][2]=way[1].p[2][1]=way[1].p[2][2]=1; way[2].p[1][1]=way[2].p[1][2]=way[2].p[1][3]=1; way[3].p[1][2]=way[3].p[1][3]=way[3].p[2][2]=way[3].p[2][3]=1; way[4].p[1][1]=way[4].p[2][1]=way[4].p[3][1]=1; way[5].p[1][2]=way[5].p[2][1]=way[5].p[2][2]=way[5].p[2][3]=way[5].p[3][2]=1; way[6].p[1][3]=way[6].p[2][3]=way[6].p[3][3]=1; way[7].p[2][1]=way[7].p[2][2]=way[7].p[3][1]=way[7].p[3][2]=1; way[8].p[3][1]=way[8].p[3][2]=way[8].p[3][3]=1; way[9].p[2][2]=way[9].p[2][3]=way[9].p[3][2]=way[9].p[3][3]=1; } int check() { int res=1; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(map[i][j]!=0) { res=0; break; } return res; } void dfs(int w,int ans) { num[ans]=w; time[w]++; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) map[i][j]=(map[i][j]+way[w].p[i][j])%4; if(ans>=minans||time[w]>3) return; //WA在这里,time[w]>3时应该是return //但是一开始把time[w]>3放在数组中了,并且判断的时候是time[w]>3时是continue //最后导致前面会输出很多多余的数 if(check()) { minans=ans; for(int i=1;i<=minans;i++) fin[i]=num[i]; } for(int k=num[ans];k<=9;k++) { if(!k) continue; dfs(k,ans+1); for(int o=1;o<=3;o++) for(int j=1;j<=3;j++) map[o][j]=(map[o][j]+4-way[k].p[o][j])%4; time[k]--; } } int main() { freopen("clocks.in","r",stdin); freopen("clocks.out","w",stdout); init(); for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { scanf("%d",&map[i][j]); if(map[i][j]==3) map[i][j]=1; if(map[i][j]==6) map[i][j]=2; if(map[i][j]==9) map[i][j]=3; if(map[i][j]==12) map[i][j]=0; } dfs(0,0); for(int i=1;i<=minans;i++) { printf("%d",fin[i]); i==minans?printf("\n"):printf(" "); } return 0; }
总结:
1.首先是读题问题,一开始读错了两次,写了两遍错误的代码。第一次单纯只因为没有完全理解题意,第二次是读懂了,但是以为每种方法最多只允许用1次;
2.写dfs时候的思维还是略混乱,更新clock语句应放在哪里,判断return的语句又应放在哪里,return之后哪些变量要更新回原来状态,这些都要一一考虑清楚;
相关推荐
USACO题目The Clocks解答,包括代码
分布式文件系统时序,lamport论文,Time-Clocks-and-the-Ordering-of-Events-in-a-Distributed-System.pdf
Time, Clocks, and the Ordering of Events in a Distributed System论文的英文PPT
Some clocks will have mutiple bits to enable the clocks, and the bits to disable the clock is not same as enabling bits.
reprogram clocks / memory
修改后的jetson_clocks.sh文件。如果TX2开发板的同名文件运行出错,可下载替换。
Clocks and Timers Random numbers and distributions New smart pointers Regular expressions New STL containers, such as arrays, forward lists, and unordered containers New STL algorithms Tuples Type ...
MSTP clocks. We can t use standard gate clocks as we need to poll on the status register when enabling the clock.
These are all the functions necessary to implement POSIX clocks & timers.
Implement CPU time clocks for the POSIX clock interface.
文中谈到了FPGA以及ASIC设计中的复位策略,对于实际工程实践以及笔试面试还有专业人员阅读都是很好的资料,复位是一个常谈的话题,这个文档就能让你明白复位的设计。
一年级英语作文Clocks
Clocks and Timers Random numbers and distributions New smart pointers Regular expressions New STL containers, such as arrays, forward lists, and unordered containers New STL algorithms Tuples ...
Marvell PXA family clocks.
USACO编程题中的一个,由一般方法编程,容易看懂,仅供交流。
USACO的题目Clocks解析 ,包括解答和代码。
三年级英语作文Clocks
Definitions and headers related to device clocks.
lamport time clocks.pdf(Time, Clocks, and the Ordering of Events in a Distributed System论文)