850 - Crypt Kicker II

[Noim]

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

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

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

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

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

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

	}

}

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

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

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

[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

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

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

[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

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

}

[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

[joliner]

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