554 - Caesar Cypher
Moderator: Board moderators
554 - Caesar Cypher
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
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
Can you tell me what's your output for the following data
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
@BEGIN_OF_TEST_CASE
THANK
YOU
FOR
YOUR
HELP
#
ABCDEFGHIJ
ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ
ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ BCDEFGHIJA
@END_OF_TEST_CASE
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]
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
And yet my memories still shine
since your program crash my VC6
you can try this input by yourself and tell me the output of your program.
btw, i still getting PE myself ![:x](./images/smilies/icon_mad.gif)
![:wink:](./images/smilies/icon_wink.gif)
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
![:x](./images/smilies/icon_mad.gif)
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]
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
And yet my memories still shine
554 - Caesar Cypher WA!!! Help PLZ!!!!!
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.
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;
}
-
- New poster
- Posts: 7
- Joined: Sat Mar 10, 2007 7:03 pm
Thank's to obayashi for post. I had many PEs, with this hint I have AC.
- 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
I don't assume leading spaces in the output, only trailing. I used this method: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.
- 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
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,
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
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.
Re: 554 - Caesar Cypher
thank for their help I get AC with your help. ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
Re: 554 - Caesar Cypher
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;
}