ICPC Live : 4855 (Hyper Box)



// 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
Advertisements

5 thoughts on “ICPC Live : 4855 (Hyper Box)

  1. Critical Input : 
    5
    15
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    2000000000
    1
    1
    1
    2000000000
    3
    5 8 13
    5
    1 2 5 8 13
    
    Output : 
    Case 1: 1152921504606846976
    Case 2: 1
    Case 3: 16
    Case 4: 1
    Case 5: 1
    
  2. @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

  3. 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.

  4. @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 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s