HDU : 1708 (Fibonacci String)


// http://acm.hdu.edu.cn/showproblem.php?pid=1708

// @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 <utility>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

long long callForOne [50 + 5];
long long callForZero [50 + 5];

long long recurOne (int n)
{
    if ( n == 1 )
        return 1;

    if ( n < 1 )
        return 0;

    if ( callForOne [n] != -1 )
        return callForOne [n];

    return callForOne [n] = recurOne (n - 1) + recurOne (n - 2);
}

long long recurZero (int n)
{
    if ( n == 2 )
        return 1;

    if ( n < 2 )
        return 0;

    if ( callForZero [n] != -1 )
        return callForZero [n];

    return callForZero [n] = recurZero (n - 1) + recurZero (n - 2);
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    memset (callForOne, -1, sizeof(callForOne));
    memset (callForZero, -1, sizeof(callForZero));

    callForOne [1] = 1;
    callForOne [0] = 0;
    callForOne [50] = recurOne (50);

    callForZero [0] = 1;
    callForZero [1] = 0;
    callForZero [2] = 1;
    callForZero [50] = recurZero (50);

    while ( testCase-- ) {
        string first;
        string second;
        int k;

        long long charFrq [26];
        memset (charFrq, 0, sizeof (charFrq));

        cin >> first >> second >> k;

        for ( size_t i = 0; i < first.size (); i++ ) {
            charFrq [first.at (i) - 'a'] += callForZero [k];
        }

        for ( size_t i = 0; i < second.size (); i++ ) {
            charFrq [second.at (i) - 'a'] += callForOne [k];
        }

        for ( int i = 0; i < 26; i++ ) {
            printf ("%c:", 'a' + i);
            cout << charFrq [i] << endl;
            //printf ("%c:%d\n", 'a' + i, charFrq [i]);
        }

        printf ("\n");
    }

    return 0;
}

// @END_OF_SOURCE_CODE

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