Czech Technical University in Prague

ACM ICPC sponsored by IBM

Central Europe Regional Contest 2007 - Practice Session

Desperate Electrician

electrician.c | electrician.C | electrician.java | electrician.p

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:

1. Electrician is back on the ground floor.

2. All lower ends of the wires are marked with distinct numbers 1 to W .

3. All upper ends are marked with distinct numbers 1 to W.

4. Each wire has the same number on both ends.

Input Specification

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 Specification

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

Output for Sample Input

Bad luck!

Electrician needs 1 trips.