## 10198 - Counting

Moderator: Board moderators

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am
Hi Dmytro_Chernysh,

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

Thanks,

Charlla

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
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"

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am
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.

Charlla
New poster
Posts: 12
Joined: Mon Oct 13, 2003 1:33 am

### 10198

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"

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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]

liangchene
New poster
Posts: 12
Joined: Thu May 19, 2005 6:07 am

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

#include<iostream>
#include<string>

using namespace std;

int num;
string counter[2000];

{
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++)
{
}
//DP solution
while(cin>>num)
{
cout<<counter[num]<<endl;
}

system("pause");
return 0;
}

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm
You should create array for saving alredy computed numbers

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
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

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:
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.

Stummer
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany
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;
}
``````
Obersturmfuhrer H. Stummer

New poster
Posts: 3
Joined: Sun Jun 24, 2007 11:51 pm
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++)
{

atribuibignum2 (&vet[i], &c);
}

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

return 0;
}
``````

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm
when n=4, the output is 2 or 33?

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
When n=4, output 33. When n=14, output 378773.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 10198 - Counting

Big Integer

Code: Select all

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

Code: Select all

``enjoying life ..... ``