10198 - Counting

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

Moderator: Board moderators

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

Post by Charlla » Sun Nov 30, 2003 2:21 am

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 :-)

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sun Nov 30, 2003 2:35 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" :-)

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Nov 30, 2003 5:30 am

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

Post by Charlla » Sun Nov 30, 2003 3:17 pm

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

Post by Charlla » Sat Dec 13, 2003 5:10 am

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
Location: Bangladesh
Contact:

Post by mamun » Thu Dec 29, 2005 7:53 pm

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?

Post by liangchene » Mon Feb 27, 2006 12:05 am

#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
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Post by WRJ » Wed Mar 29, 2006 9:19 am

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:

Post by 898989 » Mon Jun 12, 2006 4:52 pm

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

Post by Leonid » Wed Jul 26, 2006 4:50 pm

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

Post by Stummer » Sat Sep 16, 2006 4:27 pm

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;
}
Obersturmfuhrer H. Stummer

mad
New poster
Posts: 3
Joined: Sun Jun 24, 2007 11:51 pm

Post by mad » Fri Jul 06, 2007 5:45 am

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
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm

Post by lucky16g » Mon Jul 23, 2007 8:50 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jul 23, 2007 4:22 pm

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
Location: Bangladesh

Re: 10198 - Counting

Post by shuvokr » Sat Jan 25, 2014 5:32 pm

Big Integer :D

Code: Select all

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

Code: Select all

enjoying life ..... 

Post Reply

Return to “Volume 101 (10100-10199)”