485 - Pascal's Triangle of Death

[Eric]

I get wrong answer for many times, but I still can't find my bug.
Can anyone tell me what is wrong?

[pascal]--Cut--[/pascal]
The number that is greater than 10^60 should have 61 diigts, I think.

[tep]

I think u should check your code again..
this is my output.. for the first n line..

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
and your output..

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 22 66 220 495 792 924 792 495 220 66 12 1
1 33 88 286 715 1287 1716 1716 1287 715 286 78 13 1

i bolded the different one..
i haven't checked your code.. but i guess.. your addition procedure is wrong...

GBU! (God Bless U!)

[sumankar]

Code: Select all

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

#define MAX	512
#define NMAX	205

struct bignum {
	char num[MAX];
};

typedef struct bignum bignum;

bignum set(char *s)
{
	int i, len;
	bignum a;
	
	memset(a.num, '0', MAX);
	len = strlen(s);
	for( i = len-1; i >= 0; i-- )
		a.num[len-1-i] = s[i];
	a.num[MAX] = '\0';
	return a;
}

bignum add(bignum x, bignum y)
{
	bignum w;
	int i, cy, temp;;

	cy = 0;
	for( i = 0; i < MAX; i++ ) {
		temp = x.num[i]-'0' + y.num[i]-'0' + cy;
		if( temp > 9 ) {
			cy = 1;
			temp %= 10;
		}
		else cy = 0;
		w.num[i] = temp+'0';
	}
	w.num[MAX] = '\0';
	return w;
}

int compare(bignum a, bignum b)
{
	int i;

	for( i = 0; i < MAX; i++ )
		if( a.num[i] > b.num[i] )
			return 1;
		else if( a.num[i] < b.num[i] )
			return -1;
return 0;
}

void print(bignum w)
{
	int i;

	for( i = MAX-1; w.num[i] == '0'; i-- )
		;
	for( ; i >= 0; i-- )
		printf("%c", w.num[i]);
}

bignum C[NMAX+1][NMAX+1];

void nCr()
{
	int i, j;

	for( i = 0; i <= NMAX; i++ ) {
		C[i][0] = set("1");
		C[0][i] = set("0");
	}

	for( i = 0; i <= NMAX; i++ )
		C[i][i] = set("1");

	for( i = 1; i <= NMAX; i++ )
		for( j = 1; j <= NMAX; j++ ) {
			C[i][j] = add(C[i-1][j-1] ,C[i-1][j]);
		}
}

int main()
{
	int n, r;

	nCr();
	for( n = 0; n < 205; n++ )
		for( r = 0; r <= n; r++ ) {
			print(C[n][r]);
			printf("%c", r == n ? '\n' : ' ');
		}
	return 0;
}
[/c]

Getting RTE ?Why
Suman

[Eric]

Thanks. I have modified my code.
However, I still get a WA.
Can anyone help me again?

[pascal]--Cut--[/pascal]

[Eric]

Just forget it. I just make a silly mistake in initialization.
Thanks

[pavelph]

I solved this problem, but maybe wrong
So my first number that > 10^60 is

Code: Select all

102915295372100842754347681194716375353377979378184088366400 

Is it true? Help me please.

[aakash_mandhar]

Hi,
I hope you are not stopping at the first number greater than 2^60 that u encounter.. Finidh that row and then exit.. Since you had not mentioned anythong else so i assume this is the case...

If you have any problems i might pass a snippet of the code to you..

Aakash

[wyanez]

This problem is of BigNum or it is possible to use long double or double?
Thank...

my code is WA:

[cpp]
// Problem 485 - Triangle Pascal
#include <iostream>
using namespace std;

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

double ant[10000],actual[10000],*pact,*pant;
char *maxi="1000000000000000000000000000000000000000000000000000000000000";

int main(){
int i,linea=3;
char strnum[100];
long double maxim=atof(maxi);

ant[0]=1; ant[1]=1; pant=ant;
pact=actual;
cout<<1<<endl;
cout<<"1 1"<<endl;
for( ; ; ){
cout<<1;
*pact=1;
for(i=1;i<linea;i++){
*(pact+i)=*(pant+i)+*(pant+(i-1));
sprintf(strnum,"%.0Lf",*(pact+i));
cout<<" "<<strnum;
if(*(pact+i)>=maxim) goto the_fin;
}
for(i=1;i<linea;i++) *(pant+i)=*(pact+i);
cout<<endl;
linea++;
}

the_fin:
return 0;
}
[/cpp]

[playerX]

yeah.. it's a bignum problem, it would be pretty easy if it wasn't right?

[anupam]

it's really an easy problem.
use DP and Bignum having ony add function and check out the length of the answer to stop printing.
--
Anupam

[Dani Rodrigo]

I don't find the mistake of my program.
It output all the rows until row 204 (this row included, row 204 is the first which contain a number bigger tha 10^60).

This is my code:




#include <stdio.h>


void main ()
{
double antiguos[300], nuevos[300], cota;
int i, lon, chivato=0;

cota=1;
for (i=0; i<60; i++)
cota = cota*10;

printf ("1\n1 1\n");
antiguos[0]=1; antiguos[1]=1;
lon=2;

while ( chivato==0 )
{
nuevos[0]=1.0;
printf ("1");
for (i=1; i<lon; i++)
{
nuevos = antiguos[i-1]+antiguos;
printf (" %.0f", nuevos);
if ( nuevos >= cota )
chivato=1;
}
nuevos[lon]=1.0;
printf (" 1\n");
lon++;
for (i=0; i<lon; i++)
antiguos=nuevos;
}
}

Thanks you!

[UFP2161]

Doubles do not have enough precision to answer this question correctly.

[Dani Rodrigo]

Thank you, UFP! I'm going try to solve it using strings.

[Dani Rodrigo]

Finally I got ACC using strings, thanks for your post

[jaracz]

Hi everyone!

In which row should output terminate??