417 - Word Index

[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]

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]

[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

[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...

[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");
}
}

[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]

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]

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
Is there any problem in judge output file?

[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]

OH!!
I always do that fault!!

Thanks

[ibrahim]

Dear Sakib,

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

[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.
maybe i'm wrong here...
hope it helps,
dootzky

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

[hamedv]

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

[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