Page 2 of 3

Posted: Sun Nov 30, 2003 2:21 am
by Charlla
Hi Dmytro_Chernysh,

I didn't understand your message. What is "long arigfmetic"???


Thanks,

Charlla :roll:


Dmytro_Chernysh wrote:Hi Charlla,

You do have a mistake -- you should have used "long arigfmetic" instead of just long long. For example, n=30
1186714748389

Obviously, for n=1000 the number is really huge

Hope you understood :-)

Posted: Sun Nov 30, 2003 2:35 am
by Dmytro Chernysh
When you have a really big number, let's say 1000 digit, the only way to keep it is an array. Now, if you want add, subrtact, multiplay or divide such numbers you have to write alogithms of addition, subtraction...
Such procedures/methods are called "long arifmetic".

The answer for n=1000 in this problem has more than a few hundred digits, therefore, you should use "long arifmetic" :-)

Posted: Sun Nov 30, 2003 5:30 am
by shamim
Actually, C does not have any built in big integer. I mean, if there were, how big it would be, 1000 digit ,10000 digit or maybe even bigger.

The idea is to store numbers in string form, that is store them in a char array . Then you will have to create functions to add, subtract, multiply and possibly divide these numbers.

Posted: Sun Nov 30, 2003 3:17 pm
by Charlla
Hy!

Thanks,

Charlla :)

--------------------
shamim wrote:Actually, C does not have any built in big integer. I mean, if there were, how big it would be, 1000 digit ,10000 digit or maybe even bigger.

The idea is to store numbers in string form, that is store them in a char array . Then you will have to create functions to add, subtract, multiply and possibly divide these numbers.

10198

Posted: Sat Dec 13, 2003 5:10 am
by Charlla
Hy!

Thanks a lot!

Charlla. :)
-------------
Dmytro_Chernysh wrote:When you have a really big number, let's say 1000 digit, the only way to keep it is an array. Now, if you want add, subrtact, multiplay or divide such numbers you have to write alogithms of addition, subtraction...
Such procedures/methods are called "long arifmetic".

The answer for n=1000 in this problem has more than a few hundred digits, therefore, you should use "long arifmetic" :-)

Posted: Thu Dec 29, 2005 7:53 pm
by mamun
Would anybody explain how to get to this
f[n]:=f[n-1]+f[n-2]+f[n-3]+f[n-4]
that is
f[n]:=2*f[n-1]+f[n-2]+f[n-3]

I got wrong answer for this, can anybody tell me why?

Posted: Mon Feb 27, 2006 12:05 am
by liangchene
#include<iostream>
#include<string>

using namespace std;

int num;
string counter[2000];

string add(string a, string b)
{
int x;

if (a.size()<b.size())
swap(a,b);

if (a.size()==b.size())
{
for (x=b.size()-1;x>=1;x--)
{
a[x]+=b[x]-48;
if (a[x]>57)
{
a[x]-=10;
a[x-1]++;
}
}
a[0]+=b[0]-48;
if (a[0]>57)
{
a[0]-=10;
a="1"+a;
}
}
else
{
for (x=1;x<=b.size();x++)
{
a[a.size()-x] +=b[b.size()-x]-48;
if (a[a.size()-x]>57 )
{
a[a.size()-x]-=10;
a[a.size()-x-1]++;
}
}
}
return a;
}


int main()
{
counter[0]="1";
counter[1]="2";
counter[2]="5";
counter[3]="13";

int x,y;
for (x=4;x<=1010;x++)
{
counter[x]= add(counter[x],counter[x-1]);
counter[x]= add(counter[x],counter[x-1]);
counter[x]= add(counter[x],counter[x-2]);
counter[x]= add(counter[x],counter[x-3]);
}
//DP solution
while(cin>>num)
{
cout<<counter[num]<<endl;
}

system("pause");
return 0;
}

Posted: Wed Mar 29, 2006 9:19 am
by WRJ
You should create array for saving alredy computed numbers

Posted: Mon Jun 12, 2006 4:52 pm
by 898989
Please i got wrong answer
I just need sample inputs and sample outputs for
3 4 5 6 7 8 9 100 200 1000 and more if any one can

Posted: Wed Jul 26, 2006 4:50 pm
by Leonid
mamun wrote:Would anybody explain how to get to this
f[n]:=f[n-1]+f[n-2]+f[n-3]+f[n-4]
that is
f[n]:=2*f[n-1]+f[n-2]+f[n-3]
If someone ever comes up again with this question here is the answer:
Lets denote F(n) the sequence of numbers to be constructed that sum up to n.
It can BEGIN either with 1, 2, 3 or 4
When it begins with 1, then the answer is 1..F(n-1).. where F(n-1) is also a sequence of numbers that can begin with either 1, 2, 3 or 4 (that is why we include all possible arrangements). The same thing happens when the sequence begins with 2, 3 or 4.
For example if we take N = 5. Then we have: 1..F(4).. or 2..F(3).. or 3..F(2) or 4..F(4).. We can be sure that, for example, F(4) includes all possible sequences that sum up to 4 because we find it from the smaller problems with n < 4 and we know also that this sequence can begin with either 1, 2, 3 or 4 at the time of finding F(5).
Thus we include all possible arrangements of the sequence which elements sum up to n. Written generally and denoting f(n) as a number of such suquences that sum up to n we get such relation: f(n) = 2*f(n-1) + f(n-2) + f(n-3) as it was described earlier in this thread.

Posted: Sat Sep 16, 2006 4:27 pm
by Stummer
898989 wrote:Please i got wrong answer
I just need sample inputs and sample outputs for
3 4 5 6 7 8 9 100 200 1000 and more if any one can
This is my program, and it gets RTE on online judge, but it works
on my computer normally.

Code: Select all

#include <iostream.h>
int m[1005][500]={0};
int main()
{
	int i,n,j,t; m[0][499]=1; m[1][499]=2; m[2][499]=5;
	for(i=3;i<=1005;i++)
	{
		t=0;
		for(j=499;j>=0;j--)
		{
			m[i][j]+=2*m[i-1][j];
			m[i][j]+=m[i-2][j];
			m[i][j]+=m[i-3][j];
			m[i][j]+=t;
			t=m[i][j]/10;
			m[i][j]%=10;
		}
	}
	bool st;
	while(cin>>n) 
	{
		st=0;
		for(i=0;i<500;i++)
		{
			if(m[n][i]!=0) st=1;
			if(st==1) cout<<m[n][i]; 
		}
		cout<<endl;
	}
	return 0;
}

Posted: Fri Jul 06, 2007 5:45 am
by mad
Hello everybody!!! I did the program but I'm receiving presentation error. My code is below. Could someone help me?

Code: Select all

#include <string.h>
#include <stdio.h>
#define MAXDIGITS 1000
#define max(a,b) (a > b) ? a : b;

typedef struct
{
  char digits[MAXDIGITS];	/* represent the number */
  int signbit;		/* PLUS or MINUS */
  int lastdigit;		/* index of high-order digit */
} bignum;


void 
add_bignum (bignum * a, bignum * b, bignum * c) 
{
  
int carry;			/* carry digit */
int i;			/* counter */
  
for (i = 0; i < MAXDIGITS; i++)
  c->digits[i] = 0;
  
c->lastdigit = max (a->lastdigit, b->lastdigit);
 
carry = 0;
  
for (i = 0; i <= (c->lastdigit); i++)
{      
  c->digits[i] = (char) (carry + a->digits[i] + b->digits[i]) % 10;
      
  carry = (carry + a->digits[i] + b->digits[i]) / 10;
} 

if (carry != 0)
{
  c->digits[i] = 1;    
  c->lastdigit++; 
}

}

void
atribuibignum (bignum * a, char b[]) 
{
  int i, n;
  n = strlen (b);
 
  a->lastdigit = n - 1; 
 
  //assigning a string to a bignum
  for (i = 0; i < n; i++)
    a->digits[i] = b[n - i - 1] - '0';
}

void
atribuibignum2 (bignum * a, bignum * b) 
{
  int i, n;
 
  a->lastdigit = b->lastdigit; 
 
  //assigning a big num to a bignum  
  for (i = 0; i <= b->lastdigit; i++)
    a->digits[i] =  b->digits[i]; 
}

void 
print_bignum (bignum * n) 
{
  int i;
 
  for (i = n->lastdigit; i >= 0; i--)  
    printf ("%c", '0' + n->digits[i]);

  printf ("\n");
}

main () 
{
bignum a;
bignum b;
bignum c;
int i;
int j;
bignum vet[1002];
int cap;
char aux[102];

atribuibignum(&vet[0],"0");
atribuibignum(&vet[1],"2");
atribuibignum(&vet[2],"5");
atribuibignum(&vet[3],"13");

for (i = 4; i < 1002; i++)
{
  add_bignum(&vet[i-1],&vet[i-1],&a);
  add_bignum(&a,&vet[i-2],&b);
  add_bignum(&b,&vet[i-3],&c);
  
  atribuibignum2 (&vet[i], &c);
}

  while (scanf ("%d", &cap) != EOF)
    print_bignum(&vet[cap]);
  
  return 0;
}

Posted: Mon Jul 23, 2007 8:50 am
by lucky16g
when n=4, the output is 2 or 33?

and when n=14 is the anser equal to n=11 && n=44 & n=41??

Posted: Mon Jul 23, 2007 4:22 pm
by Jan
When n=4, output 33. When n=14, output 378773.

Hope these help.

Re: 10198 - Counting

Posted: Sat Jan 25, 2014 5:32 pm
by shuvokr
Big Integer :D

Code: Select all

Sample Input: 
1000
Ac Output:
78048661677573853517262981677495799469644058502252545391326824727949818697450405
37197592219996231328486687877730240352396489040560067523395940725030942516170568
23473818212763523462465577553124443843711825354225536592348622125317245620393318
92839856891161395975633376476961430054962522877349418936820194065151048298854202
61968884040123236083676226862353415881286645117793584639279853095668990201156175
586714