850 - Crypt Kicker II

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

Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Thu Oct 21, 2004 9:34 pm

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
__nOi.m....

da_brain_damage
New poster
Posts: 1
Joined: Wed Feb 02, 2005 9:55 am

Post by da_brain_damage » Wed Feb 02, 2005 10:05 am

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 Always Was Considered HeartLess"
2004 ACM ICPC Arab & North Africa

jaredjohnson
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

I've got every test i've seen working

Post by jaredjohnson » Fri Feb 04, 2005 1:54 am

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

jaredjohnson
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

I solved my problem

Post by jaredjohnson » Wed Feb 09, 2005 12:26 am

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

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

p850 SIGSEGV?!?!?

Post by dootzky » Sun May 01, 2005 8:39 pm

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";

	}

}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun May 01, 2005 9:52 pm

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) {

joliner
New poster
Posts: 4
Joined: Mon May 02, 2005 1:47 am

I'm going crazy

Post by joliner » Mon May 02, 2005 1:52 am

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!!!!!!

joliner
New poster
Posts: 4
Joined: Mon May 02, 2005 1:47 am

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

Post by joliner » Mon May 02, 2005 1:59 am

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon May 02, 2005 2:13 am

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

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

Post by dootzky » Mon May 02, 2005 2:18 am

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! :o

and by the way, MF, my proggy also manages empty input line, but i'm still getting WA. :D 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. :D i'll do it tommorrow, it's 2:15 a.m. for crying out loud!

i... must... sleep... aaaawww.. tup! :P

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon May 02, 2005 2:53 am

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

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

Post by dootzky » Mon May 02, 2005 2:17 pm

HA!
unbelivable, i totally fogot about that possibility. :P :roll:

thx MF, you saved the day... again! :D 8)

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

joliner
New poster
Posts: 4
Joined: Mon May 02, 2005 1:47 am

I'm going crazy

Post by joliner » Mon May 02, 2005 4:06 pm

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

}



mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon May 02, 2005 5:20 pm

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


joliner
New poster
Posts: 4
Joined: Mon May 02, 2005 1:47 am

THANK YOU THANK YOU THANK YOU

Post by joliner » Tue May 03, 2005 3:11 pm

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

Post Reply

Return to “Volume 8 (800-899)”