324 - Factorial Frequencies

[b3yours3lf]

Why I always get WA?
Can someone help me, please.
#include<stdio.h>

void main(void)
{
int arr[1000],fak,i,j,num[10];
int temp,sisa=0;
while(scanf("%d",&fak)==1 && fak!=0)
{
for(i=0;i<1000;i++) arr=0;
arr=1;
for(i=1;i<=fak;i++)
{
for(j=999;j>=0;j--)
{
temp=(arr[j]*i)+sisa;
if(temp>=10)
{
arr[j]=temp%10;
sisa=temp/10;
}
else
{
arr[j]=temp;
sisa=0;
}
}
arr[j]=sisa;
sisa=0;
}
for(i=0;i<10;i++) num=0;
i=0;
while(arr==0) i++;
while(i<1000)
{
num[arr]++;
i++;
}
printf("%d! --\n",fak);
printf(" (0)%5d (1)%5d (2)%5d (3)%5d (4)%5d\n",num[0],num[1],num[2],num[3],num[4]);
printf(" (5)%5d (6)%5d (7)%5d (8)%5d (9)%5d\n",num[5],num[6],num[7],num[8],num[9]);
}
}
[c][/c]

[arc16]

have you test it before submit it?
this is the output your program (in Visual C++):

Code: Select all

10
0! --
 (0)    0 (1)    0 (2)    0 (3)    0 (4)    0
 (5)    0 (6)    0 (7)    0 (8)    0 (9)    0
100
0! --
 (0)    0 (1)    0 (2)    0 (3)    0 (4)    0
 (5)    0 (6)    0 (7)    0 (8)    0 (9)    0
366
0! --
 (0)    0 (1)    0 (2)    0 (3)    0 (4)    0
 (5)    0 (6)    0 (7)    0 (8)    0 (9)    0
5
0! --
 (0)    0 (1)    0 (2)    0 (3)    0 (4)    0
 (5)    0 (6)    0 (7)    0 (8)    0 (9)    0

i haven't take a deep look into your program, but i think the problem is in your multiplication section, especially in here:

[c]
for(j=999;j>=0;j--)
{
temp=(arr[j]*i)+sisa;
[/c]

maybe you could explain more about your algorithm?

btw, your output format also is not correct

[soyoja]

I believe that my solution is correct...
I use my own BigInt class... calculate factorials and count each number.
But I got WA again and again.. -_-
So I want to confirm my solution's output.
If you have accepted solution, then please tell me each output from below input data.

360
361
362
363
364
365
366

thanks....

[Dominik Michniewski]

My accepted solution says: (it's get from screen, so input and output are mismatched .... )

Code: Select all

360
360! --
    (0)  166   (1)   55   (2)   62   (3)   75   (4)   73
    (5)   73   (6)   65   (7)   65   (8)   70   (9)   62
361
361! --
    (0)  157   (1)   62   (2)   71   (3)   80   (4)   69
    (5)   72   (6)   66   (7)   71   (8)   65   (9)   56
362
362! --
    (0)  161   (1)   67   (2)   72   (3)   57   (4)   72
    (5)   69   (6)   66   (7)   77   (8)   60   (9)   70
363
363! --
    (0)  155   (1)   65   (2)   83   (3)   77   (4)   58
    (5)   57   (6)   73   (7)   75   (8)   61   (9)   70
364
364! --
    (0)  158   (1)   69   (2)   61   (3)   74   (4)   74
    (5)   74   (6)   59   (7)   70   (8)   69   (9)   68
365
365! --
    (0)  166   (1)   76   (2)   54   (3)   64   (4)   72
    (5)   69   (6)   69   (7)   60   (8)   70   (9)   79
366
366! --
    (0)  160   (1)   93   (2)   58   (3)   60   (4)   74
    (5)   81   (6)   58   (7)   64   (8)   59   (9)   74

DM

[soyoja]

Ok.. Thanks for your answer.

I checked my answer was different to yours. So I request another data.

over 360.. is too big.. So I'm very hard to debug.

Please say to me these input data's answer...

50
100
150
200

Thanks..

[afonsocsc]

Code: Select all

50! --
   (0)   19   (1)    7   (2)    3   (3)    6   (4)    7
   (5)    2   (6)    9   (7)    5   (8)    5   (9)    2
100! --
   (0)   30   (1)   15   (2)   19   (3)   10   (4)   10
   (5)   14   (6)   19   (7)    7   (8)   14   (9)   20
150! --
   (0)   51   (1)   20   (2)   25   (3)   19   (4)   30
   (5)   32   (6)   21   (7)   22   (8)   21   (9)   22
200! --
   (0)   76   (1)   26   (2)   54   (3)   41   (4)   35
   (5)   25   (6)   29   (7)   35   (8)   23   (9)   31

By the way, you can use bc (if you're using linux or any unix based) to check for the factorials (and much more), just go to the man page and search for factorial...

[soyoja]

Wow! Eureka!

I use your data, and debuging and debuging again...

( In fact, it's very useful to me )

At last, I found small bug in my BigInt class....

It's concern about carry problem... -_-;;

As a result, I solved this problem and got Accept...

Very very thank you, Dominik Michniewski & afonsocsc

[Zhao Le]

I hava sucessfully solved the 623
and i think it also easy to solve 324
but WA?
why?
i just have some change from 623
[cpp]#include <iostream.h>

#define Max 1135

int S[Max]; // Make s[0]=1 else s=0 i>=1
int Count[10]; // 0-9 save the result

void CheckCarry()
{
int i;
for(i=0;i<Max;i++)
while(S>9)
{
S-=10;
S[i+1]+=1;
}
}

void C(int n)
{
int k;
for(;n>0;n--)
{
k=0;
int i;
for(i=0;i<Max;i++)
{
if(S>0) k=i+1;
}
for(i=0;i<k;i++)
S*=n;
CheckCarry();
}
}

void ClearState()
{
S[0]=1;
int i;
for(i=1;i<Max;i++)
S=0; // Reset the S[]
for(i=0;i<10;i++)
Count=0;
}

void main()
{
int n,k;
while(1)
{
ClearState();
cin>>n;
if(n==0) break;
C(n);
int i;
for(i=Max-1;i>=0;i--)
if(S>0)
{
k=i;
break;
}
cout<<n<<"! --"<<endl;
for(i=k;i>=0;i--)
Count[S]++;
for(i=0;i<10;i++)
cout<<"("<<i<<")"<<"\t"<<Count<<"\t";
}
}[/cpp]

[Zhao Le]

The output format isn't too critical, but you should make your program produce results that look similar to those shown below.

i think the acm tester has some bugers,
i change the format and got P.E.
Here is my changed code.

[cpp]#include <iostream.h>

#define Max 1135

int S[Max]; // Make s[0]=1 else s=0 i>=1
int Count[10]; // 0-9 save the result

void CheckCarry()
{
int i;
for(i=0;i<Max;i++)
while(S>9)
{
S-=10;
S[i+1]+=1;
}
}

void C(int n)
{
int k;
for(;n>0;n--)
{
k=0;
int i;
for(i=0;i<Max;i++)
{
if(S>0) k=i+1;
}
for(i=0;i<k;i++)
S*=n;
CheckCarry();
}
}

void ClearState()
{
S[0]=1;
int i;
for(i=1;i<Max;i++)
S=0; // Reset the S[]
for(i=0;i<10;i++)
Count=0;
}

void main()
{
int n,k;
while(1)
{
ClearState();
cin>>n;
if(n==0) break;
C(n);
int i;
for(i=Max-1;i>=0;i--)
if(S>0)
{
k=i;
break;
}
cout<<n<<"! --"<<endl;
for(i=k;i>=0;i--)
Count[S]++;
cout.width(5);
for(i=0;i<5;i++)
cout<<" ("<<i<<")"<<" "<<Count;
cout<<endl;
for(i=5;i<10;i++)
cout<<" ("<<i<<")"<<" "<<Count[i];
cout<<endl;

}
}[/cpp]

[do_ob]

Hi,Are there anyone can tell me what is wrong with my code ? i got Compile error , but they were compiled with successful (withou any warnning) in my computer .... here is code

Thanks ALOT !

Problem 324 :

/* using big number */

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXDIGITS 800

typedef struct bignum bignum;
struct bignum{
int signbit;
char digits[MAXDIGITS];
int lastdigit;
};

int count[10];
int last;
bignum mem[367];


void int_to_bignum(int n,bignum *bn){
if(n >= 0)
bn->signbit = 1;
else {
bn->signbit = -1;
n = abs(n);
}
sprintf(bn->digits,"%d",n);
bn->lastdigit = strlen(bn->digits);
}


/* *************************************************************** */
/* Multiply two big integer */
/* Input : Three big integer pointer a,b,c */
/* where a & b is argument of multiplication */
/* and c is the result. */
/* Return : Number of borrow */
/* *************************************************************** */
void multiply_bignum(bignum *a, bignum *b, bignum *c)
{
long int n_d;
register long int i,j,k;
short int num1[MAXDIGITS],num2[MAXDIGITS],of=0,res[MAXDIGITS]={0};
n_d=((a->lastdigit) < (b->lastdigit))? (b->lastdigit): (a->lastdigit);
n_d++ ;
for(i=0,j= (a->lastdigit)-1;i< (a->lastdigit) ;i++,j--)
num1=(a->digits[j])-48;
for(i=0,j=(b->lastdigit)-1;i< (b->lastdigit) ;j--,i++)
num2=(b->digits[j])-48;
res[0]=0;
for(j=0;j< (b->lastdigit);j++) {
for(i=0,k=j;i< (a->lastdigit) || of;k++,i++) {
if(i<(a->lastdigit)) res[k] += num1 * num2[j] + of;
else res[k] += of;
of=res[k]/10; res[k]=res[k]%10;
}
}
for(i=k-1,j=0;i>=0;i--,j++)
c->digits[j]=res+48;
c->digits[j]='\0';
c->lastdigit=k;
c->signbit = a->signbit*b->signbit;
}

void layout(int n)
{
for(int i = 0;i < strlen(mem[n].digits);i++)
count[mem[n].digits-'0']++;
cout << n << "! --" << endl;
for(int i = 0;i < 5;i++)
printf(" (%d)%5d",i,count);
printf("\n");
for(int i = 5;i < 10;i++)
printf(" (%d)%5d",i,count);
printf("\n");
}

void get_factorial(int n)
{
if(n < last)
goto print;

for(int i = last;i <=n;i++){
int_to_bignum(i,&mem[0]);
multiply_bignum(&mem[i-1],&mem[0],&mem);
}
print:
layout(n);
}

int main()
{
int n;
int_to_bignum(1,&mem[1]);
int_to_bignum(2,&mem[2]);
last = 3;
while(cin >> n) {
if(n == 0)
break;
for(int i = 0;i < 10;i++)
count = 0;
get_factorial(n);
}
return 0;
}

and Problem 495 :
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAXDIGITS 500
#define max(a,b) ((a>b)?a:b)
#define D(x)

class bignum {

public :
char digits[MAXDIGITS];
int sign;
int last_digit;

public :
// constructor
bignum() {
int_to_bignum(0);
}

bignum(int n) {
int_to_bignum(n);
}

bignum(bignum *n) {
strcpy(this->digits,n->digits);
this->sign = n->sign;
this->last_digit = n->last_digit;
}

void int_to_bignum(int n){
if(n >= 0)
this->sign = 1;
else {
this->sign = -1;
n = abs(n);
}
sprintf(this->digits,"%d",n);
this->last_digit = strlen(this->digits);
}

void str_to_bignum(char *str){
int i;
if(str[0] == '-'){
this->sign = -1;
i = 1;
}
else {
this->sign = 1;
i = 0;
}
strcpy(this->digits,&str);
this->last_digit = strlen(this->digits);
}

void print(){
if(this->sign == -1)
cout << "-";

for(unsigned int i = 0;i < strlen(this->digits);i++)
cout << digits[i];
}
};

bignum mem[5000];
int last;


/* *******************************************
* Compare two big integer *
* Input : Two big integer pointer a,b *
* Return : *
* 0,1 or -1, *
* 0 for a == b *
* 1 for a > b *
* -1 for a < b *
* *******************************************/
int compare_bignum(bignum *a, bignum *b)
{
if ((a->sign == -1) && (b->sign == 1))
return -1;
if ((a->sign == 1) && (b->sign == -1))
return 1;
if (b->last_digit > a->last_digit)
return (1 * b->sign);
if (a->last_digit > b->last_digit)
return (1 * a->sign);
for (int i = 0; i < a->last_digit; i++ ) {
if (a->digits[i] > b->digits[i])
return(1 * a->sign);
if (b->digits[i] > a->digits[i])
return(1 * b->sign);
}
return 0;
}

int subtract_bignum(bignum *a,bignum *b,bignum *c);

/* **************************************************************
* Add two big integer *
* Input : Three big integer pointer a,b,c *
* where a & b is argument of addition and c is the result. *
* Return : Number of carry *
* **************************************************************/
int sum_bignum(bignum *a,bignum *b,bignum *c)
{
int carry,n_carry;

if(c == NULL)
c = new bignum(0);

if(a->sign == b->sign)
c->sign = a->sign;
else {
if(a->sign == -1) {
a->sign = 1;
n_carry = subtract_bignum(b,a,c);
a->sign = -1;
}
else {
b->sign = 1;
n_carry = subtract_bignum(a,b,c);
b->sign = -1;
}
return n_carry;
}

if(a->last_digit < b->last_digit)
return sum_bignum(b,a,c);

int k = c->last_digit = a->last_digit+1;
c->digits[k--] = '\0';

int i,j;
carry = n_carry = 0;
D(cout << a->digits << " + " << b->digits << " = ");
for(i = b->last_digit-1 , j = a->last_digit-1; i >= 0; i--,j--){
carry = b->digits[i]-'0' + a->digits[j]-'0' + carry;
c->digits[k--] = (carry%10)+'0';
carry /= 10;
if(carry)
n_carry++;
}
for(;j >= 0;j--) {
carry = a->digits[j]-'0' + carry;
c->digits[k--] = (carry % 10)+'0';
carry /= 10;
if(carry)
n_carry++;
}
if(carry)
c->digits[k] = carry+'0';
else{
char str[MAXDIGITS];
strcpy(str,&c->digits[1]);
strcpy(c->digits,str);
}
//c->last_digit = c->last_digit - k - 1;
c->last_digit = strlen(c->digits);
D(cout << c->digits << endl);
return n_carry;
}

/* ****************************************************************
* Subtract two big integer *
* Input : Three big integer pointer a,b,c *
* where a & b is argument of subtraction and c is the result.*
* Return : Number of borrow *
* ****************************************************************/
int subtract_bignum(bignum *a,bignum *b,bignum *c)
{
int borrow,n_borrow;

if(c == NULL)
c = new bignum(0);

c->sign = 1;
if( a->sign == -1 || b->sign == -1) {
b->sign = (-1) * b->sign;
n_borrow = sum_bignum(a,b,c);
b->sign = (-1) * b->sign;
return n_borrow;
}

if(compare_bignum(a,b) == -1) { // a < b
n_borrow = subtract_bignum(b,a,c);
c->sign = -1;
return n_borrow;
}
// a > b
int k = c->last_digit = max(a->last_digit,b->last_digit);
n_borrow = borrow = 0;
c->digits[k--] = '\0';
int i,j,temp;
for(i = a->last_digit-1,j = b->last_digit-1;j >= 0;i--,j--) {
temp = a->digits[i]-'0' - (b->digits[j]-'0' + borrow);
if(temp < 0) {
temp += 10;
borrow = 1;
n_borrow++;
}
else
borrow = 0;
c->digits[k--] = temp + '0';
}
while(borrow) {
temp = a->digits[i--] - borrow - '0';
if(temp < 0){
temp += 10;
borrow = 1;
n_borrow++;
}
else
borrow = 0;
c->digits[k--] = temp + '0';
}
for(;i >= 0;i--)
c->digits[k--] = a->digits[i];
for(i = 0;!(c->digits[i]-'0');i++);
c->last_digit = c->last_digit - i;
if(i == a->last_digit)
strcpy(c->digits,"0");
else {
char str[MAXDIGITS];
strcpy(str,&c->digits[i]);
strcpy(c->digits,str);
}
return n_borrow;
}

void resolve(int n)
{
if(n <= last)
goto print;

int i;
for(i = last;i < n;i++){
sum_bignum(&mem[i-2],&mem[i-1],&mem[i]);
//print_bignum(mem[i]);
D(cout << i+1 << " : ";mem[i].print();cout << endl);
}
last = n;
print:
mem[n-1].print();
return;
}

int main()
{
int n; /* n <= 5000 */
mem[0] = new bignum(1);
mem[1] = new bignum(1);
last = 2;
while(cin >> n) {
cout << "The Fibonacci number for " << n;
cout << " is ";
resolve(n);
cout << endl;
}
return 0;
}

[sjn]

Code: Select all

p324.cpp: In function `void layout(int)':
p324.cpp:67: use of `count' is ambiguous
p324.cpp:14:   first declared as `int count[10]' here
D:/Program Files/MinGW/include/c++/3.2/bits/stl_algo.h:390:   also declared as
   `std::iterator_traits<_Iterator>::difference_type std::count(_InputIter,
   _InputIter, const _Tp&)' here
p324.cpp:70: use of `count' is ambiguous
p324.cpp:14:   first declared as `int count[10]' here
D:/Program Files/MinGW/include/c++/3.2/bits/stl_algo.h:390:   also declared as
   `std::iterator_traits<_Iterator>::difference_type std::count(_InputIter,
   _InputIter, const _Tp&)' here
p324.cpp:73: use of `count' is ambiguous
p324.cpp:14:   first declared as `int count[10]' here
D:/Program Files/MinGW/include/c++/3.2/bits/stl_algo.h:390:   also declared as
   `std::iterator_traits<_Iterator>::difference_type std::count(_InputIter,
   _InputIter, const _Tp&)' here
p324.cpp: In function `int main()':
p324.cpp:100: use of `count' is ambiguous
p324.cpp:14:   first declared as `int count[10]' here
D:/Program Files/MinGW/include/c++/3.2/bits/stl_algo.h:390:   also declared as
   `std::iterator_traits<_Iterator>::difference_type std::count(_InputIter,
   _InputIter, const _Tp&)' here

Try to use GCC or MinGW to compile your code
hope useful!

[Ghust_omega]

Hi! I got AC(P.E.) and i dont why please help me here is mi ouput format the way i print the numbers i not put all the code only the code for the ouput.Digit[] is the array where i have all the numbers of the result, i sure that is fine only i wanna know how is the ouput
thanks


[c]
while (scanf("%d",&a) == 1) {
if(!a)
break;
for(i=0;i<10;i++){
Digit = count_digit(&Fac[a],i);
}
printf("%d! --\n",a);
printf(" (0)%5d (1)%5d (2)%5d (3)%5d (4)%5d\n",Digit[0],Digit[1],Digit[2],Digit[3],Digit[4]);
printf(" (5)%5d (6)%5d (7)%5d (8)%5d (9)%5d\n",Digit[5],Digit[6],Digit[7],Digit[8],Digit[9]);

}
Here some ouput take from the monitor
300
300! --
(0) 121 (1) 42 (2) 66 (3) 54 (4) 53
(5) 59 (6) 66 (7) 54 (8) 51 (9) 49
360
360! --
(0) 166 (1) 55 (2) 62 (3) 75 (4) 73
(5) 73 (6) 65 (7) 65 (8) 70 (9) 62
45
45! --
(0) 13 (1) 7 (2) 4 (3) 5 (4) 4
(5) 5 (6) 8 (7) 4 (8) 3 (9) 4
360
360! --
(0) 166 (1) 55 (2) 62 (3) 75 (4) 73
(5) 73 (6) 65 (7) 65 (8) 70 (9) 62
100
100! --
(0) 30 (1) 15 (2) 19 (3) 10 (4) 10
(5) 14 (6) 19 (7) 7 (8) 14 (9) 20
200
200! --
(0) 76 (1) 26 (2) 54 (3) 41 (4) 35
(5) 25 (6) 29 (7) 35 (8) 23 (9) 31
250
250! --
(0) 103 (1) 43 (2) 56 (3) 40 (4) 34
(5) 39 (6) 32 (7) 53 (8) 53 (9) 40
8
8! --
(0) 2 (1) 0 (2) 1 (3) 1 (4) 1
(5) 0 (6) 0 (7) 0 (8) 0 (9) 0
13
13! --
(0) 4 (1) 0 (2) 3 (3) 0 (4) 0
(5) 0 (6) 1 (7) 1 (8) 1 (9) 0



[/c]

[techna]

hi

my code is working for all possible input types..i am not able to come to terms with the output format..for 324 problem..plz help me..and i am getting a WA..

[murkho]

Hi, i am also feeling trouble with this problem. I think my output for input is ok. But i don't find out the reason for WA.

Here is my code.
pls tell me the fault..



//N0: 324..
//Name: Factorial Frequencies
//date:03.03.05...


#include <stdlib.h>
#include <stdio.h>
#include<string.h>
#define N 8000

//void itoad(int num,char *p);
void itoa(int num,char *p);
void strrevd(char *p);

int main(void)
{
char str[N], *p,*r;
char ch;
int val;
char c[100];
long int a,b,carry,i;
int n,rem;
int fre[10000];
//freopen("c:\\324.txt","r",stdin);

while(scanf("%d",&n) ==1 && n)
{
//index = 0;
str[0] = '1';
str[1] = NULL;


for(i = 2;i<=n;i++)
{
p = str;
a = i;
carry = 0;
while(*p)
{
//ch = *p;
a=i;
b = *p -48;
a = b*a +carry;
rem = a%10;
carry = a/10;
*p = rem +48;
p++;
}
*p = NULL;
if(carry)
{
//r = c;
itoa(carry,c);
//strcpy(c,itoad(carry,c));
strrevd(c);
//strcpy(c,strrevd(c));
//strrev(c);
strcat(str,c);
}

}
*(p+2) = NULL;

p = str;
for( i = 0;i<10;i++)
fre = 0;
while(*p)
{
val = *p - 48;
fre[val]++;
p++;
}
printf("%d! --\n ",n);
//printf(" ");
for(i = 0;i<10;i++)
{
printf("(%d) ",i);
printf("%3d ",fre);
if(i ==4)
printf("\n ");
}
printf("\n");
}

return 0;



}







void strrevd(char *p);
void itoa(int num,char *p)
{
int i = 0;
while(num >0)
{
*(p+i) = num%10 + 48;
num = num/10;
i++;
}
*(p+i) = NULL;
strrevd(p);

}
void strrevd(char *p)
{
int i= 0 ,len,j;
char ch;
len = strlen(p) -1;
j = len;
while(i<=len/2 && j>=len/2)
{
ch = *(p+i);
*(p+i) = * (p +j);
*(p+j) = ch;
i++;
j--;
}


}

[albet_januar]

really dun't know what's wrong with my code.. can anybody help me..
thx b4..
Gb..

Code: Select all

moved after get acc.. :D