All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The following is an easy game that the setter of this problem played when he was 8:
A boatman, a wolf, a sheep, and a cabbage are on the bank of a river. They have a small boat that is capable of carrying the boatman and at most one other animal/item with him. However, if left alone by the boatman, the wolf can eat the sheep, and the sheep can eat the cabbage. How can all four be moved safely to the opposite bank of the river?
Here is a nice visualization of the whole process in the original game. Disclaimer: writers, testers and CodeChef are not related to this link.
This leads to a more general problem. If there are other groups of animals/items with the boatman, and if the boat is big enough to seat at most K animals/items other than the boatman, how quickly can all of them be moved to the opposite bank of the river in such a way that nobody/nothing gets eaten?
We will give you the number of animals/items (not including the boatman). We will also give you the new capacity of the boat. Moreover, we will give you all a list of pairs of the form "X Y" where the X-th animal/item will be eaten by the Y-th one if they are both on the opposite bank to the boatman.
Assuming a valid solution exists, you are to determine the minimum number of boat trips across the river to achieve the task.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test contains three space separated integers N, M and K - the number of animals/items not including the boatman, the number of relations of the form "X will be eaten by Y", and the capacity of the boat (not including the boatman), respectively.
The following M lines contain pairs of the form X Y with the meaning that the X-th animal/item will be eaten by the Y-th one if they are both on the opposite bank to the boatman.
For each test case, output a single line containing a single integer - the minimum number of boat trips across the river necessary. In the test cases it is always possible to accomplish this goal.
- 1 ≤ T ≤ 20
- 1 ≤ K ≤ N
- Subtask 1: 1 ≤ N ≤ 3, 0 ≤ M ≤ 3 - 22 points.
- Subtask 2: 1 ≤ N ≤ 6, 0 ≤ M ≤ 15 - 34 points.
- Subtask 3: 1 ≤ N ≤ 13, 0 ≤ M ≤ 78 - 44 points.
Input: 2 3 2 1 1 2 2 3 3 3 2 1 2 1 3 2 3 Output: 7 3
The first example is the original version of the problem.
|Tags||bfs, easy, ltime18, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.