OJ Board

Posted: **Sat Jun 12, 2004 11:13 am**

No............
I still got WA............................>.<
help

Posted: **Sat Jun 12, 2004 11:27 am**

howa wrote:No............
I still got WA............................>.<

So strange...

I have modified your program and submitted it.
It got AC.

This is the only change in your program:
[pascal]var
a,b:string;
cost:array[0..2000,0..2000] of longint;
i,j,k,n:longint;
begin
k:=0;
while not eof(input) do
begin
inc(k);
fillchar(cost,sizeof(cost),0);
readln(a);
if a='#' then exit;
readln(b);
...
end.[/pascal]

Posted: **Sat Jun 12, 2004 11:34 am**

Oh sorry~
I deleted the readln(b) carelessly ==;
Thanks~~~!

Posted: **Sat Jul 10, 2004 11:54 am**

if i put !cin.eof() in most outer while loop it will give me Time limit Exceed Error
and if i put ture in most outer while loop it will give me wrong answer please tell me whats the problem with my program.

Code: Select all

[cpp]
#include <iostream>

using namespace std;

int main (void)
{
	const short maxlength = 100;
	char text1[maxlength] = {'\0'};
	char text2[maxlength] = {'\0'};

	short check = 0;
	short stext1 = 0;
	short stext2 = 0;
	short countcase = 0;
	short j = 0;
	short i = 0;
	short visit1 = 0;
	short visit2 = 0;

	while(true)
	{
		countcase++;
		check++;
		cin.getline(text1, maxlength);

		if(text1[0] == 35)
			break;
		if(text1[0] == 35)
			break;		

		cin.getline(text2, maxlength);

		if(text2[0] == 35)
			break;
		if(text2[0] == 35)
			break;


		for(i = 0; text1[i] != '\0'; i++)
			stext1++;

		for(i = 0; text2[i] != '\0'; i++)
			stext2++;		

		j = 0;
		short i = 0;
		visit1 = 0;
		visit2 = 0;

		while(i != stext1 && j != stext2)
		{
			if(text1[i] == text2[j])
			{
				i++;
				j++;
				visit1++;
			}
			else if(j < stext1-1)
			{
				j++;
			}
			else if(i < stext2-1)
			{
				i++;
			}
		}
		
		j = 0;
		i = 0;

		while(i != stext1 && j != stext2)
		{
			if(text1[i] == text2[j])
			{
				i++;
				j++;
				visit2++;
			}
			else if(i < stext1-1)
			{
				i++;
			}
			else if(j < stext2-1)
			{
				j++;
			}
		}

		if(visit1 == 1 && visit2 == 1)
		{
			cout<<"Case #"<<countcase<<": you can visit at most "<<visit1<<" city."<<endl;
		}
		else if(visit1 >= visit2)
		{
			cout<<"Case #"<<countcase<<": you can visit at most "<<visit1<<" cities."<<endl;
		}
		else if(visit2 > visit1)
		{
			cout<<"Case #"<<countcase<<": you can visit at most "<<visit2<<" cities."<<endl;
		}

	}

	cout<<endl;

	return 0;
}
[/cpp]

Posted: **Sat Jul 24, 2004 5:25 am**

I use normal DP LCS algorithm and got AC

BTW you should output "cities" although the answer is 1.

Posted: **Tue Aug 03, 2004 6:58 am**

I am using the normal longest common subsequence algorithm for this problem but I am getting wrong answer. Can anybody tell me about some special input/output for this problem, for which my program may not be working ???

Posted: **Fri Feb 18, 2005 10:33 am**

I think the algorithm is ok, but I still get WA?!

Code: Select all


//Vacation( 10192 ACM )

#include <stdio.h>
#include <string.h>

#define MAX 101

char s1[MAX], s2[MAX];

int lcs()
{
	int i, j;
	int dp[MAX][MAX] = { 0 };
	int len1 = strlen( s1 ), len2 = strlen( s2 );
	
	for( i = 1; i <= len1; ++i )
		for( j = 1; j <= len2; ++j )
		{
			if( s1[i] == s2[j] ) dp[i][j] = dp[i-1][j-1] + 1;
			else if( dp[i-1][j] >= dp[i][j-1] ) dp[i][j] = dp[i-1][j];
			else dp[i][j] = dp[i][j-1];
		}
	return dp[len1][len2];
}

int main()
{
	int i = 0;
	while( gets( s1 ) && gets( s2 ) && ++i )
		printf( "Case #%d: you can visit at most %d cities.\n", i, lcs() );
		
	return 0;
}

Posted: **Fri Feb 18, 2005 2:07 pm**

You should do something like make sure s1 is not "#".. I think.. just in case..

Posted: **Fri May 20, 2005 9:22 pm**

First of all,

Input:
aaab
abaaa

Output:
Case #1: you can visit at most 3 cities.

Well the post of 'infancy' really puzzled me for a while and to get the output as 2 cities I modified normal LCS (Longest Common Subsequence) and removed any repeatation of cities. But the OJ gave WA.

Typical LCS algorithm stated in the CLRS book is enough to solve this problem.

Posted: **Tue Jul 05, 2005 8:11 pm**

10192 though i did dp solution but got TLE Help he please.my code is following. please say why i got TLE .

Code: Select all

#include <stdio.h>
#include <string.h>

#define SIZE 100

char X[SIZE],Y[SIZE];
int c[SIZE][SIZE];
int i,j,m,n;

int LCSlength() 
{
  m=strlen(X);
  n=strlen(Y);
  
  for (i=1;i<=m;i++)
	  c[i][0]=0;
  
  for (j=0;j<=n;j++)
	  c[0][j]=0;
	
  
  for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++) 
		{
			if (X[i-1]==Y[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];
			 
		}
	}
  return c[m][n];
}


int main() 
{
	int t_case=0;
	freopen("10192.txt","r",stdin);
	while (gets(X)!=NULL) 
	{
		t_case++;
		if(X[0]=='#')
			break;
		gets(Y);
		int len=LCSlength();
		printf("Case #%d: you can visit at most %d cities.",t_case,len); 
		printf("\n");
	}
	return 0;
}

Posted: **Tue Jul 05, 2005 8:41 pm**

10192 TLE : though i use DP solution i got TLE help PLZ. my code is following

Code: Select all

#include <stdio.h>
#include <string.h>

#define SIZE 100

char X[SIZE],Y[SIZE];
int c[SIZE][SIZE];
int i,j,m,n;

int LCSlength() 
{
  m=strlen(X);
  n=strlen(Y);
  
  for (i=1;i<=m;i++)
	  c[i][0]=0;
  
  for (j=0;j<=n;j++)
	  c[0][j]=0;
	
  
  for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++) 
		{
			if (X[i-1]==Y[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];
			 
		}
	}
  return c[m][n];
}


int main() 
{
	int t_case=0;
	freopen("10192.txt","r",stdin);
	while (gets(X)!=NULL) 
	{
		t_case++;
		if(X[0]=='#')
			break;
		gets(Y);
		int len=LCSlength();
		printf("Case #%d: you can visit at most %d cities.",t_case,len); 
		printf("\n");
	}
	return 0;
}

Posted: **Mon Jul 11, 2005 7:17 am**

Hi Thinker,
I cant understand why u use i,j,m,n variable as a global variable. I think u know clearly that how global variable initialize. This is the reason for ur TLE. Just cut those line and paste it in your LCS() function. Another thinks u will get RTE after modifying this. So also change the size. Use SIZE 1000 instead of SIZE 100. Good Luck

.

Posted: **Thu Jul 14, 2005 10:29 pm**

We are supposed to discuss problems of Voluem 3 here, not 101.

Posted: **Thu Jul 14, 2005 10:51 pm**

No need to make size 1000. I got AC using 105.

Posted: **Tue Aug 02, 2005 12:00 pm**

Hi thinker_bd

just increase your SIZE value and get ur AC

Thanks
MAP

OJ Board

10192 - Vacation

10192 vacations i got WA

WA in 10192

10192 WA problem

10192 TLE : though i did dp solution but got TLE Help please

10192 TLE : though i use DP solution i got TLE help PLZ

>>>>>