UVa 101
From Algorithmist
Contents |
[edit] 101 - The Blocks Problem
[edit] Summary
This is a simple Simulation problem. There should be more than enough time to pass.
[edit] Explanation
Things to think about include deciding what data structure to use and how to find where each block is. Since the main operations are deletion, insertion, and splicing, linked lists are a good choice. You can also use a lookup table for keeping track of where each block is, as long as you update it for each operation.
In this problem using modularity really helps; create a function for each of the different move/pile operations and one other for printing. This way you can make sure each of the individual operations is done correctly instead of trying to find a bug amongst your whole program.
[edit] Gotchas
- Illegal commands are to be ignored:
- Those where a = b.
- Those with a and b in the same stack.
- The problem statement is incorrect - to avoid Presentation Error, there is no space before the single-digit numbers: check the below output.
[edit] Input
21 move 2 onto 1 move 3 onto 2 move 4 onto 3 move 5 over 1 pile 1 over 10 move 9 over 8 move 11 over 8 pile 3 over 8 pile 8 over 3 move 20 over 19 pile 19 over 18 pile 18 onto 15 move 15 over 3 pile 20 onto 19 pile 19 onto 18 pile 18 over 17 quit
[edit] Output
0: 0 1: 2: 3: 4: 5: 6: 6 7: 7 8: 8 9 11 3 4 5 15 9: 10: 10 1 2 11: 12: 12 13: 13 14: 14 15: 16: 16 17: 17 18 19 20 18: 19: 20:
