10198 - Counting

[Charlla]

Hi Dmytro_Chernysh,

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


Thanks,

Charlla

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]

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]

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]

Hy!

Thanks,

Charlla

--------------------

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]

Hy!

Thanks a lot!

Charlla.
-------------

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]

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]

#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;
}

[WRJ]

You should create array for saving alredy computed numbers

[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

[Leonid]

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]

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;
}

[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;
}

[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??

[Jan]

When n=4, output 33. When n=14, output 378773.

Hope these help.

[shuvokr]

Big Integer

Code: Select all

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