A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

Pages: **1**

**ankit.ag2010****Guest**

WATER OF HEAVEN

Frustrated with the affair of Jasmine and Alladin, Jafar (the vizier to the sultan), somehow managed to send Alladin and his group into the 'Cave of Death'. Misfortune follows when Jasmine looks into the Mirror of Hell (a type of magical object) and turns into stone. Frightened, Alladin rubs his lamp to call genie who told him the following solution:

"At a place which is 'T' time units from here, there is a magical Golden Tap from which Water of Heaven flows. If you somehow manage to drench the Jasmine with V units (exactly V units not more not less) of it, she can turn back to normal. To help you, there will be few magical glasses of different or same volume (two or more may be of same volume). You may use them to bring water .The time required to fill one glass of V volume is F time units (where F may be different for different volume of glass which will be given as input) and time is consumed even when you are pouring water from one glass to another. This time is equal to the time required to fill the glass you are pouring into (F value of the glass in which water is being poured), irrespective of the volume being poured. You can take only one glass from there in one trip (as Lago, Abu and magical carpet denied to do any work) and you may make any number of trips (each trip will take 2*T time units)."

Your task is to find the glasses used, along with the number of times they are used (number of times means number of times

- 1 -

water is poured inside it either from the tap or by another glass) such that Alladin and his group can save Jasmine in minimum time.

Following are the assumptions to be taken

1. Time other than filling glass and moving from the tap to Jasmine is negligible.

2. If you have to make another trip, you have to bring back the glass so that it may be used again.

3. In case of clash (if time is same for two or more solution), solution using less glass should be printed and if again clashes then all are considered correct.

4. All the glasses are unmarked.

Input :

Format of input file (all input will be of integer type)

Number of test case (0 < test cases <= 100) (followed by a blank line)

Value of V (0 < V <= 100)

Value of T (0 <= T <= 1000000)

Number of magical glass n (0 <= n < 100)

Volume of the glasses as V1 V2 V3 ........ Vn ( 0 < V <= 1000000)

Value of F for each glass in same order F1 F2 F3 .........Fn (0 < F <= 1000000)

(a blank line and next case and so on….)

Output :

Case number

TRIP 1

Index of glass used in first trip (in ascending order of index) - number of time it is used.

- 2 -

TRIP 2 (and so on…)

(a blank line and next case and so on…)

Test Cases :

Input file :

2

3

1

4

1 2 3 4

1 8 10 15

8

1000

3

6 6 11

1 1 2

Output file :

case 1

TRIP 1

1 1

TRIP 2

1 1

TRIP 3

1 1

case 2

TRIP 1

1 3

2 3

3 6

- 3 -

Pages: **1**