417 - Word Index

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

Moderator: Board moderators

zulfo
New poster
Posts: 1
Joined: Fri Sep 26, 2003 6:55 pm

417 why wrong answer

Post by zulfo »

can anyone tell me what is wrong? here is source:

#include <iostream.h>
#include <string.h>

long x=0;
char s[6];
char tab[83682][6];

void genall(int len, int dub) {
if (dub) s[dub]=s[dub-1]+1; else s[dub]='a';
for ( ; s[dub]<='z'-len+dub+1; s[dub]++)
{
if (dub+1<len) genall(len,dub+1);
else strcpy(&tab[++x][0],&s[0]);
};
};

int poredi(const char *a,const char *b) {
if (strlen(a)!=strlen(b)) return strlen(a)-strlen(b);
return strcmp(a,b);
};//poredi

long bsearch_tab(long begin, long end) {
if (begin==end) return begin;
int res=poredi(&s[0],&tab[(begin+end)/2][0]);
if (!res) return (begin+end)/2;
else if (res<0) return bsearch_tab(begin,(begin+end)/2-1);
else return bsearch_tab((begin+end)/2+1,end);
};//bsearch_tab

int i,e;

int main() {
for (i=0; i<7; i++) s=0;
for (int d=1; d<6; d++) genall(d,0); //generates table

while (!cin.eof()) {
cin.getline(s,7); e=0;
for (i=1; i<strlen(s); i++)
if (s[i-1]>=s) {cout<<"0\n"; e=i; break;}
if (!e) cout<<bsearch_tab(1,83681)<<endl;
};//while loop
return 0;}

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

417 - Word Index

Post by CodeMaker »

Hi, can anyone tell me why I get wrong answer in this problem...i tried to find it out....but i think it gives correct output...where is the problem?

[c]#include<stdio.h>
#include<string.h>
#include<ctype.h>
void main()
{
int len,count,i,j,k,l,m,flage;
char temp[10],string[10000];
while(gets(string))
{
count=len=0;
for(i=0;string;i++)
{
if(islower(string))
{
temp[len++]=string;
}
}

flage=0;
for(i=0;i<len-1;i++)
{
if(temp>=temp[i+1])
{
flage=1;
break;
}
}
if(flage)
{
printf("0\n");
continue;
}

if(len==1)
{
count=temp[0]-'a'+1;
}
else if(len==2)
{
count=26;

for(i='a';i<=temp[0];i++)
{
for(j=i+1;j<='z';j++)
{
count++;
if(temp[0]==i && temp[1]==j)
break;
}
}
}
else if(len==3)
{
count=351;

for(i='a';i<=temp[0];i++)
{
for(j=i+1;j<=temp[1];j++)
{
for(k=j+1;k<='z';k++)
{
count++;
if(i==temp[0]&&j==temp[1]&&k==temp[2])
break;
}
}
}
}
else if(len==4)
{
count=2951;

for(i='a';i<=temp[0];i++)
{
for(j=i+1;j<=temp[1];j++)
{
for(k=j+1;k<=temp[2];k++)
{
for(l=k+1;l<='z';l++)
{
count++;
if(i==temp[0]&&j==temp[1]&&
k==temp[2]&&l==temp[3])
break;
}
}
}
}
}
else if(len==5)
{
count=17901;

for(i='a';i<=temp[0];i++)
{
for(j=i+1;j<=temp[1];j++)
{
for(k=j+1;k<=temp[2];k++)
{
for(l=k+1;l<=temp[3];l++)
{
for(m=l+1;m<='z';m++)
{
count++;
if(i==temp[0]&&j==temp[1]&&
k==temp[2]&&l==temp[3]&&
m==temp[4])
break;
}
}
}
}
}
}
else
count=0;
printf("%d\n",count);
}
}

[/c][/code]
Jalal : AIUB SPARKS

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker »

:-? well, it looks like noone like the code i gave here....I know, I know ,its a dumb one...but i have to do it for now, may be i will find a batter way later....

so, anyway....can anyone who got acc give me some data to test or will u plz check with ur acc code to math some output......

i m having problem to debuge the code because i dont know where i m doing the mistake, i even dont understant the output i get is right or wrong. if there is any logical error then how count reaches to 83681 for "vwxyz" ?

if someone just can say that -" your code doesn't give me the output for this input" that will do.....ok bye, plz somebody give me something before i have to find it out myself.......i have to test a lot of data for this type of problem.....too hard :cry:
Jalal : AIUB SPARKS

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker »

Hi, got Acc atlast :)

now I made a table with some kind of similar code and checked for match.....

I got similar results from these two codes and I knew that I will get Acc in this way as friend also do, but I wanted to know why generating the count at real time is not working.....

none helped, may be I will find it later myself or may be someone may help me to find out later on.....

anyway... :-?
Jalal : AIUB SPARKS

Sakib
New poster
Posts: 24
Joined: Fri Jan 28, 2005 5:27 pm
Location: Bangladesh

417 - Word index - WA - why?

Post by Sakib »

I dont know what is wrong. Can anyone help me? :(

#include<stdio.h>
#include<string.h>
char s[84000][5],t[50];
unsigned long a,b,i,j,k,n,p,q;
void main()
{
n=0;
//---------------------------
for(i=0;i<26;i++)
{
s[n][0]='a'+i;
n++;
}
//-----------------------

//---------------------------
for(i=0;i<25;i++)
{
for(j=i+1;j<26;j++)
{
s[n][0]='a'+i;
s[n][1]='a'+j;
n++;
}
}
//-----------------------

//---------------------------
for(i=0;i<24;i++)
{
for(j=i+1;j<25;j++)
{
for(k=j+1;k<26;k++)
{
s[n][0]='a'+i;
s[n][1]='a'+j;
s[n][2]='a'+k;
n++;
}
}
}
//-----------------------

//---------------------------
for(i=0;i<23;i++)
{
for(j=i+1;j<24;j++)
{
for(k=j+1;k<25;k++)
{
for(p=k+1;p<26;p++)
{
s[n][0]='a'+i;
s[n][1]='a'+j;
s[n][2]='a'+k;
s[n][3]='a'+p;
n++;
}
}
}
}
//---------------------------------

//----------------------------------
for(i=0;i<22;i++)
{
for(j=i+1;j<23;j++)
{
for(k=j+1;k<24;k++)
{
for(p=k+1;p<25;p++)
{
for(q=p+1;q<26;q++)
{
s[n][0]='a'+i;
s[n][1]='a'+j;
s[n][2]='a'+k;
s[n][3]='a'+p;
s[n][4]='a'+q;
n++;
}
}
}
}
}

//-------------------------------


while(scanf("%s",&t)==1)
{
int c=0;
for(i=0;i<n;i++)
{
if(strcmp(t,s)==0)
{
printf("%ld\n",i+1);
c=1;
}
}
if(c==0)printf("0\n");
}
}
/* Sorry For Nothing */

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 »

I don't know why I get WA in this problem. Here is some inputs please give the output of these inputs from you AC code;

Code: Select all

az
bc
bz
cd
ce
cz
xy
xz
yz
abc
abd
abz
acd
ade
awz
axz
ayz
bcd
bce
byz
cde
cdf
wxz
wyz
xyz
abcd
abce
axyz
bcde
bxyz
txyz
vxyz
wxyz
abcde
awxyz
bcdef
cdpq
uwxyz
vwxyz

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster »

My AC program's output:

Code: Select all

51
52
75
76
77
98
349
350
351
352
353
375
376
399
648
650
651
652
653
927
928
929
2949
2950
2951
2952
2953
5251
5252
7275
17886
17900
17901
17902
30551
30552
7452
83680
83681
HTH,
Christian

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 »

I got a very big input output file of this problem from this page:
http://contest.mff.cuni.cz/archive/ecam1995/index.html
And My program pass all the inputs but I am still getting WA from judge.
Here is my code:

Code: Select all

Removed After Get AC :)
I am feeling terrible :evil:
Is there any problem in judge output file?
Last edited by A1 on Sat Feb 12, 2005 10:05 am, edited 1 time in total.

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster »

I found two things:

Your "words" array needs to be of size 83682, because you write to words[83681] in makeindex.

Don't compare the result of strcmp to 1 and -1, but check if it is greater or less than zero. Due to that mistake, your program gave negative values on my (and probably the judge's) machine.

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 »

OH!!
I always do that fault!!

Thanks

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Re: 417 - Word index - WA - why?

Post by ibrahim »

Dear Sakib,

Just change your array size of s string.
char s[84000][6];
You will get Accept :D

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

well...

Post by dootzky »

probably the mistake is in your "invalid word" sequence.
what i mean is, you check with every following letter if next one is wrong, but then you get the wrong output, don't you?

let me explain. if the word is:

"abcd"
you will give the rigth answer.
if the word is:
"bacd"
you will again give the right anser.
BUT, if the word is:
"abdc",
you will start sending one by one letter to you function, and then when you get to the "d>c", you will print out "0".

seems wrong to me. but i dunno. :o
maybe i'm wrong here...
hope it helps,
dootzky

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR »

can any body help me with this code ?
i've already depressed because of this 417 problem.
did i make any mistakes in my code ?
thanx before for your help :)

Code: Select all

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

#define MAX 84000

char hurup[MAX][6];


int i=0;
void gen(void)
{
	int a,b,c,d,e;

	for(a=0;a<26;a++)
	{
		hurup[i][0]=a+'a';
		i++;
	}
	for(a=0;a<26;a++)
		for(b=a+1;b<26;b++)
		{

		   hurup[i][0]=a+'a';
		   hurup[i][1]=b+'a';
		   i++;
		}

	for(a=0;a<26;a++)
		for(b=a+1;b<26;b++)
			for(c=b+1;c<26;c++)
			{
			   hurup[i][0]=a+'a';
			   hurup[i][1]=b+'a';
			   hurup[i][2]=c+'a';
			   i++;
			}

	for(a=0;a<26;a++);
		for(b=a+1;b<26;b++)
			for(c=b+1;c<26;c++)
				for(d=c+1;d<26;d++)
				{
				   hurup[i][0]=a+'a';
				   hurup[i][1]=b+'a';
				   hurup[i][2]=c+'a';
				   hurup[i][3]=d+'a';

				   i++;
				}

	for(a=0;a<26;a++)
		for(b=a+1;b<26;b++)
			for(c=b+1;c<26;c++)
				for(d=c+1;d<26;d++)
					for(e=d+1;e<26;e++)
					{
					   hurup[i][0]=a+'a';
					   hurup[i][1]=b+'a';
					   hurup[i][2]=c+'a';
					   hurup[i][3]=d+'a';
					   hurup[i][4]=e+'a';

					   i++;
					}
}


void main()
{
	char kalimat[10];
	int il, nilai;
	#ifndef ONLINE_JUDGE
		freopen ("417.in","r",stdin);
		freopen ("417.out","w",stdout);
	#endif

	gen();
	while (scanf ("%s",&kalimat)!=EOF)
	{
		nilai=-1;
		for (il=0;il<i;il++)
		{

			/*if (kalimat[0]==hurup[il][0] && kalimat[1]==hurup[il][1] && kalimat[2]==hurup[il][2]&& kalimat[3]==hurup[il][3]&& kalimat[4]==hurup[il][4])*/
			if (strcmp(kalimat,hurup[il])==0)
			{
				nilai=il;
				break;
			}
		}
		printf("%d\n",nilai+1);
	}
}
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv »

you most replace this line
char tab[83682][6];
with
char tab[83682][7];

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 417 - Word index - WA - why?

Post by Shafaet_du »

Use nested loops to generate all the combinations serially and store it in hash table. use STL map.
sample:

Code: Select all

abc
hmxy
slop
sqwz
ayz
mptwz
output:

Code: Select all

352
14553
0
0
651
82161

Post Reply

Return to “Volume 4 (400-499)”