10066 - The Twin Towers
Moderator: Board moderators
10066 - The Twin Towers
I think that i solve this probl em correctly.
I find the longest common subsequence. May be there any numbers that are longer than "long long int".
for example:
in:
2 3
1 2
2 3 4
out:
Twin Towers #1
Number of Tiles : 1
in2
1 2
1
2 3
out2:
Twin Towers #2
Number of Tiles : 0
Is there any error in my input/output.
Thank.
My program is here:
#include <stdio.h>
void nuluj(long long m,long long n, long long p[][101]) {
for (long i=0; i<=m; i++)
for (long j=0; j<=n; j++)
p[j]=0;
}
long long pole[101][101];
int main() {
long long z=0;
long long m,n;
long long a[101],b[101];
scanf("%lli %llin",&m,&n);
while (m!=0&&n!=0) {
z++;
for (long i=1; i<=m; i++) scanf("%lli",&a);
for (long k=1; k<=n; k++) scanf("%lli",&b[k]);
nuluj(m,n,&pole[0]);
for (long j=1; j<=m; j++) {
if (a[j]==b[1]) pole[1][j]=1;
}
for (long r=2; r<=n; r++)
for (long s=1; s<=m; s++) {
if (a[s]==b[r]) {pole[r][s]=pole[r-1][s-1]+1;}
else {
if (pole[r-1][s]>pole[r][s-1]) pole[r][s]=pole[r-1][s];
else
pole[r][s]=pole[r][s-1];
}
}
printf("Twin Towers #%llin",z);
printf("Number of Tiles : %llinn",pole[n][m]);
scanf("%lli %llin",&m,&n);
}
return 0;
}
I find the longest common subsequence. May be there any numbers that are longer than "long long int".
for example:
in:
2 3
1 2
2 3 4
out:
Twin Towers #1
Number of Tiles : 1
in2
1 2
1
2 3
out2:
Twin Towers #2
Number of Tiles : 0
Is there any error in my input/output.
Thank.
My program is here:
#include <stdio.h>
void nuluj(long long m,long long n, long long p[][101]) {
for (long i=0; i<=m; i++)
for (long j=0; j<=n; j++)
p[j]=0;
}
long long pole[101][101];
int main() {
long long z=0;
long long m,n;
long long a[101],b[101];
scanf("%lli %llin",&m,&n);
while (m!=0&&n!=0) {
z++;
for (long i=1; i<=m; i++) scanf("%lli",&a);
for (long k=1; k<=n; k++) scanf("%lli",&b[k]);
nuluj(m,n,&pole[0]);
for (long j=1; j<=m; j++) {
if (a[j]==b[1]) pole[1][j]=1;
}
for (long r=2; r<=n; r++)
for (long s=1; s<=m; s++) {
if (a[s]==b[r]) {pole[r][s]=pole[r-1][s-1]+1;}
else {
if (pole[r-1][s]>pole[r][s-1]) pole[r][s]=pole[r-1][s];
else
pole[r][s]=pole[r][s-1];
}
}
printf("Twin Towers #%llin",z);
printf("Number of Tiles : %llinn",pole[n][m]);
scanf("%lli %llin",&m,&n);
}
return 0;
}
Hi!
I couldn't find an error in your program...
Try to make only one dimensional array..
It is quite simple...
I have also tested it a lot but I found nothing...
Maybe you will try to write this task again??
Good Luck
Ps.
I have realized that after "0 0" your program is still waiting for the key...
Maybe this is the bug..
I couldn't find an error in your program...
Try to make only one dimensional array..
It is quite simple...
I have also tested it a lot but I found nothing...
Maybe you will try to write this task again??
Good Luck
Ps.
I have realized that after "0 0" your program is still waiting for the key...
Maybe this is the bug..
10066 Twin Towers, Problem statement wrong!
The problem states :
the Emperor ordered his architects to remove some of the tiles from the
two towers so that they have exactly the same shape and size,
and at the same time remain as high as possible.
So the towers should be as high as possible not necessirily containing
most number of tiles.
consider the input
5 5
10 10 10 10 500
500 10 10 10 10
the tallest tower is 500 high ( actually 500 x 2 ) but containg 1 tile
the tower containing most number of tile is 4 but 40 high.
so should the answer be 1 or 4 ?
the judge accepts 4.
the Emperor ordered his architects to remove some of the tiles from the
two towers so that they have exactly the same shape and size,
and at the same time remain as high as possible.
So the towers should be as high as possible not necessirily containing
most number of tiles.
consider the input
5 5
10 10 10 10 500
500 10 10 10 10
the tallest tower is 500 high ( actually 500 x 2 ) but containg 1 tile
the tower containing most number of tile is 4 but 40 high.
so should the answer be 1 or 4 ?
the judge accepts 4.
Read Question Carefully
Hi
The question says the tiles have the same heights and the input provides the radii of the tiles, not the heights !
Ustaad
The question says the tiles have the same heights and the input provides the radii of the tiles, not the heights !
Ustaad
10066 ?????? Why WA.
I'm using LCS here but it doesn't work. WHY??
[c]#include <stdio.h>
int main(void)
{
int common[101][101];
int a[101],b[101];
int i,j,m,n, counter = 0;
scanf("%d%d",&n,&m);
while((n > 0) || (m > 0))
{
++counter;
for (i = 0; i <= 100; ++i)
for (j = 0; j <= 100; ++j)
common[j] = 0;
for (i = 1; i <= n; ++i)
scanf("%d", &a);
for (i = 1; i <= m; ++i)
scanf("%d", &b);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
if (a == b[j])
common[j] = common[i-1][j-1] + 1;
else
if (common[i-1][j] > common[j-1])
common[j] = common[i-1][j];
else
common[j] = common[j-1];
printf("Twin Towers #%d\n",counter);
printf("Number of Tiles : %d\n",common[n][m]);
scanf("%d%d",&n,&m);
if (n)
printf("\n");
}
return(0);
}
[/c]
[c]#include <stdio.h>
int main(void)
{
int common[101][101];
int a[101],b[101];
int i,j,m,n, counter = 0;
scanf("%d%d",&n,&m);
while((n > 0) || (m > 0))
{
++counter;
for (i = 0; i <= 100; ++i)
for (j = 0; j <= 100; ++j)
common[j] = 0;
for (i = 1; i <= n; ++i)
scanf("%d", &a);
for (i = 1; i <= m; ++i)
scanf("%d", &b);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
if (a == b[j])
common[j] = common[i-1][j-1] + 1;
else
if (common[i-1][j] > common[j-1])
common[j] = common[i-1][j];
else
common[j] = common[j-1];
printf("Twin Towers #%d\n",counter);
printf("Number of Tiles : %d\n",common[n][m]);
scanf("%d%d",&n,&m);
if (n)
printf("\n");
}
return(0);
}
[/c]
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
10066 (twin towers) WA!
Hi!
I get WA in this problem over and over and over...
I don't know WHY!!
here is my code:
[c]
#include <stdio.h>
int lcs(int tn1[],int tn2[],int n1,int n2){
int i,j; /*counters*/
int x,t;
int lcs=0,temp=0;
for (t=1;t<=n1;t++){
x=1;
for (i=t;i<=n1;i++)
for (j=x;j<=n2;j++)
if (tn1==tn2[j]){
temp++;x=j+1;
break;
}
if (temp>lcs) lcs=temp;
temp=0;
}
printf("%d\n\n",lcs);
}
int main()
{
int n1,n2; /*towers*/
int i; /*counter*/
int tn1[101]; /*tiles of n1*/
int tn2[101]; /*tiles of n2*/
int cases=1;
while(scanf("%d %d",&n1,&n2)){
if (n1==0 && n2==0)
break;
for (i=1;i<=n1;i++)
scanf("%d",&tn1);
for (i=1;i<=n2;i++)
scanf("%d",&tn2);
printf("Twin Towers #%d\nNumber of Tiles : ",cases);
cases++;
lcs(tn1,tn2,n1,n2);
}
return 0;
}[/c]
Maybe I missunderstood the problem, or maybe there is some special cases that my code doesn't pass....
if someone could help I would appreciate very much
I get WA in this problem over and over and over...
I don't know WHY!!
here is my code:
[c]
#include <stdio.h>
int lcs(int tn1[],int tn2[],int n1,int n2){
int i,j; /*counters*/
int x,t;
int lcs=0,temp=0;
for (t=1;t<=n1;t++){
x=1;
for (i=t;i<=n1;i++)
for (j=x;j<=n2;j++)
if (tn1==tn2[j]){
temp++;x=j+1;
break;
}
if (temp>lcs) lcs=temp;
temp=0;
}
printf("%d\n\n",lcs);
}
int main()
{
int n1,n2; /*towers*/
int i; /*counter*/
int tn1[101]; /*tiles of n1*/
int tn2[101]; /*tiles of n2*/
int cases=1;
while(scanf("%d %d",&n1,&n2)){
if (n1==0 && n2==0)
break;
for (i=1;i<=n1;i++)
scanf("%d",&tn1);
for (i=1;i<=n2;i++)
scanf("%d",&tn2);
printf("Twin Towers #%d\nNumber of Tiles : ",cases);
cases++;
lcs(tn1,tn2,n1,n2);
}
return 0;
}[/c]
Maybe I missunderstood the problem, or maybe there is some special cases that my code doesn't pass....
if someone could help I would appreciate very much
lcs not right
You did not misunderstand the problem.. it is a LCS problem...
.. but your LCS function does not seem to be right. And from the look of your algorithm it seems to have a complexity of N^3.. but LCS can be implemented with N^2...
Here is the modified function which got AC.
[c]
int max(int a, int b) {
if( a < b)
return b;
return a;
}
int lcs(int tn1[],int tn2[],int n1,int n2){
int i,j; /*counters*/
int dp[101][101];
for(i=0;i<=n1;i++)
dp[0] = 0;
for(i=0;i<=n2;i++)
dp[0] = 0;
for(i=1;i<=n1;i++)
for(j=1;j<=n2;j++) {
if( tn1 == tn2[j] ) {
dp[j] = dp[i-1][j-1] + 1;
}
else dp[j] = max(dp[i-1][j], dp[j-1]);
}
printf("%d\n\n",dp[n1][n2]);
return 0;
}
[/c]
Hope it helps.
.. but your LCS function does not seem to be right. And from the look of your algorithm it seems to have a complexity of N^3.. but LCS can be implemented with N^2...
Here is the modified function which got AC.
[c]
int max(int a, int b) {
if( a < b)
return b;
return a;
}
int lcs(int tn1[],int tn2[],int n1,int n2){
int i,j; /*counters*/
int dp[101][101];
for(i=0;i<=n1;i++)
dp[0] = 0;
for(i=0;i<=n2;i++)
dp[0] = 0;
for(i=1;i<=n1;i++)
for(j=1;j<=n2;j++) {
if( tn1 == tn2[j] ) {
dp[j] = dp[i-1][j-1] + 1;
}
else dp[j] = max(dp[i-1][j], dp[j-1]);
}
printf("%d\n\n",dp[n1][n2]);
return 0;
}
[/c]
Hope it helps.
-
- New poster
- Posts: 15
- Joined: Sun Mar 07, 2004 7:47 pm
- Location: Moscow, Russia
10066 (Twin Towers) - Why WA??????
I used simple DP-based algorithm to find LCS. Everything seems to be OK, but I've got WA.
[pascal]
Type Integer = LongInt;
Const MaxN = 100;
Var A, B : Array[1..MaxN] Of Integer;
N, M : Integer;
D : Array[0..MaxN, 0..MaxN] Of Integer;
Function Load : Boolean;
Var I : Integer;
Begin
Load:=False;
Read(N, M);
If (N=0) And (M=0) Then Exit;
Load:=True;
For I:=1 To N Do Read(A);
For I:=1 To M Do Read(B);
End;
Function Max(A, B : Integer):Integer;
Begin
If A>B Then Max:=A Else Max:=B;
End;
Function Get(I, J : Integer):Integer;
Var Res : Integer;
Begin
If D[I, J]<0 Then Begin
If A=B[J] Then Res:=1+Get(I-1, J-1)
Else Res:=Max(Get(I-1, J), Get(I, J-1));
D[I, J]:=Res;
End;
Get:=D[I, J];
End;
Procedure Solve;
Var I, J : Integer;
Begin
For I:=0 To N Do
For J:=0 To M Do
D[I, J]:=-1;
For I:=0 To N Do D[I, 0]:=0;
For I:=0 To M Do D[0, I]:=0;
Get(N, M);
End;
Procedure Save(Iter : Integer);
Begin
Writeln('Twin Towers #', Iter);
Writeln('Number of Tiles = ', D[N, M]);
End;
Var Iter : Integer;
Begin
Iter:=0;
While Load Do Begin
Inc(Iter);
Solve;
Save(Iter);
Writeln;
End;
End.
[/pascal]
I know, that this algorithm could be implemented with classical DP, instead of recursive memorization, but I wan to know WHAT IS WRONG IN THIS CODE?
If anybody could help me?
[pascal]
Type Integer = LongInt;
Const MaxN = 100;
Var A, B : Array[1..MaxN] Of Integer;
N, M : Integer;
D : Array[0..MaxN, 0..MaxN] Of Integer;
Function Load : Boolean;
Var I : Integer;
Begin
Load:=False;
Read(N, M);
If (N=0) And (M=0) Then Exit;
Load:=True;
For I:=1 To N Do Read(A);
For I:=1 To M Do Read(B);
End;
Function Max(A, B : Integer):Integer;
Begin
If A>B Then Max:=A Else Max:=B;
End;
Function Get(I, J : Integer):Integer;
Var Res : Integer;
Begin
If D[I, J]<0 Then Begin
If A=B[J] Then Res:=1+Get(I-1, J-1)
Else Res:=Max(Get(I-1, J), Get(I, J-1));
D[I, J]:=Res;
End;
Get:=D[I, J];
End;
Procedure Solve;
Var I, J : Integer;
Begin
For I:=0 To N Do
For J:=0 To M Do
D[I, J]:=-1;
For I:=0 To N Do D[I, 0]:=0;
For I:=0 To M Do D[0, I]:=0;
Get(N, M);
End;
Procedure Save(Iter : Integer);
Begin
Writeln('Twin Towers #', Iter);
Writeln('Number of Tiles = ', D[N, M]);
End;
Var Iter : Integer;
Begin
Iter:=0;
While Load Do Begin
Inc(Iter);
Solve;
Save(Iter);
Writeln;
End;
End.
[/pascal]
I know, that this algorithm could be implemented with classical DP, instead of recursive memorization, but I wan to know WHAT IS WRONG IN THIS CODE?
If anybody could help me?
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- New poster
- Posts: 15
- Joined: Sun Mar 07, 2004 7:47 pm
- Location: Moscow, Russia
OK - I fixed the excess blank line in the end of my output file, by changing the main part for thislittle joey wrote:Carefully compare the output from your program with the sample output ... notice any difference?
[pascal]
Var Iter : Integer;
First : Boolean;
Begin
Iter:=0;
First:=True;
While Load Do Begin
If First Then First:=False Else Writeln;
Inc(Iter);
Solve;
Save(Iter);
End;
End.
[/pascal]
But still WA..
May be I am a bit of idiot - but I don't see any other difference..
-
- New poster
- Posts: 15
- Joined: Sun Mar 07, 2004 7:47 pm
- Location: Moscow, Russia