ジグザグに動く蟻たちの走行時間を算出するプログラム。

Problem A
Carl the Ant
---- The 2004 ACM Programming Contest World Finals ----

Ants leave small chemical trails on the ground in order to mark paths for other ants to follow. Ordinarily these trails follow rather straight lines. But in one ant colony there is an ant named Carl, and Carl is not an ordinary ant. Carl will often zigzag for no apparent reason, sometimes crossing his own path numerous times in the process. When other ants come to an intersection, they always follow the path with the strongest scent, which is the most recent path that leads away from the intersection point.
 「ほかの蟻の道しるべになるので、蟻は通った道に臭跡を残している。ふつう、これらの臭跡がそこそこの直線になるが、ひとつだけ、カールと呼ばれる蟻だけは特別。理由不明だが、カール蟻はジグザグに動き、本来の道を何度も途中で横切ったりする。他の蟻が交差点に来ると、最も臭いの強い道、つまり、交差点から最後にできた道、に進む。」

Ants are 1 centimeter long, move and burrow at 1 centimeter per second, and follow their paths exactly (bending at right angles when moving around corners). Ants cannot cross or overlap each other. If two ants meet at the exact same instant at an intersection point, the one that has been on Carl’s path the longest has the right of way; otherwise, the ant that has been waiting the longest at an intersection will move first.
 「蟻は長さが1cm、動くのももぐるのも1秒当たり1cmのスピード。また精確に道を沿って進む(コーナーのところでは直角に曲がる)。ほかの蟻を追い越したり、オーバーラップしたりすることはない。蟻2つが交差点で出くわしたら、最も長くカール蟻が歩いた道にいた蟻が優先的に動く。あるいは、最も長く交差点で待たされた蟻が先に動く。」

Carl burrows up from the ground to start at the origin at time 0. He then walks his path and burrows back down into the ground at the endpoint. The rest of the ants follow at regular intervals. Given the description of Carl’s path and when the other ants start the path, you are to determine how long it takes the entire set of ants to finish burrowing back into the ground. All the ants are guaranteed to finish.
 「カール蟻は土の中から現われて原点の位置から、時間0よりスタート。カールは道を歩き、終点のところで再び土に戻る。他の蟻は同じ時間間隔でつぎつぎと現われてくる。カール蟻の歩く道、および他の蟻のスタート時間が与えられるものとして、すべての蟻が歩き終え、土に戻るまでの時間を計算して欲しい。すべての蟻は途中で止めることはない。」

Input

Input consists of several test cases. The first line of the input file contains a single integer indicating the number of test cases.
 「入力に複数のテストケースが含まれる。入力ファイルの1行目にテストケースの数を示す整数が1つ入る。」

The input for each test case starts with a single line containing three positive integers n (1<=n<=50), m (1<=m<=100), and d (1<d<100). Here, n is the number of line segments in Carl's path, m is the number of ants traveling the path (including Carl), and d is the time delay before each successive ant's emergence. Carl (who is numbered 0) starts at time 0. The next ant (ant number 1) will emerge at time d, the next at time 2d, and so on. If the burrow is blocked, the ants will emerge as soon as possible in the correct order.
 「各テストケースでは、最初に3つの正整数 n (1<=n<=50), m (1<=m<=100), および d (1<d<100) を含む行が入る。n はカール蟻が歩く道を示す線分の数、m はカールを含む蟻の数、d は個々の蟻が現われてくる遅延時間。カール(番号0)は時間0からスタート。つぎの蟻(番号1)は時間dに現われる、そのつぎは時間2d、等。穴の出口が塞がれたら、決められた順番で可能になった時点で蟻が外に出てくる。」

Each of the next n lines for the test case consists of a unique integer pair x y (-100<x, y<100), which is the endpoint of a line segment of Carl's path, in the order that Carl travels. The first line starts at the origin (0,0) and the starting point of every subsequent line is the endpoint of the previous line.
 「つぎのn行に、異なる整数ペア x y (-100<x, y<100) が入る。x, y ペアはカール蟻が歩く道である線分の終点を表し、カール蟻が歩く道順と一致する。最初の線分は原点 (0, 0)からスタートし、その後に続く線分は起点が前の線分の終点と重なる。」

For simplicity, Carl always travels on line segments parallel to the axes, and no endpoints lie on any segment other than the ones which they serve as an endpoint.
 「簡単にするため、カールは座標軸と並行な線分を歩き、終点と見なすもの以外に、線分上に終点がないと仮定してよい。」

Output

The output for each case is described as follows:
 「各ケースの出力は以下になる。」

Case C:
Carl finished the path at time t1
The ants finished in the following order: 
a1 a2 a3 ... am
The last ant finished the path at time t2
 「ケース C:
  カールは時間t1で走行終了。
  蟻はつぎの順番で終了:
  a1 a2 a3 ... am
  最後の蟻は時間t2で走行終了。」

Here, C is the case number (starting at 1), a1, a2, a3, … am are the ant numbers in the order that they go back underground, and t1 and t2 are the times (in seconds) at which Carl and the last ant finish going underground. You should separate consecutive cases with a single blank line.
 「Cはケース番号(1からのスタート)、a1, a2, a3, … am は土に戻る蟻の番号順、t1, t2は時間(秒単位)、カールと最後の蟻が土に戻る時間。各ケースの間に空白行を入れること。」

Sample Input

2
4 7 4
0 4
2 4
2 2
-2 2
4 7 2
0 4
2 4
2 2
-2 2

Output for the Sample Input

Case 1:
Carl finished the path at time 13
The ants finished in the following order:
0 2 1 3 4 5 6
The last ant finished the path at time 29

Case 2:
Carl finished the path at time 13
The ants finished in the following order:
0 4 1 5 2 6 3
The last ant finished the path at time 19

Comments are closed.

Post Navigation