10100 - Longest Match

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sat Aug 30, 2003 3:50 pm

little joey wrote:Hi hi.
We were writing our postings at the same time! Julien and I said exactly the same thing.
:lol: :wink:

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sat Sep 06, 2003 4:15 pm

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
Istiaque Ahmed [the LA-Z-BOy]

shamim(aiub)
New poster
Posts: 5
Joined: Wed Oct 22, 2003 3:29 am
Location: dhaka
Contact:

10100::::what will be the output

Post by shamim(aiub) » Mon Nov 03, 2003 11:25 pm

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]

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Mon Mar 08, 2004 2:57 pm

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

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

10100 - Longest match WA?????

Post by mlvahe » Sun Apr 11, 2004 7:34 pm

Can anybody do a favour telling me where I am mistaken.
Whatever I do I get WA. :cry: :cry: :cry: :cry:
[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]

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Apr 12, 2004 10:26 am

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.

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

Thanks.

Post by mlvahe » Mon Apr 12, 2004 6:22 pm

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

udcp
New poster
Posts: 6
Joined: Fri Jun 21, 2002 10:24 pm
Location: USA

Can anyone help me find the reason for WA?? : 10100

Post by udcp » Wed May 05, 2004 7:44 pm

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
New poster
Posts: 6
Joined: Fri Jun 21, 2002 10:24 pm
Location: USA

10100

Post by udcp » Tue May 11, 2004 7:52 am

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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Wed May 19, 2004 6:27 am

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?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Tue Jun 01, 2004 7:35 am

My code gives the output for the following inputs as..
You're outputs are exactly the same as mine.


Anggakusuma

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Runtime Error SIGSEGV

Post by ec3_limz » Sun Jun 20, 2004 7:53 pm

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
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

10100 & 10101 both WA. Why?

Post by matrix2 » Wed Jul 21, 2004 11:48 am

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]
Things are simple, but we make them complex.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Sat Jul 24, 2004 3:34 am

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
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Sun Jul 25, 2004 1:48 pm

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 ;)
kiha

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest