E |
Frequency Hopping |
|
Input: Standard Input Output: Standard Output |
|
20th
July, 1942 Colonel Al Pacheno, According to the previous order “ref: 232/UK44i/334sda#nh$X3y”,
you are required back in the DOI (Department of intelligence, Level 3 Secrecy must be maintained. Sincerely, General
Shaan Konary Director,
DOI Ps: Sorry to
ruin your |
232/UK44i/334sda#nh$X3y/Appx-301a
At
this moment, through out
--End
of Attachment
As members of Secret Programmers Group (SPG) you are assigned to solve this problem within 5 hrs and deliver the solution directly to Colonel Al Pacheno. You have to maintain Level 3 secrecy and destroy all documents corresponding to this as soon as you deliver the solution.
Input:
There will be multiple test cases. The first line of each test case contains three numbers N, E and C where N (0<N<101) represents the number of base stations, E (E<10000) represents the number of available connections between the base stations and C (C<2000000000) represents the number of secret message fragments that are required to send from station 1 to station N. After that, there will be E lines. Each line contains 3 numbers: b1(0<b1<101), b2(0<b2<101) and fp (0<fp<5001) which represent the number of frequency channels available currently from b1 to b2. Input is terminated when N=E=C=0.
Output:
For each test case, there will be one line of output. First, you have to print the case number. If it is possible to send C secret message fragments from the current status the output will be “possible”. Otherwise, you have to print all pairs of stations (in ascending order) if it is possible send the required message fragments by increasing the frequency channel between any one of them. If it is still impossible, you have to print “not possible”.
4 4 5 1 2 5 1 3 5 2 4 5 3 4 5 4 4 5 1 2 1 1 3 5 2 4 5 3 4 1 4 4 5 1 2 1 1 3 1 2 4 1 3 4 1 0 0 0 |
Case 1: possible Case 2: possible option:(1,2),(3,4) Case 3: not possible |
Problemsetter: Syed Monowar Hossain
Special Thanks: Abdullah al Mahmud