Ladice
레이팅 미적용의견: 0
\(5^{th}\) round, February \(15^{th}\), 2014
Authors: Luka Kalinovčić, Gustav Matula
Mirko has N items (labeled with numbers from 1 to N) and L drawers (labeled with numbers from 1 to
L). All items are currently scattered throughout his room, so he decided to clean them up. Each drawer
can contain one item, and in order to make it easier for Mirko to find them later, he has determined in
advance exactly two drawers (A_{i} and B_{i}) for each item i.
Mirko stores the items in order from 1 to N using the first rule he can apply:
1. If the drawer A_{i} is empty, he stores the item i in that drawer
2. If the drawer B_{i} is empty, he stores the item i in that drawer
3. Try to move the item from A_{i} to its other drawer; if that one's filled too, try moving that item to
its other drawer, and so on until you either succeed or get back to a previously seen drawer. In
case of success, store the item i in the drawer A_{i}. In case of failure, continue to next rule.
4. Try moving the item from B_{i} to its other drawer; if that one's filled too, try moving that item to
its other drawer, and so on until you either succeed or get back to a previously seen drawer. In
case of success, store the item i in the drawer B_{i}. In case of failure, continue to next rule.
5. Give up and throw away the item i.
For given pairs of drawers for each item, determine which items will be stored and which will be
thrown away.
In test cases worth 50% of total points, both N and L will be lesser than 2000.
The first line of input consists of two integers, N and L (\(1 \le N\), \(L \le 300\,000\)), the number of items
and the number of drawers.
Each of the following N lines contains two integers: A_{i} and B_{i} (\(1 \le A_{i}\) and \(B_{i} \le L\)), pair of drawers
corresponding to the item i. The numbers A_{i} and B_{i} will be different.
For each item, respectively, output where it ends up.
In case the item is stored successfully, output "LADICA" (without quotes, Croatian word for drawer).
In case the item is thrown away, output "SMECE" (without quotes, Croatian word for trash).
\(5^{th}\) round, February \(15^{th}\), 2014
Authors: Luka Kalinovčić, Gustav Matula
5 3
1 2
1 3
1 2
1 3
1 2LADICA
LADICA
LADICA
SMECE
SMECE9 10
1 2
3 4
5 6
7 8
9 10
2 3
1 5
8 2
7 9LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICAClarification of the first example: The first item goes to drawer 1 by rule 1). The second item goes to
drawer 3 by rule 2). The third item goes to drawer 2 by rule 2).
For the fourth and fifth item, both drawers are already taken and cannot be emptied.
Clarification of the second example: The first six items go into drawers 1, 3, 5, 7, 9, 2 (respectively),
by rule 1). For the seventh item, applying the rule 3), we try to move the item in drawer 1 to drawer 2,
the item in drawer 2 to drawer 3, the item in drawer 3 to drawer 4, which we succeed because the
drawer is empty.
The eighth item goes to drawer 8 which was empty from the beginning.
For the ninth item, applying the rule 3), we try to move the item in drawer 7 to drawer 8, the item in
drawer 8 to drawer 2, the item in drawer 2 to drawer 1, the item in drawer 1 to drawer 5, the item in
drawer 5 to drawer 6, which we succeed because the drawer is empty.
평가 및 의견
Ladice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ladice