BagsQuiz
SRM 350 · 2007-05-23 · by Xixas
SRM 350 · 2007-05-23 · by Xixas · Graph Theory, Simulation, String Parsing
Problem Statement
Problem Statement
We have n bags numbered from 1 to n. Each bag can contain bags in its interior, which themselves can contain more bags. For the purposes of this problem, bag i is said to be inside bag j if and only if bag i is immediately contained in bag j. For example, if bag 1 contains bag 2, which contains bag 3, then bag 3 is inside bag 2, but it is not inside bag 1. All bags are initially empty and lying on the floor. We will perform a sequence of actions, each of which is one of the following types:
"PUT i INSIDE j" - Put bag i inside bag j. Both bag i and bag j must currently be on the floor for this action to be valid."SET i LOOSE" - Remove all the bags currently inside bag i and place them on the floor. Bag i must currently be on the floor for this action to be valid."SWAP i WITH j" - Swap the contents of bag i with the contents of bag j (i.e., take all the bags that are inside bag i and put them inside bag j, and vice versa). Both bag i and bag j must currently be on the floor for this action to be valid.The final configuration of bags is said to be proper if no bag lies inside a bag with a smaller number. Given n, the number of bags, and actions, the sequence of actions to perform on the bags, determine if the final configuration is proper. If so, return the number of bags that are on the floor in the final configuration. If it is not proper or if any of the actions are invalid, return -1 instead. See examples for further clarification.
Constraints
- n will be between 1 and 50, inclusive.
- actions will contain between 0 and 50 elements, inclusive.
- Each element of actions will be formatted as "PUT i INSIDE j" (where i and j are two distinct integers between 1 and n, inclusive, with no leading zeroes), "SET i LOOSE" (where i is an integer between 1 and n, inclusive, with no leading zeroes), or "SWAP i WITH j" (where i and j are two distinct integers between 1 and n, inclusive, with no leading zeroes). All quotes for clarity only.
Examples
0)
2
{"PUT 1 INSIDE 2"}
Returns: 1
Bag 1 is put inside bag 2 so only 1 bag remains on the floor.
1)
2
{"PUT 1 INSIDE 2", "SET 2 LOOSE"}
Returns: 2
No effect on the initial configuration.
2)
2
{"PUT 2 INSIDE 1"}
Returns: -1
This time the obtained configuration is improper since bag 2 lies inside a bag with a smaller number.
3)
4
{"PUT 3 INSIDE 2", "SWAP 4 WITH 2", "PUT 2 INSIDE 4", "SET 1 LOOSE"}
Returns: 2
4)
3
{"PUT 1 INSIDE 2", "PUT 3 INSIDE 1"}
Returns: -1
We can not perform the last command since the bag 1 is not on the floor.
67)
40
{"SET 9 LOOSE", "PUT 1 INSIDE 8", "PUT 5 INSIDE 11", "PUT 7 INSIDE 32", "PUT 6 INSIDE 22", "SET 15 LOOSE", "PUT 8 INSIDE 12", "PUT 4 INSIDE 19", "PUT 3 INSIDE 27", "SET 10 LOOSE", "PUT 9 INSIDE 34", "SET 8 LOOSE", "PUT 2 INSIDE 38", "SWAP 17 WITH 26"}
Returns: -1
"SET 8 LOOSE" is invalid.
82)
49
{"PUT 3 INSIDE 12", "PUT 1 INSIDE 5", "SWAP 35 WITH 14", "PUT 2 INSIDE 23", "PUT 6 INSIDE 14", "PUT 7 INSIDE 25", "PUT 20 INSIDE 49", "PUT 11 INSIDE 43", "SWAP 22 WITH 24", "PUT 4 INSIDE 9", "PUT 13 INSIDE 43", "PUT 15 INSIDE 49", "PUT 24 INSIDE 39", "SWAP 30 WITH 42", "PUT 23 INSIDE 26", "PUT 12 INSIDE 28", "PUT 5 INSIDE 22", "PUT 17 INSIDE 28", "SET 38 LOOSE", "PUT 8 INSIDE 10", "PUT 14 INSIDE 45", "PUT 22 INSIDE 30", "PUT 18 INSIDE 36", "PUT 9 INSIDE 40", "PUT 25 INSIDE 37", "PUT 10 INSIDE 37", "PUT 19 INSIDE 28", "PUT 16 INSIDE 43", "PUT 22 INSIDE 40"}
Returns: -1
Last action is invalid.
85)
41
{"SET 13 LOOSE", "PUT 12 INSIDE 22", "SET 19 LOOSE", "PUT 4 INSIDE 19", "PUT 17 INSIDE 15", "SET 39 LOOSE", "PUT 3 INSIDE 20", "SWAP 39 WITH 6", "PUT 19 INSIDE 25", "PUT 7 INSIDE 28", "PUT 5 INSIDE 13", "PUT 9 INSIDE 31", "SWAP 27 WITH 15", "PUT 20 INSIDE 25", "PUT 16 INSIDE 36", "SWAP 25 WITH 26", "PUT 2 INSIDE 18", "SWAP 6 WITH 37", "PUT 21 INSIDE 25", "PUT 13 INSIDE 31", "PUT 6 INSIDE 15", "PUT 1 INSIDE 11", "PUT 14 INSIDE 33", "PUT 15 INSIDE 33", "PUT 8 INSIDE 27", "PUT 18 INSIDE 29", "PUT 41 INSIDE 24", "PUT 11 INSIDE 10"}
Returns: -1
10 and 41 were changed.
86)
50
{"PUT 1 INSIDE 2", "PUT 2 INSIDE 3", "PUT 3 INSIDE 4", "PUT 4 INSIDE 5", "PUT 5 INSIDE 6", "PUT 6 INSIDE 7", "PUT 7 INSIDE 8", "PUT 8 INSIDE 9", "PUT 9 INSIDE 10", "PUT 10 INSIDE 11", "PUT 11 INSIDE 12", "PUT 12 INSIDE 13", "PUT 13 INSIDE 14", "PUT 14 INSIDE 15", "PUT 15 INSIDE 16", "PUT 16 INSIDE 17", "PUT 17 INSIDE 18", "PUT 18 INSIDE 19", "PUT 19 INSIDE 20", "PUT 20 INSIDE 21", "PUT 21 INSIDE 22", "PUT 22 INSIDE 23", "PUT 23 INSIDE 24", "PUT 24 INSIDE 25", "PUT 25 INSIDE 26", "PUT 26 INSIDE 27", "PUT 27 INSIDE 28", "PUT 28 INSIDE 29", "PUT 29 INSIDE 30", "PUT 30 INSIDE 31", "PUT 31 INSIDE 32", "PUT 32 INSIDE 33", "PUT 33 INSIDE 34", "PUT 34 INSIDE 35", "PUT 35 INSIDE 36", "PUT 36 INSIDE 37", "PUT 37 INSIDE 38", "PUT 38 INSIDE 39", "PUT 39 INSIDE 40", "PUT 40 INSIDE 41", "PUT 41 INSIDE 42", "PUT 42 INSIDE 43", "PUT 43 INSIDE 44", "PUT 44 INSIDE 45", "PUT 45 INSIDE 46", "PUT 46 INSIDE 47", "PUT 47 INSIDE 48", "PUT 48 INSIDE 49", "PUT 49 INSIDE 50"}
Returns: 1
A big chain of "PUT i INSIDE i+1".
Submissions are judged against all 106 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BagsQuiz with a public method int checkIfProper(int n, vector<string> actions) · 106 test cases · 2 s / 256 MB per case