554 - Caesar Cypher

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

Moderator: Board moderators

dongyf
New poster
Posts: 4
Joined: Thu Jun 13, 2002 5:12 pm

554 - Caesar Cypher

Post by dongyf » Sat Aug 10, 2002 8:17 pm

Can anyone tell me why this code got WA.
Anything helpful on the problem will be appreciate.

@BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <strstream>
#include <cstring>
#include <cctype>
using namespace std;

char dic[200][30];
int len;
char cipher[300], message[300];
int match, best;

void readDic()
{
char word[30];
len = 0;
cin.getline(word, sizeof(word));
while (word[0] != '#') {
strcpy(dic[len], word);
len++;

cin.getline(word, sizeof(word));
}
}

bool find(char* word)
{
for (int i = 0; i < len; i++)
if (strcmp(dic, word) == 0)
return true;

return false;
}

int toInt(char ch)
{
if (ch == ' ')
return 0;
else
return ch - 'A' + 1;
}

char toChar(int i)
{
if (i == 0)
return ' ';
else
return i - 1 + 'A';

}

void decrypt(int k)
{
for (int i = 0; i < strlen(cipher); i++) {
int x = toInt(cipher);
x = (x + k) % 27;
message = toChar(x);
}
message[strlen(cipher)] = '\0';
}

void solve()
{
best = 0;
match = 0;
for (int k = 1; k <= 26; k++) {
decrypt(k);

istrstream is(message);
char word[300];
int cnt = 0;
while (is >> word)
if (find(word))
cnt++;

if (cnt > match) {
match = cnt;
best = k;
}
}

decrypt(best);

if (strlen(message) > 60) {
int i = 60;
while (i >= 0 && isupper(message))
i--;
if (i >= 0)
message = '\0';
else
message[0] = '\0';
}

cout << message << endl;
}

void main()
{
readDic();

cin.getline(cipher, sizeof(cipher));
while (!cin.eof()) {
solve();
cin.getline(cipher, sizeof(cipher));

}
}
@END_OF_SOURCE_CODE

donny
New poster
Posts: 2
Joined: Thu Jun 06, 2002 8:45 am

Post by donny » Sun Aug 11, 2002 1:03 pm

firstly, i think you need to format the output
i also need some help...
i keep getting presentation error, can't seem to
get rid of it i think i have handled the word warping..
is there any trick to the output?

dongyf
New poster
Posts: 4
Joined: Thu Jun 13, 2002 5:12 pm

Can you tell me what's your output for the following data

Post by dongyf » Mon Aug 12, 2002 5:04 am

Can you tell me what's your output for the following data
@BEGIN_OF_TEST_CASE
THANK
YOU
FOR
YOUR
HELP
#
ABCDEFGHIJ
ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ
ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ BCDEFGHIJA
@END_OF_TEST_CASE

donny
New poster
Posts: 2
Joined: Thu Jun 06, 2002 8:45 am

Post by donny » Tue Aug 13, 2002 4:12 pm

I get:
ABCDEFGHI

the program only takes in one line as the input.

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Wed Aug 14, 2002 5:28 am

and here's my code...
why wa?

[cpp]
#include <iostream>
#include <string.h>
char dict[100][30],str[300],d[27];
int n,map[128];
void init () {
char ch;
for (ch='A';ch<='Z';ch++)
map[ch] = ch-'A'+1;
map[' '] = 0;
for (ch='A';ch<='Z';ch++)
d[ch-'A'+1] = ch;
d[0] = ' ';
}
int search (char s[]) {
for (int i=0;i<n;i++)
if (strcmp(s,dict)==0)
return 1;
return 0;
}
void decrypt () {
int i,k,l,len,maxlen,maxmatch,match;
char tmp[300],bak[300],ok[300],*p;
maxlen = maxmatch = 0;
for (k=0;k<=26;k++) {
strcpy(tmp,str);
l = strlen(tmp);
for (i=0;i<l;i++) {
tmp = d[(map[tmp]+k)%27];
}
l--;
while (tmp[l]==' ') l--;
tmp[l+1] = '\0';
strcpy(bak,tmp);
len = l+1;
match = 0;
p = strtok(tmp," \t\b\r\n");
while (p) {
if (search(p))
match++;
p = strtok(NULL," \t\b\r\n");
}
if (match>maxmatch) {
maxlen = len;
maxmatch = match;
strcpy(ok,bak);
} else if (match==maxmatch) {
if (len>maxlen) {
maxlen = len;
strcpy(ok,bak);
}
}
}
maxlen = maxlen>60?60:maxlen;
for (i=0;i<maxlen;i++)
cout<<ok;
cout<<endl;
}
int main () {
init();
while (cin>>str) {
n = 0;
while (str[0]!='#') {
strcpy(dict[n++],str);
cin>>str;
}
cin.getline(str,1);
cin.getline(str,299);
decrypt();
}
return 0;
}

[/cpp]
Time makes a fool of memory
And yet my memories still shine

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Fri Aug 23, 2002 4:08 am

since your program crash my VC6 :wink: you can try this input by yourself and tell me the output of your program.

Code: Select all

HOUSE
GOOD
NOW
THING
THIS
PIGLET
MEN
TREE
BUT
WAS
AID
IN
THE
IS
IT
OTHER
BEECH
ALL
VERY
AND
FOREST
COME
OF
GRAND
ON
TRESPASSERS
FOR
PARTY
TIME
TO
MIDDLE
LIVED
THAT
THEMIDDLEOFTHEHOUSEN
HAD
#
BVTYRFMYVHRQMV MNMHRDKMTDN QMUAGERMV MFURMZVQQYRMASMNMORRPUMFDRRMN QMFURMORRPUMFDRRMINEMV MFURMZVQQYRMASMFURMSADREFMN QMBVTYRFMYVHRQMV MFURZVQQYRASFURUAGER RJFFAUVEUAGERINENBVRPRASODAXR OANDQIUVPUMUNQMFDREBNEERDEMIMA MVFM
btw, i still getting PE myself :x

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Wed Aug 28, 2002 5:34 am

i got AC (not PE).

there's a trick.

if your output have linewraps, you should omit leading blanks in the following line.

[cpp]

eg.

bla bla XXXX...XXXXXX bla bla bla <-- then linewrap
bla bla ... <-- the following line may has leading blanks, just leave out the blanks

like this

bla bla XXXX...XXXXXX bla bla bla <-- then linewrap
bla ... <-- no leading blanks
[/cpp]
Time makes a fool of memory
And yet my memories still shine

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

554 - Caesar Cypher WA!!! Help PLZ!!!!!

Post by Chok » Tue Aug 22, 2006 7:42 am

Hello all,
I've got WA several times for the Problem 554 - Caesar Cypher. Here is my code. Plz someone help me to find out my error.Wht i miss ????? Thanks in advance.

Code: Select all

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

#define MAX 100
#define MAX_S 255

char dic[MAX][30];
int n;


int find_word(char *item)
{
	int i;
	for(i=0;i<n;i++)
		if(strcmp(dic[i],item)==0)
			return 1;
	return 0;
}


int main()
{
	char buf[MAX_S],word[MAX_S],sen[MAX_S],res[MAX_S];
	int i,len,k,pos,w,s,cnt,max;
	n=0;
//	freopen("554.in","r",stdin);
	//freopen("554.out","w",stdout);
	while(1)
	{
		gets(buf);
		if(strcmp(buf,"#")==0)
			break;
		strcpy(dic[n++],buf);
	}
	while(gets(buf))
	{
		len=strlen(buf);
		if(!len)
			continue;
		int pp;
		max=-1;
		strcpy(res,buf);
		for(k=1;k<=26;k++)
		{
			w=s=cnt=0;
			for(i=0;i<len;i++)
			{
				if(buf[i]==' ')
					pos=0;
				else
					pos=buf[i]-'A'+1;
				pos=(pos+k)%27;
				if(!pos)
				{
					word[w]='\0';
					sen[s++]=' ';
					if(find_word(word))
						cnt++;
					w=0;
					word[w]='\0';
				}
				else
				{
					word[w++]='A'+pos-1;
					sen[s++]='A'+pos-1;
				}
			}
			word[w]='\0';
			sen[s]='\0';
			if(find_word(word))
				cnt++;
			if(max<cnt)
			{
				max=cnt;
				strcpy(res,sen);
				pp=k;
			}
		}
		puts(res);
		//printf("%d\n",pp);
	}
	return 0;
}

marthapfhui
New poster
Posts: 7
Joined: Sat Mar 10, 2007 7:03 pm

Post by marthapfhui » Wed May 30, 2007 5:59 pm

I am getting number of PEs. I have tried to skip the line full of spaces, removing the leading spaces, removing the trailing space, etc.

What's the trick? Any example? Thanks.

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Post by jurajz » Sat Aug 18, 2007 8:21 am

Thank's to obayashi for post. I had many PEs, with this hint I have AC.
marthapfhui wrote:I am getting number of PEs. I have tried to skip the line full of spaces, removing the leading spaces, removing the trailing space, etc.

What's the trick? Any example? Thanks.
I don't assume leading spaces in the output, only trailing. I used this method:

- first, I deleted all trailing spaces in output_string
- if length of output_string is 60 or less than 60, write whole string
- if length of output_string is 61 or more, then i:=61 and decrement i, until output_string is not a space (I assumed, that in the this part of output_string is least 1 character, that is not a space)
- string to write is from first to (i-1)-th character, but it is needful delete all trailing spaces from this part-string
- write this part-string
- delete this part-string (included previous trailing spaces) from output_string
- if length of output_string is <=60, write it, if length of output_string is still 61 and more, process recursively method described above

User avatar
krap
New poster
Posts: 4
Joined: Wed Aug 29, 2007 3:52 pm
Location: Thessaloniki, Greece
Contact:

Post by krap » Thu Aug 30, 2007 8:42 pm

Hello there,

I've come to a solution on the Ceasar's Cypher Problem and I keep getting WAs. I took care of the litle trick you guys mentioned so now in my solution, when there are linewraps I omit the leading blanks and in each line the 61st character is being wrapped. The 60th of each line is being printed weather it is a blank or something else. I get the right output for the proposed input in the problem's page (the one that the problemset provides) so I would like to ask wheather there is a particular "tricky" input that I should try.

Thanks in advance guys,
Rather be a thinker than a casuist

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Wed Sep 19, 2007 2:17 am

I followed the jurajz's hint and I got it. So according to jurajz`s instructions, we can reason this problem's judge-data is not correct. Because why we should eliminate trailing spaces? problem statement says we should divide the output into some lines which no one of them should be bigger than 60 characters. We we erase the trailing spaces it means, we are erase the output because the output has characters which deciphered into space and this elimination is ignoring them. Unfortunately we have such these problems in some of the UVa`s problems.

User avatar
krap
New poster
Posts: 4
Joined: Wed Aug 29, 2007 3:52 pm
Location: Thessaloniki, Greece
Contact:

Post by krap » Fri Sep 21, 2007 11:03 am

I believe my code is working according what he said too. But I'll check again just in case. Thank you for your contribution!
Rather be a thinker than a casuist

fryzito
New poster
Posts: 2
Joined: Wed Nov 23, 2011 3:38 am

Re: 554 - Caesar Cypher

Post by fryzito » Wed Nov 23, 2011 3:49 am

thank for their help I get AC with your help. :D

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 554 - Caesar Cypher

Post by jddantes » Tue Mar 11, 2014 6:58 pm

I'm getting Runtime Error on mine:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define SAFE printf("Safe\n");
char * shift(char * str, int k)
{
    char * decoded = (char *)malloc(251);
    int i;
    strcpy(decoded, str);

    for(i=0; decoded[i]; i++)
    {
        int num;
        if(isalpha(decoded[i]))
        {
            num = decoded[i] - 'A' + 1;
        }
        else
        {
            num = 0;
        }

        num+=k;
        if(num>26)
            num-=27;

        if(!num)
        {
            decoded[i] = ' ';
        }
        else
        {
            decoded[i]  = num + 'A' - 1;
        }


    }
    decoded[i] = 0;

    return decoded;
}

int countWords(char ** dictionary, char *str)
{
    int count = 0;
    char word[21];

    FILE * stream = fmemopen(str,strlen(str),"r");

    while(fscanf(stream, "%s",word)>0)
    {

        int i = 0;
        for(i; dictionary[i]; i++)
        {
            if(!strcmp(word,dictionary[i]))
            {
                //printf("%s matches %s in the dictionary!\n",word,dictionary[i]);
                count++;
                continue;
            }
            else
            {
                //printf("%s does not match %s in the dictionary\n",word,dictionary[i]);
            }
        }
    }
    fclose(stream);
    return count;
}

int main()
{
    char  ** dictionary = (char **)malloc(100);
    memset(dictionary,0,100);
    int i = 0;
    while(1)
    {
        char * word = (char *)malloc(22);
        //scanf("%s",word);
        fgets(word, 22, stdin);
        word[strlen(word)-1] = 0;
        if(strcmp(word,"#"))
        {
            dictionary[i] = word;
            i++;
        }
        else
        {
            break;
        }
    }

    /*

    dictionary input end

    */

    char message[252];
    fgets(message, 252, stdin);
    message[strlen(message) - 1] = 0;

    char ** decoded_strings = (char **)malloc(27);
    int k;

    int match_count[27];

    int max = 0;
    int max_words = 0;
    int index = 0;
    for(k=0; k<27; k++)
    {
        decoded_strings[k] = (char *)malloc(251);
        decoded_strings[k] = shift(message,k);
        match_count[k] = countWords(dictionary,decoded_strings[k]);

        if(match_count[k]>max)
        {
            max = match_count[k];
            max_words = 1;
            index = k;
        }
        else if(match_count[k] == max)
        {
            max_words++;
        }
    }



    if(max_words>1)
    {
        int i;
        int maxlen = 0;
        int ndex = 0;
        for(i=0; i<27; i++)
        {

            if(match_count[i] == max)
            {
                int len = strlen(decoded_strings[i]);
                if(len>maxlen)
                {
                    maxlen = len;
                    ndex = i;
                }
            }
        }

        printf("%s\n",decoded_strings[ndex]);
    }
    else if(max_words == 1)
    {
        printf("%s\n",decoded_strings[index]);
    }
    /*
    printf("Dictionary:\n");
    for(i=0; dictionary[i]; i++)
    {
        printf("%s\n",dictionary[i]);
    }

    printf("Decoded strings:\n");
    for(k=0; k<27; k++)
    {
        printf("%d %s %d\n",k,decoded_strings[k], countWords(dictionary,decoded_strings[k]));
    }*/



    //printf("Safe\n");

    /*

    end

    */


    /*
        free
    */

    // free dictionary
    for(i=0; dictionary[i]; i++)
    {
        free(dictionary[i]);
    }
    free(dictionary);
    //printf("Freed dictionary\n");
    //free decoded strings

    for(i=0; decoded_strings[i]; i++)
    {
        free(decoded_strings[i]);
    }
    //printf("Freed decoded words\n");
    //free(decoded_strings);
    return 0;
}


Post Reply

Return to “Volume 5 (500-599)”