UVA 6662 The Last Ant（模擬退火）
來源：程序員人生 發(fā)布時間：2014-10-04 08:00:01 閱讀次數(shù)：2958次
A straight tunnel without branches is crowded with busy ants coming and going. Some ants walk left
to right and others right to left. All ants walk at a constant speed of 1 cm/s. When two ants meet, they
try to pass each other. However, some sections of the tunnel are narrow and two ants cannot pass each
other. When two ants meet at a narrow section, they turn around and start walking in the opposite
directions. When an ant reaches either end of the tunnel, it leaves the tunnel.
The tunnel has an integer length in centimeters. Every narrow section of the tunnel is integer
centimeters distant from the both ends. Except for these sections, the tunnel is wide enough for ants to
pass each other. All ants start walking at distinct narrow sections. No ants will newly enter the tunnel.
Consequently, all the ants in the tunnel will eventually leave it. Your task is to write a program that
tells which is the last ant to leave the tunnel and when it will.
Figure B.1 shows the movements of the ants during the first two seconds in a tunnel 6 centimeters
long. Initially, three ants, numbered 1, 2, and 3, start walking at narrow sections, 1, 2, and 5 centimeters
distant from the left end, respectively. After 0.5 seconds, the ants 1 and 2 meet at a wide section, and
they pass each other. Two seconds after the start, the ants 1 and 3 meet at a narrow section, and they
turn around.
Figure B.1 corresponds to the first dataset of the sample input.
Figure B.1. Movements of ants
Input
The input consists of one or more datasets. Each dataset is formatted as follows.
n l
d1 p1
d2 p2
.
.
.
dn pnACM-ICPC Live Archive: 6662
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
------分隔線----------------------------
------分隔線----------------------------
