OJ Board • 850 - Crypt Kicker II - Page 2

Page 2 of 6

Posted: Thu Oct 21, 2004 9:34 pm

by Noim

input wrote:1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
awerwaerwrwa

output wrote: now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they
xzurzxurzrzx
Press any key to continue

try this inputs.
good luck

Posted: Wed Feb 02, 2005 10:05 am

by da_brain_damage

i finally got accepted on this one ...

here's some hints to any of u who still go WA's

1- there won't always be a key in the input , even though it says in the problem ( Assume that one of the lines of input is the encrypted form of the plaintext " the quick brown fox jumps over the lazy dog " ), but it seems that some test data doesn't have this encypted line , so following test data will be legal

Code: Select all

1

Test

Output :

Code: Select all

No solution.

2- check for all given keys , here a test data

Code: Select all

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceeob lrtzv ita hegfd tsmr xnm ypwq ktj
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

Output :

Code: Select all

now is the time for all good men to come to the aid of the party
the quuck brown fox jumps over the lazy dog
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

well i hoped i helped ....

I've got every test i've seen working

Posted: Fri Feb 04, 2005 1:54 am

by jaredjohnson

I just can't get the judge to accept it. I'm going a little crazy....

#include<iostream>
#include<string>
#include<fstream>
using namespace std;

char phrase[44]="the quick brown fox jumps over the lazy dog";
char phraseReversed[44]="god yzal eht revo spmuj xof nworb kciuq eht";

char decode(char c, string decoder)
{
return phrase[decoder.find(c)];
}

char decode2(char c, string decoder)
{
return phrase[decoder.find_last_of(c)];
}

bool testLine(string s) {

char test[44];
char test2[44];

if(s.length()!=43) return 0;
for(int i=0; i<43; i++)
test=decode(s, s);
for(int i=0; i<43; i++)
test2=decode2(s, s);
test[43]=0;
test2[43]=0;
return !(strcmp(test, phrase)) && !(strcmp(test2, phrase));

}

int main(void) {
//ifstream fin("in.txt");
int numTests;
int numLines=0;
string s;
string lines[100];
string decoder;
decoder[0]='&';
cin>>numTests;
getline(cin,s);
getline(cin,s);
for(int i=0; i<numTests; i++) {

while(getline(cin, s) && s.length()>0) {
lines[numLines]=s;
if(testLine(lines[numLines])) decoder=lines[numLines];
numLines++;
}
if(decoder[0]=='&')
cout<<"No solution."<<endl<<endl;
else {
for(int i=0; i<numLines; i++) {
int temp=lines.length();
for(int j=0; j<temp; j++)
cout<<decode(lines[j], decoder);
cout<<endl;
}
cout<<endl;
}
decoder[0]='&';
numLines=0;
}
}

I solved my problem

Posted: Wed Feb 09, 2005 12:26 am

by jaredjohnson

(I am typing this because it is annoying when people solve their problems and then let us all know their program was accepted, without enlightening us to what the problem was)

A fellow classmate tested my program for me and found a case that it doesn't work on.

I was treating the space as a regular character, when, with this program, it is a special character. That is, it can't ever be converted into any other character.

So if you gave my program a key with the spaces converted all to some character, then it would accept this key.

I fixed the problem by adding a line to my decode function which checks for a spaces before converting characters.

p850 SIGSEGV?!?!?

Posted: Sun May 01, 2005 8:39 pm

by dootzky

wtf?

invalid memory reference?!?!
why? my arrays are obviously big enough (1000).

maybe i'm handling input wrongly?
here's my code, hope someone can help.
and please, look only the MAIN function, forget about decode and key sentance functions. it works for all test cases posted on this forum.

thx,
dootzky

Code: Select all

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

	int a,c,i,j,n,br,duz;
	char dict[1000][1000],line[1000],line2[1000];

bool banzaii_test (char line[1000]) {

	// 1. duzina recenice
	if (duz!=43) return false;

	// 2. broj space-ova
	a=0;
	for (j=0;j<duz;j++) if (line[j]==' ') a++;
	if (a!=8) return false;

	// 3. pozicija space-ova
	if ( (line[3]==' ') && (line[9]==' ') && (line[15]==' ') && 
		 (line[19]==' ') && (line[25]==' ') && (line[30]==' ') && 
		 (line[34]==' ') && (line[39]==' ') ) {}
	else return false;

	// 4. the=the
	if ( (line[0]==line[31]) && (line[1]==line[32]) && (line[2]==line[33]) ) {}
	else return false;

	// 5. e=e
	if (line[2]==line[28]) {}
	else return false;

	// 6. u=u
	if (line[5]==line[21]) {}
	else return false;

	// 7. r=r
	if (line[11]==line[29]) {}
	else return false;
	
	// 8. o=o=o=o
	char t=line[12];
	if ( (line[12]==t) && (line[17]==t) && (line[26]==t) && (line[41]==t) ) {}
	else return false;

	return true;
}


bool go_find_pass () {

	bool ok=false;

	for (i=0;i<c;i++) {
		duz = strlen(dict[i]);
		if (banzaii_test(dict[i])) { br=i; ok=true; break; }
	}

	return ok;
}


void fucking_output () {

	for (i=0;i<c;i++) {
		for (j=0;j<(signed)strlen(dict[i]);j++) {
			if (dict[i][j]==dict[br][0]) cout << 't';
			else if (dict[i][j]==dict[br][1]) cout << 'h';
			else if (dict[i][j]==dict[br][2]) cout << 'e';
			else if (dict[i][j]==dict[br][4]) cout << 'q';
			else if (dict[i][j]==dict[br][5]) cout << 'u';
			else if (dict[i][j]==dict[br][6]) cout << 'i';
			else if (dict[i][j]==dict[br][7]) cout << 'c';
			else if (dict[i][j]==dict[br][8]) cout << 'k';
			else if (dict[i][j]==dict[br][10]) cout << 'b';
			else if (dict[i][j]==dict[br][11]) cout << 'r';
			else if (dict[i][j]==dict[br][12]) cout << 'o';
			else if (dict[i][j]==dict[br][13]) cout << 'w';
			else if (dict[i][j]==dict[br][14]) cout << 'n';
			else if (dict[i][j]==dict[br][16]) cout << 'f';
			else if (dict[i][j]==dict[br][18]) cout << 'x';
			else if (dict[i][j]==dict[br][20]) cout << 'j';
			else if (dict[i][j]==dict[br][22]) cout << 'm';
			else if (dict[i][j]==dict[br][23]) cout << 'p';
			else if (dict[i][j]==dict[br][24]) cout << 's';
			else if (dict[i][j]==dict[br][27]) cout << 'v';
			else if (dict[i][j]==dict[br][35]) cout << 'l';
			else if (dict[i][j]==dict[br][36]) cout << 'a';
			else if (dict[i][j]==dict[br][37]) cout << 'z';
			else if (dict[i][j]==dict[br][38]) cout << 'y';
			else if (dict[i][j]==dict[br][40]) cout << 'd';
			else if (dict[i][j]==dict[br][42]) cout << 'g';
			else if (dict[i][j]==dict[br][3]) cout << ' ';
		}
		cout << endl;
	}

	cout << endl;
}


void main () {

	scanf ("%d\n",&n);

	for (int m=0;m<n;m++) {
	
		c=0; // number of lines in text

		while (1) {
			gets(line2);
			duz = strlen(line2);
			if (duz==0) break; 
			strcpy (dict[c++],line2);

		} // end of while

		if (go_find_pass()) fucking_output();
		else cout << "No solution.\n";

	}

}

Posted: Sun May 01, 2005 9:52 pm

by mf

Hi, dootsky.

You get sigsegv because there's no blank line after the last test case in the input.

The function gets() on EOF only returns NULL, without modifying its buffer.

To handle this, you can replace the code

Code: Select all

      while (1) {
         gets(line2);

by

Code: Select all

      while (gets(line2) != NULL) {

I'm going crazy

Posted: Mon May 02, 2005 1:52 am

by joliner

is this input legal? or should my program "cout" No solution?

Code: Select all

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm        ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

please post some cases, i've tested all i've found and my program apparently works...
but I always get a WA!!!!!!

850 WA !!!!!!!!!!!

Posted: Mon May 02, 2005 1:59 am

by joliner

is this input legal? or should my program "cout" No solution?

Code: Select all

1

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm        ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

and is that correct?
Input:

Code: Select all

2

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
xnm ceeob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceeob lrtzv ita hegfd tsmr xnm ypwq ktj
xnm ceoob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

Output:

Code: Select all

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
the quuck brown fox jumps over the lazy dog
programming contests are fun arent they

No solution.

Posted: Mon May 02, 2005 2:13 am

by mf

Well, my accepted program printf's

"No solution" for your input.

The only tricky case in the judge's input, I think, may be a blank case:

Code: Select all

3

vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq


vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq

My output:

Code: Select all

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

No solution.

now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they

Posted: Mon May 02, 2005 2:18 am

by dootzky

i also think that the answer should be "No solution."
because it's said:

"...and that one of the lines of input is the encrypted form of the plaintext the quick brown fox jumps over the lazy dog..."

so, i don't think additional spaces should occur in "decrypt key sentance".
i think!

and by the way, MF, my proggy also manages empty input line, but i'm still getting WA.

i must've done something terribly stupid, but i'll try more test cases L8R.

thx MF once more for your help, but now i must figure out why i'm getting WA.

i'll do it tommorrow, it's 2:15 a.m. for crying out loud!

i... must... sleep... aaaawww.. tup!

Posted: Mon May 02, 2005 2:53 am

by mf

Hi again, dootzky. I found a test case which your program does not handle correctly:

Code: Select all

1

xxx xxxxx xxxxx xxx xxxxx xxxx xxx xxxx xxx

The output must be "No solution," because the encryption function must be one-to-one, i.e. reversible. And in the above example, there's no way to replace `x' by some letter to get "the lazy fox..."

Posted: Mon May 02, 2005 2:17 pm

by dootzky

HA!
unbelivable, i totally fogot about that possibility.

thx MF, you saved the day... again!

cheers dude,
i just hope i can repay my debt some day, i hope there's gonna be a problem you won't be able to solve, and then - the great dootzky will come to aid you! haha...

no, seriously - thx man. i would waist my already wasted brain cells on this, you helped a lot.

ReSPeCT,
dootzky

I'm going crazy

Posted: Mon May 02, 2005 4:06 pm

by joliner

thanx a lo mf, but my program allready manages with blank cases and also returns no solution for a cas where there is not "bijection" (xxx xxxxx xxxxx...) but i still get a WA!
I post my code, if you can see any error please tell it to me....

Code: Select all

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main()
{
int cases;
string theone = "the quick brown fox jumps over the lazy dog";
cin >> cases;
cin.ignore();
string str;

getline(cin,str);
for (int c=0; c<cases; c++)
{


getline(cin,str);
vector<string> totes;
bool calamar=false;

while ((int)str.size()!=0 && not calamar)
{
totes.push_back(str);
if (cin.eof())
calamar=true;
getline(cin,str);
}

vector<int> quines;

for (int i=0; i<(int)totes.size(); i++)
{
bool es=true;

	if (totes[i].size()==theone.size())
	{
		for (int p=0; p<(int)theone.size(); p++)
		{
		for (int l=0; l<(int)theone.size(); l++)
		{
		if (theone[l]==theone[p] && totes[i][p]!=totes[i][l])
		es=false;
		}
		
		
			if (theone[p]==' ')
			{
			if (totes[i][p]!=' ')
				es=false;
			
			}
			if (totes[i][p]==' ')
			{
			if (theone[p]!=' ')
				es=false;
			
			}
		}
	}
	else
	{
		es=false;
	}
	if (es==true)
	{
		es=false;
		quines.push_back(i);
	}
}
bool grater=false;

for (int qui=0; qui<(int)quines.size() && grater==false; qui++)
{
	bool bigexit = false;
	vector<string> totowrite;
	for (int i=0; i<(int)totes.size() && bigexit == false; i++)
	{

		string towrite;
		bool imposible=false;
		for (int k=0; k<(int)totes[i].size() && imposible == false; k++)
		{
			bool exit = false;
			for (int p=0; p<(int)totes[quines[qui]].size() && exit == false; p++)
			{
				if (totes[quines[qui]][p] == totes[i][k])
				{
					exit = true;
					towrite.push_back(theone[p]);
				}
			}
		if (exit == false)
		imposible = true;
		
		
		}
	
	if (imposible==false)
	totowrite.push_back(towrite);
	else
	bigexit = true;
	
	}

if (bigexit == false)
{
	for (int m=0; m<(int)totowrite.size(); m++)
		cout << totowrite[m] << endl;
	grater=true;
}




//if ((int)quines.size()=0)
//cout << "No solution." << endl;


}
if (grater==false)
cout << "No solution." << endl;
if (c<cases-1)
cout << endl;
}

}

Posted: Mon May 02, 2005 5:20 pm

by mf

Hi! Try these test cases. The output for all should be "No solution." There are no spaces at the end of lines in these inputs.

Code: Select all

4

xxx xxxxx xxxxx xxx xxxxx xxxx xxx xxxx xxx

xnm eeeee lrtzv ita hegfd tsmr xnm yyyy ktj
zzz zzzzz zzzzz zzz zzzzz zzzz zzz zzzz zzz

the quikk brown fox jumps over the lazy log

the quite grown fox jumps over the lazy box

THANK YOU THANK YOU THANK YOU

Posted: Tue May 03, 2005 3:11 pm

by joliner

thanks mf
I got AC... theres is nothing more to say....
Thank you.