10008 - What's Cryptanalysis?

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

Moderator: Board moderators

chaojinn
New poster
Posts: 6
Joined: Fri Apr 19, 2002 12:34 pm

10008 - What's Cryptanalysis?

Post by chaojinn » Tue Jul 30, 2002 8:03 am

[cpp]
#include "iostream.h"
#include "stdio.h"
#include "string.h"

char str[800];
int list[26];

void init()
{
int i;
for(i=0;i<26;i++)
list=0;
}

void input()
{
int i,l,n,j;
cin>>n;
for(j=0;j<n;j++)
{
gets(str);
l=strlen(str);
for(i=0;i<l;i++)
{
if((str>='A')&&(str<='Z'))
list[str-'A']++;
if((str>='a')&&(str<='z'))
list[str-'a']++;
}
}
}

void output()
{
int max,maxpos,i,j;
max=-1;
for(i=0;i<26;i++)
{
for(j=0;j<26;j++)
if(list[j]>max)
{
max=list[j];
maxpos=j;
}
if(max!=0)
cout<<char(maxpos+'A')<<' '<<max<<endl;
list[maxpos]=0;
max=-1;
}
}


void main()
{
init();
input();
output();
}

:evil:
[/cpp]

karl
New poster
Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

10008 - Need some test cases

Post by karl » Wed Nov 06, 2002 11:36 am

Hi, folks :D


I'm very disappointed because of getting always WA in prob 10008.
May someone send my some test cases please or any hints?

For input I use a string of length 20000. Is that enough?

Any idea?


Thank you very much!


Karl

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub » Thu Nov 07, 2002 6:16 am

Code: Select all

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

#define MAX 1000000

char a[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int f[27];
char s[MAX];

int cmpf(const void *a, const void *b)
{
	char *x = (char *)a;
	char *y = (char *)b;

	if(f[*x-65]!=f[*y-65])
		return f[*y-65] - f[*x-65];

	return *x - *y;
}

int main()
{
	
	int n,i,j;
/*	freopen("10008.txt","r",stdin);  */
	while(scanf("%d",&n)==1)
	{	
		for(i=0; i<26; i++)
			f[i] = 0;

		gets(s);
		for(i=0; i<n; i++)
		{
			gets(s);
			for(j=0; s[j]; j++)
			{
				if(s[j]>=97 && s[j] <= 122)
				f[s[j]-97]++;
				if(s[j]>=65 && s[j] <= 90)
				f[s[j]-65]++;
			}
		}
		qsort((void *)a,26,sizeof(a[0]),cmpf);
		for(i=0; i<26; i++)
			if(f[a[i]-65]>0)
				printf("%c %d\n",a[i],f[a[i]-65]);
	}
	return 0;
}

abyssinian
New poster
Posts: 13
Joined: Wed Jan 01, 2003 1:25 pm

10008 cryptanalysis...need more input 'n output sample

Post by abyssinian » Wed Jan 01, 2003 1:51 pm

:( confused.....need more samples of input and output....
i got it right on my computer but received "wrong answer" from online judge??...........what's cryptal?? what's wrong??

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

char line[100];
int f[26],j;

int main(){
unsigned int max,baris,i;
char huruf[26];

for(i='A';i<='Z';i++){
huruf[j++]=i;
}

while(scanf("%d",&baris)==1){
max=0;
for(i=0;i<26;i++){f=0;}

while(baris!=0){
fflush(stdin);
gets(line);
for(i=0;line!='\0';i++){
for(j=0;j<26;j++){
if(toupper(line)==huruf[j]){
f[j]++;
if (f[j]>max) max=f[j];
break;
}
}
}
baris--;
}

while(max!=0){
for(j=0;j<=26;j++){
if(f[j]==max) printf("%c %d\n",huruf[j],f[j]);
}
max--;
}

}

return 0;
}

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Thu Jan 02, 2003 8:19 pm

Using fflush is wrong. fflush is only used for ensuring that all data written to a stream is really written to disk (or at least to kernel buffers...). You cannot use fflush to consume the newline character after the number on the first line. Instead, you could simply do
[c]gets(line);[/c] right after scanf.

Other things you might want to watch out for is lines longer than 100 characters. I don't know how long the lines are in the judge input but there is no limit mentioned in the specification as far as I can see.

See for example http://www.gnu.org/manual/glibc-2.2.5/h ... ffers.html or type man fflush on any UNIX-like operating system for more info.

Also, when posting please use the C button, so the code is readable.

abyssinian
New poster
Posts: 13
Joined: Wed Jan 01, 2003 1:25 pm

Post by abyssinian » Fri Jan 03, 2003 10:09 am

:) thank you ......
i've tried to eliminate fflush....n i got accepted..
thanx very much for your advice

bye

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Re: Very confuce about 10008

Post by zsepi » Tue Jan 14, 2003 11:27 pm

For the TLE: you should only change the value of the max when you came upon a character, which is a letter... like this:
Hisoka wrote:I dont know Why I got TLE if I use this program in c:
[c]
for(j=0;kalimat[j];j++)
{
if(isalpha(kalimat[j])) {
banyak[toupper(kalimat[j])-'A']++;
if(banyak[toupper(kalimat[j])-'A']>max)
max=banyak[toupper(kalimat[j])-'A'];
}
}
[/c]
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Jan 30, 2003 2:21 am

Hello, ... your 2nd program might be accessing an invalid index. That might be why it got WA.

Try to trace with k = 1. The first if statement below will be comparing angka[-1] and angka[0]. And then it depends what is currently stored in angka[-1] ... you might end up swapping your huruf and angka because it is less than angka[0].

-turuthok-

[c]for(i=0;i<k;i++)
{
for(j=k-1;j>=i;j--)
{
if(angka[j-1]<angka[j])
{
tukar_angka(&angka[j-1],&angka[j]);
tukar_huruf(&huruf[j-1],&huruf[j]);
}
else
if(angka[j-1]==angka[j]&&huruf[j-1]>huruf[j])
tukar_huruf(&huruf[j-1],&huruf[j]);
}
}
[/c]

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Sat Mar 29, 2003 7:03 pm

hello.

look into the sorting part. you need to "swap" the counter as well, or better, swap the whole objects.

hope this helps.

Professor_Of_Love
New poster
Posts: 9
Joined: Tue Apr 01, 2003 10:03 pm
Location: Dhaka, Bangladesh

Post by Professor_Of_Love » Sat Apr 05, 2003 6:48 am

Thankssssss Adil vaiya.... I just wrote another swap function for the characters and got AC. Thanks again! Have a nice day! :lol:

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

10008

Post by awik_10 » Tue Jun 10, 2003 12:44 pm

i don't know why i got wa on my code
thank you, i'll wait for your replies.
Last edited by awik_10 on Fri Jun 20, 2003 12:39 pm, edited 1 time in total.

hager
New poster
Posts: 10
Joined: Wed Jan 01, 2003 4:26 am
Location: Ume

Post by hager » Tue Jun 17, 2003 1:30 pm

I haven't tried your program, but you shouldn't use fflush(). It is not meant for consuming the newline character, but rather flushing output buffers to assure that they are written to kernel buffers. One way you could do it is:
[c]gets(temp);[/c]
or by looping:
[c]while (getchar() != '\n') ;[/c]
By replacing fflush(stdin); with one of the above examples your program is likely to work.

Best regards

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

Post by awik_10 » Fri Jun 20, 2003 12:37 pm

thank you anyway, i've got an acc. if you have time, would you explain more about fflush()? :-?
best regards,
awik :P

hager
New poster
Posts: 10
Joined: Wed Jan 01, 2003 4:26 am
Location: Ume

Post by hager » Mon Jun 23, 2003 12:16 pm

You could check out this thread where the use of fflush() is discussed. http://acm.uva.es/board/viewtopic.php?t=2011&highlight=
It also contains a link to an online manual for the GNU C Library.

Best regards

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. » Sun Jun 29, 2003 8:25 am

do you know what makes my program taking to much time?
Last edited by r.z. on Sun Jun 29, 2003 12:08 pm, edited 1 time in total.

Post Reply

Return to “Volume 100 (10000-10099)”