## 10066 - The Twin Towers

Moderator: Board moderators

kier.guevara
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

### Re: 10066 - The Twin Towers

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
int n, m;
vector <int> twin_1;
vector <int> twin_2;
vector <int> numTiles;
int input, testC = 1;
while(cin >> n >> m )
{

if(m == 0 && n ==0)
break;

for(int i = 0; i < n; i++)
{
cin >> input;
twin_1.push_back(input);
}

for(int i = 0; i < m; i++)
{
cin >> input;
twin_2.push_back(input);
}

if(n < m)
{
swap(n, m);
swap(twin_1, twin_2);
}

for(int i = 0; i < n; i++)
{
int temp = 0;
int counter = 0;
int p = 0;

for(int k = i; k < n; k++)
{
p = temp;
for(; p < m; p++)
{
if(twin_1[k] == twin_2[p])
{
counter++;
p++;
temp = p;
break;
}
}
}

numTiles.push_back(counter);

}

swap(n, m);
swap(twin_1, twin_2);

for(int i = 0; i < n; i++)
{
int temp = 0;
int counter = 0;
int p = 0;

for(int k = i; k < n; k++)
{
p = temp;
for(; p < m; p++)
{
if(twin_1[k] == twin_2[p])
{
counter++;
p++;
temp = p;
break;
}
}
}

numTiles.push_back(counter);

}

int maxTiles = 0;
for(int i = 0; i < numTiles.size() - 1; i++)
{
numTiles[i+1] = max(numTiles[i], numTiles[i+1]);
}

cout << "Twin Towers #" << testC << endl << "Number of Tiles : " <<   numTiles[numTiles.size()-1]  << endl << endl;

twin_1.clear();
twin_2.clear();
testC++;
numTiles.clear();
}
return 0;
}
``````
Tried a lot test cases in uva toolkit and it matches mine but I still got WA..why?

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 10066 - The Twin Towers

@kier.guevara try this I/O

Code: Select all

``````100 100
1 2 3 4 5 6 5 4 8 5 4 5 4 5 8 6 5 4 8 4 5 6 8 5 1 2 3 1 5 1 4 5 6 5 8 5 2 1 4 5 5 6 4 5 6 5 8 5 4 5 1 2 3 4 5 6 5 4 8 5 4 5 4 5 8 6 5 4 8 4 5 6 8 5 1 2 3 1 5 1 4 5 6 5 8 5 2 1 4 5 5 6 4 5 6 5 8 5 4 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0
``````

Code: Select all

``````Ac code output is : 6123088
It is a sequence problem.
``````

Code: Select all

``enjoying life ..... ``

Testment
New poster
Posts: 3
Joined: Sun Nov 16, 2014 4:06 am

### Re: 10066 - The Twin Towers WA

isn't this a straight LCS !?
can any one help with my code

Code: Select all

``````#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>
#include <set>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <iomanip>
#include <complex>
#include <sstream>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <functional>
#include <bitset>
using namespace std;
//
#define lp(i, n)			for(int (i)=0;		(i)<(int)(n);	(i)++)
#define MAX 109
#define dex [i][j]
int DP[MAX][MAX];
int ST[MAX][MAX] = {0};
//
int mark = 0;
int n, m;
int *s1, *s2;
//
int doit(int i = 0, int j = 0)
{
if(i == n || j == m)
return 0;

if(ST dex == mark)
return DP dex;
ST dex = mark;

if(s1[i] == s2[j])
return DP dex = 1 + doit(i+1, j+1);

int c1 = doit(i+1, j);
int c2 = doit(i, j+1);
return DP dex = max(c1, c2);
}
//
int main()
{
while( scanf("%d %d", &n, &m) && !(n == 0 && m == 0) )
{
s1 = new int[n];
s2 = new int[m];
lp(i, n)
scanf("%d", &s1[i]);
lp(i, m)
scanf("%d", &s2[i]);
printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", ++mark, doit());
}
}
``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10066 - The Twin Towers

Your code doesn't match first case of sample. http://ideone.com/riv1Zf
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Testment
New poster
Posts: 3
Joined: Sun Nov 16, 2014 4:06 am

### Re: 10066 - The Twin Towers

lighted wrote:Your code doesn't match first case of sample. http://ideone.com/riv1Zf
that was really unfair
it was just a difference in compiling the printf() function
with this little edit it works fine with the judge

Code: Select all

``````mark++;
printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", mark, doit());``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10066 - The Twin Towers

http://stackoverflow.com/questions/1790 ... tions-in-c
Evaluation order of function parameters is not specified - it is left up to the implementation.
One reason to use the same compiler (g++) to test your code that the judge uses.
Check input and AC output for thousands of problems on uDebug!