### 10192 Vacation Problem - Wrong Answer

Posted:

**Sun Sep 18, 2005 8:43 pm**I

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=10&t=26354

Page **3** of **4**

Posted: **Sun Sep 18, 2005 8:43 pm**

I

Posted: **Sun Nov 13, 2005 3:32 pm**

thank you

Posted: **Sun Nov 13, 2005 6:06 pm**

I think that you should change your input reading method. You can read one line using gets(). I have changed your code using gets() and it was not OLE anymore.

Hope it helps

Hope it helps

Posted: **Mon Nov 14, 2005 7:06 am**

Yes...you are right

I think I should change my method

I think I should change my method

Posted: **Wed May 10, 2006 7:28 am**

I have the same problem here...

can any body give me another sample I/O ?

just feeling depressed from getting 6 WAs in a row , after 2 years idle from UVA

can any body give me another sample I/O ?

just feeling depressed from getting 6 WAs in a row , after 2 years idle from UVA

Posted: **Fri Jun 30, 2006 7:52 pm**

hello, your algo seems to be right...

so try to solve it in C instead Java

so try to solve it in C instead Java

Posted: **Fri Jul 28, 2006 9:23 pm**

I am also getting WA for this problem, but i think my algo and code is OK.

I also checked my code for some I/O. It gives me correct output.

Then wheres the worng.

Here my code:

I also checked my code for some I/O. It gives me correct output.

Then wheres the worng.

Here my code:

Code: Select all

```
Removed after got AC
```

Posted: **Sat Jul 29, 2006 7:06 pm**

Yes Lastly I got AC. The wrong was that in my while loop . I should use gets() rather than scanf() in while and then check the first string which will contain "#" string

Thanks for every body.

Mushfiqur Rahman

Thanks for every body.

Mushfiqur Rahman

Posted: **Fri Aug 18, 2006 10:33 am**

I think my algorithm is correct but get WA! I check many times but cant find where the problem is. I will be very grateful if any suggestion.

Code: Select all

```
#include <cstdlib>
#include <stdio.h>
#include <iostream>
#include <string>
#define MAXCITY 102
using namespace std;
int c[MAXCITY][MAXCITY];
char s1[MAXCITY], s2[MAXCITY];
void LCS(int time){
int m = strlen(s1);
int n = strlen(s2);
int i, j;
for(i=0; i<MAXCITY; i++)
for(j=0; j<MAXCITY; j++)
c[i][j] = 0;
for(i=0; i<m; i++){
for(j=0; j<n; j++){
if(s1[i] == s2[j]) c[i][j] = c[i-1][j-1]+1;
else c[i][j] = (c[i][j-1]>c[i-1][j])? c[i][j-1] : c[i-1][j];
}
}
cout << "Case #" << time << " : you can visit at most " << c[m-1][n-1] << " cities." << endl;
}
int main(int argc, char *argv[])
{
int time;
for(time=1; ; time++){
gets(s1);
if(!(strcmp(s1, "#"))) return 0;
gets(s2);
LCS(time);
}
return EXIT_SUCCESS;
}
```

Posted: **Fri Aug 18, 2006 1:43 pm**

I think you can simply solve Q10192 bu using LCS algorithm ~~

There's no trick in this problem.

Check your code one more time ~~

If you still can't find the error, send PM to me and I'll send my ACC code to you !!

But I think there isn't much difference between our codes ~~

Hope it will help !!

There's no trick in this problem.

Check your code one more time ~~

If you still can't find the error, send PM to me and I'll send my ACC code to you !!

But I think there isn't much difference between our codes ~~

Hope it will help !!

Posted: **Mon Aug 28, 2006 1:46 pm**

My source code.

I was solve this problem with Dynamic Algorithm

Thank you.

I was solve this problem with Dynamic Algorithm

Code: Select all

```
#include<stdio.h>
#include<string.h>
void main(){
char a[1001];
char b[1001];
int tb[1001][1001]={0,};
int alen, blen;
int i, j;
char dap[101]={0,};
int cnt;
int t=1;
while(1){
gets(a);
if(a[0] == '#')
break;
gets(b);
alen = strlen(a);
blen = strlen(b);
for(i=alen;i>=0;i--)
a[i] = a[i-1];
for(i=blen;i>=0;i--)
b[i] = b[i-1];
for(i=1;i<=alen;i++){
for(j=1;j<=blen;j++){
if(a[i] == b[j]){
tb[i][j] = tb[i-1][j-1]+1;
}
else{
tb[i][j] = tb[i-1][j-1];
if(tb[i][j] < tb[i][j-1])
tb[i][j] = tb[i][j-1];
if(tb[i][j] < tb[i-1][j])
tb[i][j] = tb[i-1][j];
}
}
}
cnt = tb[alen][blen];
printf("Case #%d: you can visit at most %d cities.\n",t,cnt);
t++;
}
}
```

Posted: **Tue Aug 29, 2006 8:04 am**

I think it's better not to post your code ~~

Because that way anyone can get ACC immediately by posting your code.

That's not fair !!

So please delete it ~~

Because that way anyone can get ACC immediately by posting your code.

That's not fair !!

So please delete it ~~

Posted: **Sun Dec 16, 2007 1:50 pm**

Can anyone tell why CE in this prog?

#include<stdio.h>

#include<string.h>

char str1[100], str2[100];

int test_case = 1;

int m, n;

int i, j;

int c[110][110];

void LCScount()

{

m = strlen(str1);

n = strlen(str2);

for(i=0; i<=m; ++i)

c[i][0] = 0;

for(i=0; i<=n; ++i)

c[0][i] = 0;

for(i=1; i<=m; ++i)

{

for(j=1; j<=n; ++j)

{

if( str1[i-1] == str2[j-1] )

{

c[i][j] = c[i-1][j-1] + 1;

}

else if( c[i-1][j] >= c[i][j-1] )

{

c[i][j] = c[i-1][j];

}

else

{

c[i][j] = c[i][j-1];

}

}

}

printf("Case #%d: you can visit at most %d cities.\n", test_case++, c[m][n]);

}

int main()

{

//freopen("in.txt", "r" ,stdin);

while(1)

{

scanf("%s %s", str1, str2);

if( !( strcmp (str1,"#") ) )

return;

LCScount();

//printf("%s\n",str1);

}

return 0;

}

#include<stdio.h>

#include<string.h>

char str1[100], str2[100];

int test_case = 1;

int m, n;

int i, j;

int c[110][110];

void LCScount()

{

m = strlen(str1);

n = strlen(str2);

for(i=0; i<=m; ++i)

c[i][0] = 0;

for(i=0; i<=n; ++i)

c[0][i] = 0;

for(i=1; i<=m; ++i)

{

for(j=1; j<=n; ++j)

{

if( str1[i-1] == str2[j-1] )

{

c[i][j] = c[i-1][j-1] + 1;

}

else if( c[i-1][j] >= c[i][j-1] )

{

c[i][j] = c[i-1][j];

}

else

{

c[i][j] = c[i][j-1];

}

}

}

printf("Case #%d: you can visit at most %d cities.\n", test_case++, c[m][n]);

}

int main()

{

//freopen("in.txt", "r" ,stdin);

while(1)

{

scanf("%s %s", str1, str2);

if( !( strcmp (str1,"#") ) )

return;

LCScount();

//printf("%s\n",str1);

}

return 0;

}

Posted: **Tue Dec 25, 2007 8:47 am**

In int main() you have two returns, among which one is not returning anything. This gave compile error in my compiler VS 2005.

Posted: **Wed Feb 06, 2008 5:29 am**

Sorry, I've looked at the old topics for this problem and read the code in those topics but I still don't understand why my code repeatedly gets me WA. I'm just using the standard LCS algorithm. Could someone please help me?

Thanks in advance.

Code: Select all

```
#include <stdio.h>
#include <string.h>
#define SIZE 110
#define MAX(a, b) (a > b ? a : b)
static long best[SIZE][SIZE];
static char line1[SIZE], line2[SIZE];
static int len1, len2;
static int i, j;
static int num;
int main (){
gets (line1);
num = 0;
while (strcmp (line1, "#") != 0){
gets (line2);
num++;
len1 = strlen (line1);
len2 = strlen (line2);
for (i = 0; i < len1 + 1; i++)
best[i][0] = 0;
for (j = 0; j < len2 + 1; j++)
best[0][j] = 0;
for (i = 1; i < len1 + 1; i++)
for (j = 1; j < len2 + 1; j++)
if (line1[i] == line2[j])
best[i][j] = best[i - 1][j - 1] + 1;
else
best[i][j] = MAX(best[i - 1][j], best[i][j - 1]);
printf ("Case #%d: you can visit at most %ld cities.\n", num, best[len1][len2]);
gets (line1);
}
return 0;
}
```