当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2717:Hour Glass

Special Judge 特殊评判
题目描述
You are given two hour glasses. They measure M and N minutes respectively. You wish to use these two hour glasses to measure a target period of T minutes. Each hour glass consists of two glass bowls connected by a narrow section (the "narrows") where sand can flow from one bowl into the other. If all of the sand is in the lower bowl and the hour glass is turned upside down ("flipped"), the sand will flow into the other bowl (which is now the lower bowl) in M or N minutes, respectively.

Initially (at time = 0), all of the sand is in the lower bowl in each of the hour glasses, and both hour glasses are flipped. Subsequently, one can flip one or both of the hour glasses according to the following rules.
  1. When only one of the hour glasses expires at a particular instant, one has four choices of action:
    1. flip the hour glass that expired;
    2. flip the hour glass that did not expire;
    3. flip both hour glasses;
    4. do not flip either one, just let one hour glass sit idle until the other one expires.

  2. When both of the hour glasses happen to expire simultaneously, or if one hour glass has been sitting idle and the other one has just expired, one must flip at least one of the hour glasses.
  3. Any hour glass may be flipped only at an instant when either the same hour glass, or the other one, or both have just expired.

A particular time T can be measured if there is a sequence of hour glass flips such that one (or both) of the hour glasses expires at time T during the sequence. You may assume that flipping an hour glass is instantaneous and does not take any time.
输入解释
The input consists of a number of lines, each representing one instance of the problem. Each line contains three positive integers which represent the values of M, N, and T. You may assume that 2 <= M < N <= 200 and M <= T <= 2000. The input is terminated by a line containing three zeroes.
输出解释
For each instance of the problem, print the shortest sequence of flips which measures the target time T. For each flip, print on a single line the time, followed by a colon and a space, followed by the capacities of the hour glasses to be flipped (separated by a comma if both are flipped). The sequence of flips should be printed in chronological order. If there are multiple shortest sequences, any one is acceptable. If it is impossible to measure the target time T, print "Impossible" on a single line. The output for each instance of the problem should be followed by a line consisting of ten hyphens.
输入样例
4 17 21
4 17 22
8 13 23
0 0 0
输出样例
0: 4,17
17: 4,17
----------
0: 4,17
4: 4
8: 4
12: 4
16: 4
17: 4
18: 4,17
----------
0: 8,13
8: 8
13: 8,13
18: 8,13
----------

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Rocky Mountain 2005

源链接: POJ-2717

最后修改于 2020-10-29T06:40:28+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000 65536