10100 - Longest Match

[Julien Cornebise]

Hi hi.
We were writing our postings at the same time! Julien and I said exactly the same thing.

[the LA-Z-BOy]

Output for your input:

Code: Select all

 1. Length of longest match: 2
 2. Blank!
 3. Length of longest match: 0
 4. Length of longest match: 0
 5. Length of longest match: 0

[shamim(aiub)]

i got WA.
plz anybody tell me the output for
input:
---------------------------
this is a test
this is is a a test
76.67 67
67 67 76
---------------------------[/img]

[alu_mathics]

1. Length of longest match: 4
2. Length of longest match: 2

[mlvahe]

Can anybody do a favour telling me where I am mistaken.
Whatever I do I get WA.
[cpp]
#include <iostream.h>
#include <iomanip.h>
#include <string.h>

bool chr(const char c)
{
return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

main()
{
long m,n,s,c[120][120],i,j,lng1,lng2;

char x[101][31],y[101][31], tmp[1010], strtmp[50];
s = 1;
while (cin.getline(tmp+1,1002,'\n'))
{
for (i = 0; i < 101; i++)
{
x[0] = '\0';
x[1] = '\0';
y[0] = '\0';
y[1] = '\0';
}
c[0][0] = 0;
m = 0;
tmp[0] = 0;
lng1=strlen(tmp+1);
for (i = 1; tmp; i++)
if (chr(tmp) && chr(tmp[i-1]))
{
strtmp[0] = tmp;
strtmp[1] = '\0';
strcat(x[m],strtmp);
}

else
if (chr(tmp))
{
m = m + 1;
x[m][0] = tmp;
x[m][1] = '\0';
}
n = 0;
c[m][0] = 0;
cin.getline(tmp+1,1002,'\n');
lng2= strlen(tmp+1);
tmp[0]=0;
for (i = 1; tmp; i++)
if (chr(tmp[i]) && chr(tmp[i-1]))
{
strtmp[0] = tmp[i];
strtmp[1] = '\0';
strcat(y[n],strtmp);
}
else
if (chr(tmp[i]))
{
n = n + 1;
y[n][0] = tmp[i];
y[n][1] = '\0';
}
for (i = 0; i <= n; i++)
c[0][i] = 0;
for (i = 0; i <= m; i++)
c[i][0] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
if (strcmp(x[i],y[j]) == 0)
{
c[i][j] = c[i-1][j-1] + 1;
}
else
if (c[i][j-1] > c[i-1][j])
{
c[i][j] = c[i][j-1];
}
else
{
c[i][j] = c[i-1][j];
}
}
if (lng1 + lng2 == 0)
break;
cout << setiosflags(ios::right) << setw(2) << s;
if (lng1*lng2 == 0)
cout << ". Blank!" << endl;
else
cout << ". Length of longest match: " << c[m][n] << endl;
s++;
}

return 0;
}

[/cpp]
[/pascal]

[sohel]

By giving a quick glace I found two minor mistakes:

1) you can not ignore digits.
eg

12 12
12 12

Output should be 2

2) there can be two blanks in one case
output for two blanks should be blank but your program terminates if given this input.

[mlvahe]

Dear sohel
Thank you very much.
I finally got AC.

[udcp]

My code gives the output for the following inputs as..

12 12
12 12
1. Length of longest match: 2
this is a test
this is is a a test
2. Length of longest match: 4
76.67 67
67 67 76
3. Length of longest match: 2
(\n)
(\n)
4. Blank!
(\n)
asd
5. Blank!
(\n)
(space)
6. Blank!
(space)
(space)
7. Length of longest match: 0
a s d c f
a d c
8. Length of longest match: 3
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
9. Length of longest match: 11
a s d
r t g
10. Length of longest match: 0
.;.;[
.;.;[
11. Length of longest match: 0

I feel I have considered all cases... Also the case number is right justified in a field width of two.. Am I overlooking something????????
Hope I get a reply........... Thanks in advance...

[udcp]

My code gives the output for the following inputs as..

12 12
12 12
1. Length of longest match: 2
this is a test
this is is a a test
2. Length of longest match: 4
76.67 67
67 67 76
3. Length of longest match: 2
(\n)
(\n)
4. Blank!
(\n)
asd
5. Blank!
(\n)
(space)
6. Blank!
(space)
(space)
7. Length of longest match: 0
a s d c f
a d c
8. Length of longest match: 3
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
9. Length of longest match: 11
a s d
r t g
10. Length of longest match: 0
.;.;[
.;.;[
11. Length of longest match: 0

I feel I have considered all cases... Also the case number is right justified in a field width of two.. Am I overlooking something????????
Hope I get a reply........... Thanks in advance...

[howardcheng]

I went through all the suggestions in the forum (blank line interpretations, non-letter = non-alphanumeric, etc), and I still get WA. Are there any more tricks to this?

[angga888]

My code gives the output for the following inputs as..

You're outputs are exactly the same as mine.


Anggakusuma

[ec3_limz]

Can anyone tell me what's wrong with this (I got Runtime Error SIGSEGV)

[cpp]
// ACM #10100: Longest Match

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

#define MAXLLEN 1000
#define MAXWLEN 20
#define MAXNW 55

#define MAX(A,B) ((A)>(B)?(A):(B))

char line[MAXLLEN+1],w1[MAXNW+1][MAXWLEN+1],w2[MAXNW+1][MAXWLEN+1];
int n1,n2,match[MAXNW+1][MAXNW+1];

int input() {
char *tok;
int len,i;

if(!gets(line))
return 0;
len=strlen(line);
if (len<1) {
gets(line);
return -1;
}
for (i=0;i<len;i++)
if (!isalnum(line))
line=' ';
n1=0;
for (tok=strtok(line," ");tok;tok=strtok(NULL," "))
strcpy(w1[++n1],tok);

if(!gets(line))
return 0;
len=strlen(line);
if (len<1)
return -1;
for (i=0;i<len;i++)
if (!isalnum(line))
line=' ';
n2=0;
for (tok=strtok(line," ");tok;tok=strtok(NULL," "))
strcpy(w2[++n2],tok);

return 1;
}

void process() {
int i,j;

for (i=0;i<=n1;i++)
match[0]=0;
for (j=0;j<=n2;j++)
match[0][j]=0;

for (i=1;i<=n1;i++)
for (j=1;j<=n2;j++) {
if (!strcmp(w1,w2[j]))
match[j]=match[i-1][j-1]+1;
else
match[j]=MAX(match[i-1][j],match[j-1]);
}

printf("Length of longest match: %d\n",match[n1][n2]);
}

int main() {
int c,z;

#ifndef ONLINE_JUDGE
freopen("p10100i.txt","r",stdin);
freopen("p10100o.txt","w",stdout);
#endif

c=1;
while (z=input()) {
printf("%2d. ",c++);
if (z>0)
process();
else
printf("Blank!\n");
}
return 0;
}[/cpp]

[matrix2]

I've got WA on both problems. Perhaps I didn't understand the problems.
These problems are very poorly presented. The text tells you almost nothing.

For 10101 problem (Bangla numbers) what I must print if in the input is number like 1000000000? (1 billion)

Code: Select all

/*
 *	ACM Contest training
 *	Ion Lamasanu , July 2004
 *
 *	Bangla numbers: 10101  
 */

#include <stdio.h>
#include <math.h>

char *name[] = {
	"", 
	"shata", 
	"hajar", 
	"lakh",
	"kuti",  /***/
	"shata", 
	"hajar", 
	"lakh", 
	"kuti", /***/
	"shata",
	"hajar" };
double number[] = {
	1e0,
	1e2,
	1e3,
	1e5,
	1e7, /***/
	1e9,
	1e10,
	1e12,
	1e14, /***/
	1e16,
	1e17 };
double count[11];

double fdiv(double d, double x);
/* double fmod(double d, double x); EXISTA */
void calc(double N, int ind);


int main(void)
{
	int t=0;
	double N;
	while( scanf("%lf", &N) != EOF )
	{
		printf("%4d.", ++t);
		if(N == 0.00)
			puts(" 0");
		else
		{
			calc(N, 0);
         puts("");
		}
	}
	return 0;
}

double fdiv(double d, double x)
{
	double r = fmod(d,x);
	return (d-r)/x;
}

void calc(double N, int ind)
{
	if(N > 0.00)
	{
		double r = fmod(N, number[ind+1]);
		N -= r;
		r = fdiv(r, number[ind]);
		count[ind] = r;
		calc(N, ind+1); /** calc */
		printf(" %.0lf %s", r, name[ind]); /** print */
	}
} 

Wow..and here it comes Longest match.
What does mean longest match? The maximum number of consecutive words which are common to both lines of input? If so, the text for the problem does not suggest this.

Here is my code:

Code: Select all

/*
 *	ACM Contest training
 *	Ion Lamasanu , iulie 2004
 *
 *	Longest match: 10100
 */
#include <stdio.h>
#include <string.h>
#include <ctype.h>

char s1[1010], s2[1010], *words1[1000], *words2[1000];
int n1, n2;  /*** number of words */

int wordSrch(char s[], char *words[]);
void wordPrint(int n, char *words[]);
int longestMatch(void);
void init(void);

int main(void)
{
	int t = 0;
	fflush(stdin);
	while( 1 )
	{
		init();
		if( fgets(s1,1005,stdin)== NULL )
			break;
		fgets(s2,1005,stdin);
		printf("%2d. ", ++t); 
		if( *s1==0 || *s1=='\r' || *s1=='\n' || *s2==0 || *s2=='\r' || *s2=='\n' )
			puts("Blank!");
		else
		{
			n1 = wordSrch(s1, words1);
			n2 = wordSrch(s2, words2);
			/* wordPrint(n1, words1);
			wordPrint(n2, words2); */
			printf("Length of longest match: %d\n", longestMatch() );
		}
	}
	return 0;
}

int wordSrch(char s[], char *words[])
{
	int n, i;
	n = i = 0;
	while(i < 1010)
		if( isalpha(*s) )
		{
			words[n] = s;
			n++;
			while( isalpha(*s) && i<1010 )
				s++, i++;
		}
		else {
			*s = 0;
			s++;
			i++;
		}
	return n;
}

void wordPrint(int n, char *words[])
{
	int i;
	printf("{ ");
	for(i=0; i<n; i++)
		printf("%s ", words[i]);
	puts("}");
}

int longestMatch(void)
{
	int i, j, nr=0, t, a, b;
/*
	for(i=0; i<1010; i++)
	{
		s1[i] = toupper(s1[i]);
		s2[i] = toupper(s2[i]);
	}                    */

	for(i=0; i<n1; i++)
	{
		for(j=0; j<n2; j++)
			if( strcmp(words1[i],words2[j])==0 )
			{
				a = i; 
				b = j; 
				t = 0;
				while( a<n1 && b<n2 ) 
				{
					if( strcmp(words1[a],words2[b])==0 )
					{
						a++;
						b++;
						t++;
					}
					else
						break;
				}
				if(t > nr) nr = t;
			}
	}
	return nr;
}

void init(void)
{
	int i;
	for(i=0; i<1010; i++)
		s1[i] = s2[i] = 0;
}

Please help. (for me is really enigmatic)[/code]

[jackie]

Got AC
DP LCS
not a difficult problem but you should pay attention to the special input otherwise you may get WA for many many times.

input code


[cpp] while (gets(line1) && gets(line2))
{
m = strlen(line1);
n = strlen(line2);
if (m == 0 || n == 0)//for blank line if it exists
{
printf("%2d. Blank!\n", ++c);
continue;
}
//other
}[/cpp]

you should consider the input
;test;input;a

three words
1 test
2 input
3 a

so

[cpp] if (isupper(line1) || islower(line1) || isdigit(line1))
//put the charactor to the back of the current word[/cpp]
then do LCS
you will got AC

BTW i got PE for the first time i submitted it. The reason is:

For each case of input, you have to output a line starting with the case number right justified in a field width of two

Good luck

[kiha]

Heyya

some hints for those who know the algorithm but got WA [there are some stupid test cases]:

1) The case of the letters matters,
2) Characters '0', '1', ..., '9' are considered as alphabetic ones [not as white spaces],
3) Output 'Blank' only when no characters appear in the line.

Finally I got AC but I think it is pointless to waste solutions only when there are some stupid tests that nobody thinks of at first. With my hints above you should get AC. Good luck