10008 - What's Cryptanalysis?

[chaojinn]

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


[/cpp]

[karl]

Hi, folks


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]

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]

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]

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]

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

bye

[zsepi]

For the TLE: you should only change the value of the max when you came upon a character, which is a letter... like this:

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]

[turuthok]

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]

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]

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

[awik_10]

i don't know why i got wa on my code
thank you, i'll wait for your replies.

[hager]

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]

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

[hager]

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

do you know what makes my program taking to much time?