| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1116 | Power Crisis |
|
| 1120 | You want what filled? |
|
| 1124 | Morning Walk |
|
| 1128 | Airport Express |
|
Description
[[Category: Simulation]]
During the power crisis in New Zealand this winter (caused by a shortage of rain and hence low levels in the hydro dams), a contingency scheme was developed to turn off the power to areas of the country in a systematic, totally fair, manner. The country was divided up into N regions (Auckland was region number 1, and Wellington number 13). A number, m, would be picked `at random', and the power would first be turned off in region 1 (clearly the fairest starting point) and then in every m'th region after that, wrapping around to 1 after N, and ignoring regions already turned off. For example, if N = 17 and m = 5, power would be turned off to the regions in the order:1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7.
The problem is that it is clearly fairest to turn off Wellington last (after all, that is where the Electricity headquarters are), so for a given N, the `random' number m needs to be carefully chosen so that region 13 is the last region selected.
Write a program that will read in the number of regions and then determine the smallest number m, which will ensure that Wellington (region 13) can function while the rest of the country is blacked out.
Input
Input will consist of a series of T (T ≤50000) lines, each line containing the number of regions (N) with 13 ≤ N < 100. The file will be terminated by a line consisting of a single 0.
You may assume that m is less than 1000 for any N < 100.
Output
Output will consist of a series of lines, one for each line of the input. Each line will consist of the number m according to the above scheme.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[[Category: Graphs and DFS]]
Now that Ryan and Larry infuriated the bear, they're now forced to do menial tasks for food; one such task is filling in potholes on this deserted island. But of course, it's never quite that easy, as the bear forces them to fill in the biggest hole first. Since Ryan and Larry are still lazy (very little has changed, you see), can you tell them the order to fill in the holes?
Input
There are at most 100 test cases. The first line will contain two numbers x and y, followed by x lines of y characters each. (x and y are less than 50). The holes will be represented by the uppercase characters A to Z, and regular land will be represented by ".". There will be no other characters in the map. Two characters in the map are considered in the same hole if and only if they are adjacent in either vertical or horizontal direction. The size of a hole is measured by the number of characters in the hole. Input will be terminated by having 0 0 as input.
Output
For each map, output the problem number (as shown below), then output the hole represented by the character, and the number of space the hole takes up, sorted by the size of the hole, break ties by sorting the characters in alphabetical order, as shown in the sample output on a separate line as shown below.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[[Category: Eulerian Circuit]]
Kamal is a Motashota guy. He has got a new job in Chittagong. So, he has moved to Chittagong from Dinajpur. He was getting fatter in Dinajpur as he had no work in his hand there. So, moving to Chittagong has turned to be a blessing for him. Every morning he takes a walk through the hilly roads of charming city Chittagong. He is enjoying this city very much. There are so many roads in Chittagong and every morning he takes different paths for his walking. But while choosing a path he makes sure he does not visit a road twice not even in his way back home. An intersection point of a road is not considered as the part of the road. In a sunny morning, he was thinking about how it would be if he could visit all the roads of the city in a single walk. Your task is to help Kamal in determining whether it is possible for him or not.
Input
Input will consist of at most 100 test cases. Each test case will start with a line containing two numbers. The first number indicates the number of road intersections and is denoted by N (2 ≤ N ≤ 200). The road intersections are assumed to be numbered from 0 to N - 1. The second number R denotes the number of roads (0 ≤ R ≤ 10000). Then there will be R lines each containing two numbers c1 and c2 indicating the intersections connecting a road.
Output
Print a single line containing the text “Possible” without quotes if it is possible for Kamal to visit all the roads exactly once in a single walk otherwise print “Not Possible”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[[Category: Single Source Shortest Path]]
In a small city called Iokh, a train service, Airport-Express, takes residents to the airport more quickly than other transports. There are two types of trains in Airport-Express, the Economy-Xpress and the Commercial-Xpress. They travel at different speeds, take different routes and have different costs.
Jason is going to the airport to meet his friend. He wants to take the Commercial-Xpress which is supposed to be faster, but he doesn't have enough money. Luckily he has a ticket for the Commercial-Xpress which can take him one station forward. If he used the ticket wisely, he might end up saving a lot of time. However, choosing the best time to use the ticket is not easy for him.
Jason now seeks your help. The routes of the two types of trains are given. Please write a program to find the best route to the destination. The program should also tell when the ticket should be used.
Input
The input consists of at most 20 test cases. Consecutive cases are separated by a blank line.
The first line of each case contains 3 integers, namely N, S and E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ N), which represent the number of stations, the starting point and where the airport is located respectively.
There is an integer M (1 ≤ M ≤ 1000) representing the number of connections between the stations of the Economy-Xpress. The next M lines give the information of the routes of the Economy-Xpress. Each consists of three integers X, Y and Z (X, Y ≤ N, 1 ≤ Z ≤ 100). This means X and Y are connected and it takes Z minutes to travel between these two stations.
The next line is another integer K (1 ≤ K ≤ 20) representing the number of connections between the stations of the Commercial-Xpress. The next K lines contain the information of the Commercial-Xpress in the same format as that of the Economy-Xpress.
All connections are bi-directional. You may assume that there is exactly one optimal route to the airport. There might be cases where you MUST use your ticket in order to reach the airport.
Output
For each case, you should first list the number of stations which Jason would visit in order. On the next line, output "Ticket Not Used" if you decided NOT to use the ticket; otherwise, state the station where Jason should get on the train of Commercial-Xpress. Finally, print the total time for the journey on the last line. Consecutive sets of output must be separated by a blank line.