Page 3 of 4

### 10192 Vacation Problem - Wrong Answer

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

### 10192......OLE!!!!

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

Posted: Mon Nov 14, 2005 7:06 am
Yes...you are right
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

Posted: Fri Jun 30, 2006 7:52 pm
hello, your algo seems to be right...
so try to solve it in C instead Java

### Anybody Help PLZ about 10192

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:

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

### 10192 WA help!

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 !!

Posted: Mon Aug 28, 2006 1:46 pm
My source code.
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++;
}
}

``````
Thank you.

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 !!

### 10192 - CE

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;
}

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.

### 10192 - Vacation

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?

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;
}
``````