Threaded Mode | Linear Mode

***drdebcol*** · (This post was last modified: 05-09-2011 12:29 AM by drdebcol.)

Gustavo knows how to count, but he is just now learning how to write numbers.
He has already learned the digits 1, 2, 3, and 4. But he does not yet realize that 4 is different than 1, so he thinks that 4 is just another way to write 1.
He is having fun with a little game he created: he makes numbers with the four digits that he knows and sums their values. For example:

Code:

132 = 1 + 3 + 2 = 6

112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)

Gustavo now wants to know how many such numbers he can create whose sum is a number n. For n = 2, he can make 5 numbers: 11, 14, 41, 44, and 2. (He knows how to count up beyond five, just not how to write it.) However, he can’t figure out this sum for n greater than 2, and asks for your help.
Input
Input will be an integer 1 ≤ n ≤ 1, 000.
Output
Output an single integer stating how many numbers Gustavo can make such that the sum of their digits is equal to n.
Sample Input
2
Sample Output
5
Sample Input
3
Sample Output
13
You can find the solution just by making a for loop that will count and you just separate digits using MOD DIV algorithm, you have it explained here :
http://www.pro9ramming.com/showthread.php?tid=124
And then check if numbers in that integer are 1,2,3 or 4 and that's it and the check sum of course. But this algorithm, despite it's slowness, is not elegant.
So i decided to make recursive solution that is faster and more reliable.
It basically makes every possible variation of 1,2,3 or 4 counting from length 1 to n, and checks for sum.
So here is the code in TPW :

Code:

program counting;

uses wincrt;

var

  k,n,br:integer;

  a:array[1..1000] of 1..4;

function sum:integer;

var

 i,s:integer;

begin

  s:=0;

for i:=1 to k do

  if a[i]=4 then

    s:=s+1

  else

    s:=s+a[i];

   sum:=s;

end;

procedure combine(index:integer);

var

  i:integer;

begin

  if index>k then

    begin

      if sum=n then

        br:=br+1;       

      end

  else

    begin

     for i:=1 to 4 do

       begin

        a[index]:=i;

        combine(index+1);

       end;

    end;

end;

begin

 br:=0;

 readln(n);

for k:=1 to n do

   combine(1);

writeln(br);

end.

And for C++ lovers, i wrote code in C++ LOL :

Code:

#include <iostream>

#include <cstdio>

using namespace std;

int n,k,br;

int a[1000];

int sum()

{

    int s,i;

    s=0;

      for (i=1;i<=k;i++)

        if (a[i]==4)

          s++;

        else

          s=s+a[i];

      return s;

    }

int combine(int index)

{

    if (index>k)

     {

          if (sum()==n)

            br++;      

     }

     else

     {

         int i;

         for (i=1;i<=4;i++)

           {

             a[index]=i;

             combine(index+1);              

           }

         }

    }

int main()

{

    cin>>n;

    br=0;

    for (k=1;k<=n;k++)

      combine(1);

    cout<<br<<endl;

    system("pause");  

}

***l3g1sl4tor*** · 08-18-2009, 09:14 PM

Typical mathematical task... Programing in this task is not so matter Smile

***drdebcol*** · 08-18-2009, 11:44 PM

(08-18-2009 09:14 PM)l3g1sl4tor Wrote: Typical mathematical task... Programing in this task is not so matter

Yeah, you can make variations with repetition using this formula :

Code:

V(n,k)=n!/(n-k)!

And just extract those with specified sum !