1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <iostream>

using namespace std;

void setFib(unsigned long long * fib, int elements)
{
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i < 2000; ++i)
        fib[i] = fib[i - 1] + fib[i - 2];

}

unsigned long long fibToDec(string fib, unsigned long long * pattern)
{
    unsigned long long result = 0;
    for (int i = 0; i < fib.length(); ++i)
    {
        if (fib[i] == '1')
            result += pattern[i];
    }
    return result;
}

string decToFib(unsigned long long dec, unsigned long long * pattern)
{
    string result = "";
    int i = 1999;

    if (dec == 0)
        return "0";

    while(pattern[i] > dec && i > 0)
        --i;

    for (; i >=0; --i)
    {
        if (pattern[i] <= dec)
        {
            result = "1" + result;
            dec -= pattern[i];
        }
        else
            result = "0" + result;
    }

    return result;
}

void printFib(string fib)
{
    cout << fib.length() << " ";
    for (int i = 0; i < fib.length(); ++i)
    {
        cout << fib[i] << " ";
    }
    if (fib.length() == 0)
        cout << "0";
    cout << endl;
}

unsigned long long fib[2000], fib1Dec, fib2Dec, resultInDec;
int dataSets, numberOfFibBits;
string fib1 = "";
string fib2 = "";
string resultInFib;
char fibBit;

int main()
{
    setFib(fib, 2000);

    cin >> dataSets;

    for (int i = 0; i < dataSets; ++i)
    {
        cin >> numberOfFibBits;
        for(int j = 0; j < numberOfFibBits; ++j)
        {
            cin >> fibBit;
            fib1 += fibBit;
        }

        cin >> numberOfFibBits;
        for(int j = 0; j < numberOfFibBits; ++j)
        {
            cin >> fibBit;
            fib2 += fibBit;
        }

        fib1Dec = fibToDec(fib1, fib);
        fib2Dec = fibToDec(fib2, fib);
        resultInDec = fib1Dec * fib2Dec;
        resultInFib = decToFib(resultInDec, fib);
        printFib(resultInFib);

        fib1 = fib2 = "";
    }

    return 0;
}