10338 - Mischievous Children

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

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Wed Sep 18, 2002 11:42 am

Found a silly error in the selection sort portion of the code- [str[j]<str[index]] not [str[j]<min]-...still WA,though, with double and long long used for the variable num and the factorial function.

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

Post by Professor_Of_Love » Wed Apr 02, 2003 8:44 pm

Why I always get WA????????

[c]#include<stdio.h>
#define SIZE 20

struct letter{
char chr;
int freq;
};

struct letter in[SIZE];
char str1[20000];
unsigned long long i,j,flag,countStruct,n,k,sum,cur;

unsigned long long fact(unsigned long long d)
{
unsigned long long s,b;
s=1;
for(b=1;b<=d;b++)
s *= b;
return s;
}

void swap(char *a, char *b)
{
*a = *a + *b - (*b=*a);
}

void initAll()
{
int i;
for(i=0;i<SIZE;i++)
in.chr=-1,in.freq=0;
}

void main(void)
{
scanf("%lld",&n);
k=0;
while(k<n)
{
scanf("%s",str1);
countStruct=0,initAll();
for(i=0;i<strlen(str1);i++)
{
flag=0;
for(j=0;j<=countStruct;j++)
{
if(in[j].chr==str1)
{
in[j].freq++;
flag=1;
break;
}
}
if(flag==0)
in[countStruct].chr=str1,in[countStruct].freq=1,countStruct++;
}
if(strlen(str1)==countStruct)
cur = fact(strlen(str1));
else
{
cur=0;
for(i=0;i<countStruct;i++)
if(in.freq>1)
cur += fact(in.freq);
cur = fact(strlen(str1))/cur;
}
printf("Data set %lld: %lld\n",k+1,cur);
k++;
}
}[/c]

Thanks!

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

WA

Post by bobi1978 » Tue Jul 22, 2003 2:23 pm

I can't get ACCEPTED on this easy problem.
My formula is: n!/(k1!*k2!*...*km!).
Any special case?
What is output if there is a blank line (word with length 0)?
[/cpp]

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Sat Jul 26, 2003 10:46 am

Perhaps you should see problem 160 Factor and Factorials. There's a technique to define a factorial by factorizing them into prime factors.
for instance 5! becomes 311 (means 5! = 2*2*2*3*5 (three twos,one three and one five))

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Thu Aug 28, 2003 10:37 am

it.s wrong

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Thu Aug 28, 2003 10:12 pm

Thanks but i got it accepted a long time ago. My conception was wrong when i posted that. Thanks again. :) :) :)

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Wed Sep 24, 2003 3:00 pm

I solved it finally...letters don't necessarily repeat after each other; Found that the hard way.

Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:

10338

Post by Rony » Sun Jul 04, 2004 2:16 pm

Code removed after AC

Gazi Shaheen Hossain
New poster
Posts: 7
Joined: Fri Sep 03, 2004 6:47 pm

10338 compile error

Post by Gazi Shaheen Hossain » Mon Sep 06, 2004 5:29 pm

[cpp]
why it gives me compile error?
tell me please

#include <stdio.h>
#include <string.h>
void main()
{
long double fact[21],f=1,i,ans;
char word[22];
int l;
unsigned long set=1;
for(i=1;i<=20;i++)
{
f=f*i;
fact=f;
}

while(scanf("%s",word)==1)
{
int frec[26]={0};
l=strlen(word);
i=-1;
while(word[++i])
frec[word-65]++;
ans=fact[l];
for(i=0;i<26;i++)
if(frec>1)
ans=ans/fact[frec];
printf("Data set %lu: %.0Lf\n",set++,ans);
}
}
[/cpp]

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Mon Sep 06, 2004 5:53 pm

Hi Gazi Shaheen Hossain, i compile with gcc in linux red hat, and in this lines
12, 20,21,24,25 the index is not a integer that the reason for the compile error
Hope it helps
Keep posting :D

P.S. if change the declaration of i to int give WA. if you want some inputs posted here your I/O and I give you the anwser of my AC code.

TWEmp
New poster
Posts: 7
Joined: Tue Jan 21, 2003 4:52 am
Location: Hong Kong
Contact:

10338 WA...

Post by TWEmp » Sat Oct 23, 2004 6:52 pm

Maybe I'm irresponsible, but I'd used the n!/(n1!*n2!...) algorithm and got WA. I don't dare to use long long so I check if the range was exceeded then pause and just start dividing, and once it's indivisible with a certain number then build up the remaining factorial, and so forth:

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned long int o;
int charcount[26];

int main(int args, char **argv) {
int i, j, t, s, L, N;
unsigned long int r;
char in[20];
scanf("%d", &N);
for (i = 0; i < N; i++) {
for (j = 0; j < 26; j++) charcount[j] = 0;
scanf("%s", in);
L = strlen(in);
for (j = 0; j < L; j++) charcount[(in[j] - 65)]++;
r = 1;
j = 1;
do {
r *= j;
j++;
} while ((j <= L) && (4294967296 / r >= j));
t = j;
for (j = 0; j < 26; j++) {
s = 1;
while (s <= charcount[j]) {
if (r % s == 0) {
r /= s;
s++;
}
else while ((t <= L) && (4294967296 / r >= t)) {
r *= t;
t++;
}
}
}
while (t <= L) {
r *= t;
t++;
}
printf("Data set %d: %ld\n", i+1, r);
}
return 0;
}
[/c]

Actually I read earlier posts but I can't figure it out. Maybe somebody provide some testcases for me... :-? [/c]

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sat Oct 23, 2004 9:24 pm

hi,
Each word will have at most 20 letters.
then char in[20]; should be char in[21]; ( one extra for 0 termination, blah blah)

Code: Select all

printf("Data set %d: %ld\n", i+1, r);
well, unsigned long's should be printed using %lu, isn't it?
TWEmp wrote:294967296 / r
Now, 294967296 = 2^32, which does not fit in even unsigned long, so...
1) it should be 294967295 ( 2^32-1) OR
2) cast 294967296 to long long ( no need of big guts to use long long here :) ) using 294967296ll [ 294... ell,ell] instead of 294967296.
thank you.
Istiaque Ahmed [the LA-Z-BOy]

TWEmp
New poster
Posts: 7
Joined: Tue Jan 21, 2003 4:52 am
Location: Hong Kong
Contact:

Post by TWEmp » Sun Oct 24, 2004 5:27 pm

the LA-Z-BOy wrote:hi...
Thank you very much. I got accepted. :)

p!ter
New poster
Posts: 11
Joined: Thu Nov 18, 2004 8:55 pm

10338 -->Why WA

Post by p!ter » Sun Dec 26, 2004 5:23 pm

Hi,
Can enyone tell me what is wrong with my code. Output seems Ok.

Code: Select all

Code removed after ACC..
THANKS!!
Last edited by p!ter on Sat Jan 15, 2005 5:50 pm, edited 1 time in total.

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Mon Dec 27, 2004 4:23 am

Code: Select all

:D perdon
Last edited by lord_burgos on Mon Jan 17, 2005 9:04 am, edited 1 time in total.

Post Reply

Return to “Volume 103 (10300-10399)”