1405 - Desperate Electrician
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 352
Solved: 81
- Description
The Czech Technical University educates not only computer engineers, but also electricians, who may sometimes face challenging problems.
One electrician has been sent to a very high building to install new electrical wiring. Before starting his work, he needed to determine the state of the old wires. There were W wire endings on the ground floor and another W endings on the 42nd floor. The electrician knew for sure that each of the lower ends was connected to exactly one of the upper ends. However, there were no signs or marks, so he had no information about which of the wires is which.
The main trouble is that elevators are not working yet (because they are still not connected to the electricity). Therefore, we absolutely need to minimize the number of trips up and down.
The electrician has connectors able to connect an arbitrary number of wire endings together (on the same floor, of course). Then he can walk to the other end and measure which wires are connected. For example, if the electrician connects two wires only, it is easy to detect this pair at the other end. Unfortunately, it is impossible to distinguish between those 2 connected wires.
Your task is to write a program that determines the best way to mark all of the wires. It is allowed to connect any number of wires together and to have any number of connected groups (there are always enough connectors) simultaneously. The electrician may perform any number of measurements on each floor. At the end, the following conditions must be met:
Electrician is back on the ground floor.
All lower ends of the wires are marked with distinct numbers 1 to W .
All upper ends are marked with distinct numbers 1 to W.
Each wire has the same number on both ends.
- Input
The input consists of several test cases. Each test case is given as a single line with one integer W ,the number of wires, 1<= W <= 200. The input is terminated by a line containing zero.
- Output
For each test case, your program should output a single line with the sentence "Electrician needs X trips.", where X is the minimal possible number of times he has to climb up to the 42nd floor and descend back down.
If it is not possible to mark the wires at all, output the sentence "Bad luck!"instead.
- sample input
-
2 3 0
- sample output
-
Bad luck! Electrician needs 1 trips.
- hint
- source
- Central Europe Regional Contest 2007 - Practice Session