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) .