418 - Molecules

[Rein]

I try to use brute force to caculate all possible arrangement, but I just can't get AC on this porblem. So, could anyone please give me a hint?

Besides, there seems to be some illegal input given, and how should I handle with them? Skip all the four line? Or skip only one line?

[mamun]

I'm getting WA. Can somebody kindly post their output for the following input?

Code: Select all

DHBEHPJKEEOG
BEPIKGIFPHIG
BNKBAOFCFEFO
FLMLDOKHMLJM
GOONKCMPDJMA
GONODPDFJABJ
FPBDOKOKOLMG
PMIBKLEHEOIJ
HDHCMIMKGALA
EGBFINLCABIF
IHOOJIIAHFJA
LNBMNPDJDCDI
KLMGFJJBJHMB
NHPNEOGNGHGK
MBBLDPJJDALJ
JMHCHMHOJEBD
NOFJEMOGDCDD
BOFJBBLEMOBD
ILDEOFBAOMGH
NCCBPFBFONLD
LIHEBEEHOEMH
OCEONEPNCKFD
IBLDPJAOKECH
DBPNIJGLBONO
ALBCFIAAEHJF
BOJJNMLOOFBN
DGNJELDPGKGC
OMKGEMMCAFKP
GPFNEBKMFLHL
JMLJNCNHJFLO
GMNIAILGOPNK
NDJGDPBNEPMO
OKCDGPKKFKPD
JNCNPHLOCGAF
OBCOAELLPPGH
MIBKJOLFIKEP
LINEDIOMEGIC
LGAIEHEHDJJE
FKFANCLAEKJJ
EAHHPHKLICEG
AAAAAAAAAAAA
AAAAAAAAAAAA
AAAAAAAAAAAA
AAAAAAAAAAAA
AAAAAAAAAAAA
BBBBBBBBBBBB
CCCCCCCCCCCC
DDDDDDDDDDDD
APAAAAAAAAPA
BPBBBBBBBBPB
CPCCCCCCCCPC
DPDDDDDDDDPD
APAAAAAAAAOA
BOBBBBBBBBNB
CMCCCCCCCCNC
DPDDDDDDDDMD
Q

[mf]

My AC's output is:

Code: Select all

2
30
4
8
24
14
6
21
6
16
64
0
64
64

[mamun]

Thanks a lot! I've got it accepted.

[Jemerson]

Hi all, i got a question, if any can tell me i'll be thankfull. As my english is not so good I guess I didn't understand the problem description very well. Is is true that both vertical chains must be is the same horizontal level?
Here is an example:

Code: Select all

              O
              S
         B    J
    JAAISLJDALLA 
         D    L
       FCAOAIAAALL 
         O    L
         M    P
         N    A
         A    Q
         L    O
         A    A
         X
         Z

My understand is that this can't happen cause the two vertical lines are not in the same horizontal level, is this correct?

Thanx in advance

[mf]

No, the arrangement you showed is valid.

[shanto86]

I cant understand why my code gives wa. as u can see there are two CHECK functions. the second one is my friend's if i use that it gives AC, but mine is the un commented, if i use that it gives WA. i searched net and got the i/o of the regionals. and both of the function gives same output. so i am confused. can any one tell me where is my fault?

Code: Select all

#include<stdio.h>
#include<algorithm>
#include<assert.h>
using namespace std;

#define L 1
#define H 11

int ans;

void CHECK(char *s1,char *s2,char *s3,char *s4)
{
	int i,j,k,l,m,s,t,d;

	for(i=L;i<H;i++)
		for(j=L;j<H;j++)
			if(s1[i]==s2[j])
			{
				for(k=i+2;k<H;k++)
					for(l=L;l<H;l++)
						if(s1[k]==s3[l])
						{
							d=k-i;

							for(m=L;m+d<H;m++)
							{
								for(s=j+2,t=l+2;s<H && t<H;s++,t++)
									if(s2[s]==s4[m] && s3[t]==s4[m+d] && ans<(d-1)*(s-j-1))
										ans=(d-1)*(s-j-1);
							}
						}
			}

}
/*
void CHECK(char *h1,char *h2,char *v1,char *v2){
	int i1,i2,hd,j1,j2,vd;
	for(hd=9;hd>1;hd--){
		for(vd=9;vd>1;vd--){
			for(i1=1;i1+hd<11;i1++){
				for(j1=1;j1+vd<11;j1++){
					if(h1[i1]!=v1[j1])
						continue;
					for(i2=1;i2+hd<11;i2++){
						if(h2[i2]!=v1[j1+vd])
							continue;
						for(j2=1;j2+vd<11;j2++){
							if(h1[i1+hd]!=v2[j2] || h2[i2+hd]!=v2[j2+vd])
								continue;
							if((hd-1)*(vd-1) > ans)
								ans=(hd-1)*(vd-1);
						}
					}
				}
			}
		}
	}
}
*/
int main()
{
	char word[5][20];
	int x[5];

	while(scanf("%s",word[0]) && word[0][0]!='Q')
	{
		scanf("%s%s%s",word[1],word[2],word[3]);

		x[0]=0, x[1]=1, x[2]=2, x[3]=3;

		ans=0;

		do
		{
			CHECK(word[x[0]],word[x[1]],word[x[2]],word[x[3]]);
		}while(next_permutation(x,x+4));

		printf("%d\n",ans);
	}

	return 0;
}

[shakil]

shanto86 ,
My function is similar to you and AC.I also don't understood of your WA.

Code: Select all

for(i=1;i<=10;i++)
for(j=1;j<=10;j++)
if(sa0[i]==sa1[j])
{
for(m=j+2;m<=10;m++)
for(k=1;k<=10;k++)
if(sa1[m]==sa2[k])
{
p=i+2;
q=k+2;
dis=m-j;
while(1)
{
if(p>10||q>10)
break;
for(n=1;n<=10-dis;n++)
if(sa3[n]==sa0[p]&&sa3[n+dis]==sa2[q])
{
re=(dis-1)*(p-i-1);
if(re>max)
max=re;
}
p++;q++;

}


}



}