# Luogu UVA101 The Blocks Problem [simulation / linked list]

Input format

Output format

Meaning translation
Initially, there are from left to right n n n wooden blocks numbered 0 ... n − 1 0 \ldots n-1 0... n − 1, the following four operations are required:

• move a onto b: put the wood block above a and b in place, and then put a on b.
• move a over b: return the wood block above a, and then put a on the top of the pile of wood blocks where b is located.
• pile a onto b: put the wood blocks above b in place, and then lump the wood blocks above a onto b.
• pile a over b: lump the wood blocks of a and above onto b.
• The end flag of a group of data is quit. If there are illegal instructions (for example, a and b are in the same pile), it does not need to be processed.

Output: after all operations are input, the wood block number of each position is output from left to right and from bottom to top.

Sample input and output
Enter #1

```10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
```

Output #1

```0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:
```

### Solution simulation

The meaning of this topic is a little complicated, but it's not difficult to understand. If you write a function for each of the four operations and solve the problem violently, it is actually feasible. However, through observation, we abstract two common operations - homing and moving, and then implement four instructions. The code is as follows. pos[maxn][2] is used to record the current pile position of the wood block and the position of the wood block in the pile, which is convenient to find.

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
int n, a, b, pos[maxn][2]; //pos[i][0] records the stacking position of wood block I, and pos[i][1] records the position of wood block I in the stacking pos[i][0]
char act[5], how[5];
vector<int> blcs[maxn]; //blocks
void blocksReturn(int x) { //The homing function returns all the wood blocks above X in the pile where x is located to its original position
int blcPos = pos[x][0];
for (int i = blcs[blcPos].size() - 1; blcs[blcPos][i] != x; --i) { //The position of the wooden block x in the pile can be used here
int val = blcs[blcPos].back();
blcs[blcPos].pop_back();
pos[val][0] = val, pos[val][1] = blcs[val].size(); //Put it back in the original heap
blcs[val].push_back(val);
}
}
void putOn(int x, int y) { //Put X and the wood blocks above x (if any) in the pile where x is located on the pile where y is located as a whole
int xBlcPos = pos[x][0], yBlcPos = pos[y][0], xPos = pos[x][1]; //Query the heap position of x and the position of x in the heap
for (int i = xPos; i < blcs[xBlcPos].size(); ++i) {
int val = blcs[xBlcPos][i];
pos[val][0] = yBlcPos, pos[val][1] = blcs[yBlcPos].size();
blcs[yBlcPos].push_back(val); //Put it on the pile of wooden blocks where y is located
}
while (blcs[xBlcPos].size() > xPos) blcs[xBlcPos].pop_back(); //Really discard elements
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) { blcs[i].push_back(i); pos[i][0] = i, pos[i][1] = 0; }
while (~scanf("%s", act)) {
if (strcmp(act, "quit") == 0) break;
scanf("%d %s %d", &a, how, &b);
if (a == b || pos[a][0] == pos[b][0]) continue; //Illegal instruction
if (strcmp(act, "move") == 0) {
if (strcmp(how, "onto") == 0) { //move a onto b
blocksReturn(a), blocksReturn(b); //Put all the wood blocks above a and b in place
putOn(a, b); //At this time, both a and b are at the top of their respective wood blocks; Put a on b
} else { //move a over b
blocksReturn(a); //Put the wood block above a in place
putOn(a, b); //At this time, a is at the top of the pile of wood blocks; Put a on the top of the pile of wood blocks where b is located
}
} else if (strcmp(act, "pile") == 0) {
if (strcmp(how, "onto") == 0) { //pile a onto b
blocksReturn(b); //Put the wood block above b in place
putOn(a, b); //At this time b, it is at the top of the pile of wood blocks; Put a and the wood block above it on b
} else { //pile a over b
putOn(a, b); //Put the wood blocks above a on the top of the pile of wood blocks where b is located
}
}
}
for (int i = 0; i < n; ++i) {
printf("%d:", i);
for (int j = 0; j < blcs[i].size(); ++j) printf(" %d", blcs[i][j]);
printf("\n");
}
return 0;
}
```

At this time, the code can be AC:

However, there is room for further simplification. For example, when implementing the four instructions with homing and moving, it is found that the wood block above a must be homing when there is move, and the wood block above b must be homing when there is onto. Therefore, the simplified main() function is as follows, just like other codes:

```//......
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) { blcs[i].push_back(i); pos[i][0] = i, pos[i][1] = 0; }
while (~scanf("%s", act)) {
if (strcmp(act, "quit") == 0) break;
scanf("%d %s %d", &a, how, &b);
if (a == b || pos[a][0] == pos[b][0]) continue; //Illegal instruction
if (strcmp(act, "move") == 0) blocksReturn(a); //Put the wood block above a in place
if (strcmp(how, "onto") == 0) blocksReturn(b); //Put the wood block above b in place
putOn(a, b); //Put the wood blocks above a on the top of the pile of wood blocks where b is located
}
for (int i = 0; i < n; ++i) {
printf("%d:", i);
for (int j = 0; j < blcs[i].size(); ++j) printf(" %d", blcs[i][j]);
printf("\n");
}
return 0;
}
```

If you use a linked list (such as a static linked list), the efficiency of the putOn() function can be further improved. Whether you are handling a block or a pile of blocks, the time complexity can be achieved O ( 1 ) O(1) O(1) .