// Cpu time : 0.004s
// Memory : minimum
// Tag : Fibonacci, Gotcha, Elegant
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;
int ar [50];
int index;
void fibo ()
{
LL a = 0, b = 1, c = 1;
index = 0;
while ( c <= 2000000000 ) {
ar [index++] = c;
a = b;
b = c;
c = a + b;
}
}
int numsOfFibo (int n)
{
int ret = 0;
for ( int i = index - 1; i >= 0; i-- ) {
if ( n == 0 ) return ret;
else if ( ar [i] <= n ) { n -= ar [i]; ret++; }
}
return ret;
}
int main ()
{
fibo ();
int testCase;
scanf ("%d", &testCase);
int cases = 0;
while ( testCase-- ) {
int d;
scanf ("%d", &d);
int input;
LL cnt = 1;
for ( int i = 0; i < d; i++ ) {
scanf ("%d", &input);
cnt *= numsOfFibo (input);
}
cout << "Case " << ++cases << ": " << cnt << endl;
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

What d problem actually said?

@Mohammad Saifullah,

output = multiply the number needed to express a dimension as a summation of fibonacci numbers, for every dimension

function numsOfFibo (int n) returns, minimum number of Fibonacci needs to express ‘n’ as summation

for example,

if n = 6

numsOfFibo () will return 2

because, u need at least 2 fibonacci number to express 6

3 + 3 or 5 + 1

if n = 8

numsOfFibo () will return 1

because, 8 itself a fibonacci number

if n = 12

numsOfFibo () will return 3

12 = 8 + 3 + 1

so output = multiply numsOfFibo () for each dimension

Assalamualaikum Shihab bhai,

Can you kindly tell me what compiler you are using? I’m using GCC (MingW port) with Code::Blocks. I get wrong values for large numbers in the Long Long modifier. Such as your first output. Many problems that I’ve solved give wrong outputs in this way, but get AC in OJs. It will be really helpful for me.

Thanks in advance.

@Tafhim,

Walaikum-as-Salam

the correct spelling of my name is Shahab .. its ok though, not a problem 🙂

i also use GCC compiler with codeblocks .. long long qualifier is enough for this problem .. and i don’t see any reason of getting wrong values

might be, u r using printf (“%lld”);

or printf (“%I64d”); to print the values in long long variable

u can try to use cout for output.

let me know if this is the solution or u r still facing the same problem .. thank u 🙂