UVa 10066 – The Twin Towers
A long time ago, in the ancient kingdom of Teacher Wang, there stood two towers of different shapes in two different cities. These towers were built using circular tiles stacked on top of each other. Each tile had the same height and an integer radius. Therefore, although the two towers had different shapes, they shared many identical tiles.
However, a thousand years after the towers were built, the king ordered the architects to remove certain tiles so that the two towers would become identical in shape and size while maintaining the maximum possible height. The tiles had to remain in the same order as in the original construction. The king believed that this would symbolize harmony and equality between the two cities. He named it the "Twin Star Towers."
Now, nearly two thousand years later, you've been given a simpler task: given the descriptions of the two towers, your job is to find the maximum possible number of identical tiles.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| For each test case, input is received via EOF. Each test case represents a pair of twin towers.
The first line of each test case contains two integers, N1 and N2 (1 ≤ N1, N2 ≤ 100), representing the number of tiles in the two towers. The next line contains N1 positive integers, representing the radii of the tiles in the first tower from top to bottom. The line after that contains N2 integers representing the radii of the tiles in the second tower from top to bottom. The input ends when N1 and N2 are both 0. Your task is to compute the maximum possible number of identical tiles that can remain in both towers while maintaining the original order. | For each pair of twin towers, output the case number and the maximum possible number of identical tiles that can be retained in both towers while preserving the original order of tiles. Leave a blank line between the outputs for different test cases. |
| 7 6 20 15 10 15 25 20 15 15 25 10 20 15 20 8 9 10 20 20 10 20 10 20 10 20 10 20 10 10 20 10 10 20 0 0 | Twin Towers #1 Number of Tiles : 4 Twin Towers #2 Number of Tiles : 6 |
Thought Process
Declare a two-dimensional array and run a loop for N1 * N2. If N1[i] == N2[j], you need to check whether any value is the first (i.e., i == 0 or j == 0). If either i or j is 0, set array[i][j] to 1. Otherwise, set array[i][j] to array[i-1][j-1] + 1. This will ensure you’re tracking the longest common subsequence between the two towers while respecting their order.
To handle cases where N1[i] != N2[j], you need to check several conditions:
1. If both i and j are 0: Set array[i][j] to 0.
2. If either i == 0 or j == 0: Set array[i][j] to array[i-1][j] or array[i][j-1] respectively.
3. If neither i nor j is 0 and N1[i] != N2[j]: Set array[i][j] to the maximum value between array[i-1][j] and array[i][j-1].
The final answer is the value in array[N1-1][N2-1].
Sample Code－ZeroJudge A133: The Twin Towers
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M, towers = 1;
while (cin >> N >> M && N != 0 && M != 0) {
if (towers != 1) cout << "\n";
int N1[200] = {}, N2[200] = {}, DP[200][200] = {};
for (int i = 0; i < N; i++) {
cin >> N1[i];
}
for (int i = 0; i < M; i++) {
cin >> N2[i];
}
for (int i = 0; i<N; i++) {
for (int j = 0; j<M; j++) {
if (N1[i] == N2[j]) {
if (i-1 >= 0 && j-1 >= 0) {
DP[i][j] = DP[i-1][j-1] + 1;
}
else {
DP[i][j] = 1;
}
}
else {
if (i-1 >= 0 && j-1 >= 0) {
DP[i][j] = max(DP[i][j-1], DP[i-1][j]);
}
else if (i-1 >= 0) {
DP[i][j] = DP[i-1][j];
}
else if (j-1 >= 0) {
DP[i][j] = DP[i][j-1];
}
else {
DP[i][j] = 0;
}
}
}
}
cout << "Twin Towers #" << towers << "\n" << "Number of Tiles : " << DP[N-1][M-1] << "\n";
towers++;
}
}
//ZeroJudge A133
//Dr. SeanXD