UVa 101

From Algorithmist
Jump to navigation Jump to search


101 - The Blocks Problem[edit]

Summary[edit]

This is a simple Simulation problem. There should be more than enough time to pass.

Explanation[edit]

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.

Gotchas[edit]

  • Illegal commands are to be ignored:
    1. Those where a = b.
    2. 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.

Input[edit]

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

Output[edit]

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:

Solution[edit]