[UVA] 10423 - Peter Takes a Tramway
Problem E
Peter Takes a
Tramway
Input: standard input
Output: standard output
Time Limit: 2 seconds
Main Town has a well-developed system of tramway network. Since most of the important buildings in town are located along the Main Street, almost all the tramways pass through the street. All the stops along the Main Street, and there are very many of them, are numbered with numbers: 0, 1, 2 and so on. All the tramways enter the Main Street at the stop numbered 0 and continue towards the higher numbered stops. For each tramway line, which is identified also by a number, there is a schedule posted at stop 0 giving the minutes within an hour when a tramway of this line leaves the stop.
Peter arrives at stop 0 at m minutes (0 <= m < 60) after an hour and takes the first tramway that leaves stop 0 along the Main Street. If Peter arrives at stop 0 the same minute when a tram leaves, Peter manages to board the tram. He leaves the tram at the next stop and takes the next tram that arrives and continues to the next stop where he leaves. Peter continues in this fashion until he reaches stop 0 < n < 1000000000. By which tram will Peter arrive at stop n?
Input
Input contains multiple cases. The first line of a case gives t, the number of tramway lines, 0<t<30. The next t lines each contain a number of a tram line followed by a colon and then a list (separated by spaces) of minutes after a full hour when the tram of this line leaves stop 0. Each list of departure times is terminated by -1. No tram leaves stop 0 more than 20 times in an hour, no two trams leave station 0 at the same time, all the trams have the same speed and they never meet at a stop. A line with m and n then follows. The input ends with a line where t= 0. This line should not be processed.
Output
For each case of input, output in a format shown below the number of the tram line by which Peter arrives at stop n.
Sample Input
111: 10 20 30 -13 2211: 10 20 30 -1134: 16 25 35 45 58 -148 7830
Sample Output
Case 1: Peter arrives at stop 2 by tram 11.Case 2: Peter arrives at stop 783 by tram 134.
(Problem-setters: Piotr Rudnicki, University of Alberta, Canada)
“If the educational system of an institute is based on mere memorization
and directionless class notes then it surely will struggle to
arrange a proper programming contest.”
題目描述：
Peter 要搭電車抵達某一個地方，一開始從站牌 0 時刻 m 開始，
每到一個站後會下來等下一班電車再往下一個前進。
給所有電車從站牌 0 發車的時間，問抵達第 n 個站是用哪一班車。
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, m, t, cases = 0;
while(scanf("%d", &n) == 1 && n) {
int i, j, id, x;
vector< pair<int, int> > a;
for(i = 0; i < n; i++) {
scanf("%d: ", &id);
while(scanf("%d", &x) == 1 && x != -1)
a.push_back(make_pair(x, id));
}
sort(a.begin(), a.end());
scanf("%d %d", &t, &m);
for(i = 0; i < a.size(); i++) {
if(a[i].first >= t)
break;
}
printf("Case %d: Peter arrives at stop %d by tram %d.\n", ++cases, m, a[(i - 1 + m)%a.size()].second);
}
return 0;
}