시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 3 | 1 | 1 | 100.000% |
Kuno Kunibertson is moving house from Amman to Brasília. His new employer pays the trip and allows him to make as many stop-overs as he wants; the only two conditions are: (1) the i-th stop-over city of the trip should be nearer to Brasília than the (i − 1)-th stop-over city and (2) the trip should not take more than m nights. Furthermore, as Brasília is a transport hub, there is a direct flight from each city to Brasília. Kuno Kunibertson has to supply the following information to the trip evaluation:
The trip evaluation agency will then plan out a suitable trip for him with some artificial intelligence program, which optimises the trips according to a data base of tourist attractions. However, in order not to overload its computers, the trip evaluation agency has the following requirement:
Note that for counting, two itineraries are considered to be different, if one of the following conditions applies:
For example, if the itinerary is Amman - Cairo - Dakar - Brasília, then an itinerary which departs from Cairo on day 2 differs from another itinerary which departs from Cairo on day 3. Furthermore, if there are two flights from Dakar to Brasília (even if they depart and arrive on the same days), the itineraries are different since they use these different flights.
As there is a penalty when the condition (∗) is violated, Kuno Kunibertson asks his friend Herbert Hercules to write for him a computer program which computes the number of itineraries which use up to k days.
Your program must read from standard input.
The first row of the input consists of three integers n, m and h, where n is the number of cities, m is the strict upper bound of the number of nights used and h is the number of follow-on flights per city. We assume city 0 is Amman and city n − 1 is Brasília. We also assume city i is closer to Brasília than city j if i > j.
Then, the input contains n − 1 rows, where the ith row, i = 0, 1, . . . , n − 2, consists of h pairs of integers (j, k), which means that Kuno Kunibertson can fly from city i to city j and stays at least k nights. If there are several flights to the same city, they are considered different. All 2h integers are listed in one row separated by spaces.
Your program must output to standard output only. The output is a list of m integers between 0 and 500000001 which are, respectively, the number of itineraries from Amman to Brasília taking 0, 1, . . ., m − 1 nights, respectively. If the number of itineraries is 500000001 or more, the output should be 500000001.
At most one stop-over means that all outgoing flights from a stop-over location go directly to Brasília. No minimum stay means that the stay in each stop-over can be any number (including 0) and that Kuno Kunibert can report to work on arrival in Brasília.
4 4 3 1 2 2 2 3 0 2 2 2 3 3 0 3 1 3 3 3 0
1 1 3 6
Here city 0 stands for Amman, city 1 might stand for Cairo, city 2 for Dakar and city 3 for Bras´ılia. So the data stands for the following information.
City | Flight a To City | Min. Stay | Flight b To City | Min. Stay | Flight c to City | Min. Stay |
---|---|---|---|---|---|---|
Amman | Cairo | 2 | Dakar | 2 | Brasília | 0 |
Cairo | Dakar | 2 | Dakar | 3 | Brasília | 0 |
Dakar | Brasília | 1 | Brasília | 3 | Brasília | 0 |
The itineraries are the following, where flight a is the first, flight b the second and flight c the third flight out of a city; the overall number of itineraries is 11.
Total Nights | Itinerary | Day | From | To | Flight | Nights at Next City |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 3 | c | 0 |
1 | 0 | 0 | 0 | 3 | c | 1 |
2 | 0 | 0 2 |
0 1 |
1 3 |
a c |
2 0 |
1 | 0 2 |
0 2 |
2 3 |
b c |
2 0 |
|
2 | 0 | 0 | 3 | c | 2 | |
3 | 0 | 0 2 |
0 1 |
1 3 |
a c |
2 1 |
1 | 0 3 |
0 1 |
1 3 |
a c |
3 0 |
|
2 | 0 2 |
0 2 |
2 3 |
b a |
2 1 |
|
3 | 0 3 |
0 2 |
2 3 |
b c |
3 0 |
|
4 | 0 2 |
0 2 |
2 3 |
b c |
2 1 |
|
5 | 0 | 0 | 3 | c | 3 |
4 8 3 1 0 2 1 3 0 3 1 3 2 3 0 3 1 3 1 3 0
2 5 11 17 23 29 35 41
This testcase consists of test data with at most one stop over.
4 11 3 1 0 2 0 3 0 0 0 2 0 3 0 0 0 0 0 3 0
4 8 13 19 26 34 43 53 64 76 89
This testcase consists of test data with no minimum stay.
8 8 8 1 0 1 0 1 0 1 0 1 0 1 0 1 0 7 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 7 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 7 0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 7 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 7 0 6 0 6 0 6 0 6 0 6 0 6 0 6 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0
960800 6702725 26746084 80092734 199948848 439388874 500000001 500000001
This testcase consists of test data which generate large output numbers so that the rule comes into place which limits the maximum of an output number to 500000001.