485 - Pascal's Triangle of Death

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

Moderator: Board moderators

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

p485 WA

Post by 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.
Last edited by Eric on Fri Nov 07, 2003 5:28 pm, edited 1 time in total.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

Post by 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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

485:Pascal'str of death:RTE

Post by 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
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric »

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

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

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric »

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

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Need help with 485 - Pascal`s Triangle

Post by 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
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by 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 :)
...I was born to code...

wyanez
New poster
Posts: 8
Joined: Thu Nov 20, 2003 7:19 pm

485 - Triangle Pascal Help... is BigNum?

Post by wyanez »

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

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
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post by playerX »

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by 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
"Everything should be made simple, but not always simpler"

Dani Rodrigo
New poster
Posts: 11
Joined: Sun Jul 18, 2004 1:39 am

485 - Pascal's Triangle WA!!

Post by 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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

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

Dani Rodrigo
New poster
Posts: 11
Joined: Sun Jul 18, 2004 1:39 am

Post by Dani Rodrigo »

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

Dani Rodrigo
New poster
Posts: 11
Joined: Sun Jul 18, 2004 1:39 am

Post by Dani Rodrigo »

Finally I got ACC using strings, thanks for your post :P

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

485 WA........

Post by jaracz »

Hi everyone!

In which row should output terminate??
keep it real!

Post Reply

Return to “Volume 4 (400-499)”