| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1306 | Energy Saver |
|
| 2114 | Interstar Transport |
|
| 4009 | A Spy in the Metro |
|
| 4047 | Morning Walk |
|
Description
Welcome to NTHU Online Judge! You must notice the avenue planted with many streetlamps. Since energy issue is serious, NTHU decided to turn off some streetlamps. However, there are so many activities held in NTHU, sometimes we need more lights for safety, so a fixed setting is not flexible.
As a computer science student, Scott designed a system to control the setting of streetlamps. At first, he gave every streeplamps a number from 1, 2, 3, ..., and so on. There is a control panel with two lines of buttons, and the buttons each line are indexed from 1 to n provided that the total number of streeplamps is n. When Scott pushed a button on first line, e.g: i_th one, the status of i_th streetlamp changes. Changing status means that if a streetlamp is turn off, then it would be turned on, and vice versa. This kind of action is called "normal" push.
Another line of buttons is more powerful, called "toggle" push. If we toggle pushed the i_th button, then the status of streetlamps from the i_th streetlamp to the last(n_th) one would be changed. For example, if we toggle pushed 5th button, then the status of streetlamps with index 5, 6, ..., n will be changed.
Now we want to know how to minimize the total number of normal push and toggle push on buttons. Please write a program to help Scott. We assume that originally all streetlamps are turned off.
Input
The first line is the number of test cases. Each test case starts with an integer n and the next line are n integers v_1, v_2, ..., v_n. n(<=10^6) is the number of streeplamps, and v_i is i_th streeplamp status for final setting. v_i is either 0 or 1, 0 is turned off and 1 is turned on.
Output
For each test case, output the test case number and the minimum number of push. See sample for more details.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
By 2100, space travel will be a reality for the Milky Way (Solar Galaxy) residents. The Interstar Transport Travel agency operates scheduled direct space transports (flights) between some of the most popular planet destinations in the Milky Way. The cost of these scheduled direct transports are predetermined in Galaro (Galaxy Currency unit) and are published in many different languages. For travel to planets that is not on the schedule, there are slower, yet free, space flights from the closest planet that is on the direct transport list. To help travelers plan their itinerary, the Interstar Transport wants to offer a mobile application that can find the best traveling option, based on the total cost of the direct transports on the itinerary. Given the starting and destination planets on the itinerary, find the sequence of direct transports that has the lowest total traveling cost. Output all the planets in sequence that one must pass through on this best route. If two or more routes exist with the same cost, then the route that goes through the least number of intermediate planets is considered a better route. There will always exist a unique best route for any of the given test cases.
Technical Specification
- The number of planets on the direct transport list is at most s, 1 ≤ s ≤ 26. The planets are labeled using capital letters of the English alphabets, i.e., “A”, “B”, “C”, ..., “Z”, in no particular order.
- The Interstar Transport operates at most p, 1 ≤ p ≤ 200, direct transports between planets. There is at most one (could be none) direct transport between any two distinct planets.
- The cost of any transport is given as a natural number less than or equal to 100 Galaros.
Input
The first line of the input file contains two integers, s and p, separated by a space. The next p lines each contains two letters, ei and ej , followed by a natural number, dij , indicating that there exists a direct transport between planets ei and ej with a cost of dij . The next line contains an integer n ≤ 20, indicating the number of queries to follow. For each of the next n lines, each line contains two letters ek and em, indicating a user is looking for a best (lowest cost) way to get from planet ek to planet em.
Output
For each of the n queries in the input, output on one line the best route to take, in the sequence of starting planet, the intermediate planets in sequence along the route and the destination planet; all separated by one blank space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. After several thrilling events we find her in the first station of Algorithms City Metro, examining the time table. The Algorithms City Metro consists of a single line with trains running both ways, so its time table is not complicated.Maria has an appointment with a local spy at the last station of Algorithms City Metro.
Maria knows that a powerful organization is after her. She also knows that while waiting at a station, she is at great risk of being caught. To hide in a running train is much safer, so she decides to stay in running trains as much as possible, even if this means traveling backward and forward. Maria needs to know a schedule with minimal waiting time at the stations that gets her to the last station in time for her appointment. You must write a program that finds the total waiting time in a best schedule for Maria.
The Algorithms City Metro system has N stations, consecutively numbered from 1 to N. Trains move in both directions: from the first station to the last station and from the last station back to the first station. The time required for a train to travel between two consecutive stations is fixed since all trains move at the same speed.Trains make a very short stop at each station, which you can ignore for simplicity. Since she is a very fast agent, Maria can always change trains at a station even if the trains involved stop in that station at the same time.
Input
The input file contains several test cases. Each test case consists of seven lines with information as follows.
The integer N ( 2 ≤ N ≤ 50), which is the number of stations.
Line 2.
The integer T ( 0 ≤ T ≤ 200), which is the time of the appointment.
Line 3.
N - 1 integers: t1, t2,..., tN - 1 ( 1 ≤ ti ≤ 70), representing the travel times for the trains between two consecutive stations: t1 represents the travel time between the first two stations, t2 the time between the second and the third station, and so on.
Line 4.
The integer M1 ( 1 ≤ M1 ≤ 50), representing the number of trains departing from the first station.
Line 5.
M1 integers: d1, d2,..., dM1 ( 0 ≤ di ≤ 250 and di < di + 1), representing the times at which trains depart from the first station.
Line 6.
The integer M2 ( 1≤M2≤50), representing the number of trains departing from the N-th station.
Line 7.
M2 integers: e1, e2,..., eM2 ( 0 ≤ ei ≤ 250 and ei < ei + 1) representing the times at which trains depart from the N-th station.
The last case is followed by a line containing a single zero.
Output
For each test case, print a line containing the case number (starting with 1) and an integer representing the total waiting time in the stations for a best schedule, or the word `impossible' in case Maria is unable to make the appointment. Use the format of the sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Kamal is a Motashota guy. He has got a new job in
Input
Input will consist of several 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 Rdenotes 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”.