10192 - Vacation

[rafaelsilva]

I

[Wei-Ming Chen]

thank you

[angga888]

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

[Wei-Ming Chen]

Yes...you are right
I think I should change my method

[Shaka_RDR]

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

[beloni]

hello, your algo seems to be right...
so try to solve it in C instead Java

[Mushfiqur Rahman]

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

[Mushfiqur Rahman]

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

[nicky]

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

[Bluefin]

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

[justjoy]

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.

[Bluefin]

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

[farhan]

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

[Samiul]

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

[Farnak]

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

Thanks in advance.