История изменений

#include <stdio.h>
#include <stdlib.h>

static long long solutions[1024+1];

void init()
{
    solutions[1] = 1; // (1)
    solutions[2] = 2; // (1,1) (2)
    solutions[3] = 3; // (1,1,1) (1,2) (2,1)
}

int isPowerOfTwo(long long x)
{
    return ((x > 0) && ((x & (x - 1)) == 0));
}

void solve(int n)
{
    for (int i = 4; i <= n; i++) // jedz po tablice rozwiazan od 4 do 1024 czyli rozwiazuj dla 4, dla 5, itd/
    {
        int numberOfSolutions = 0;
        for (int j = i-1; j > 0; j--) // jedz w tyl od tej liczby, ktora teraz rozwiazujesz
        {
            if (!isPowerOfTwo(j)) // jezeli liczba mniejsza od tej, ktora rozw. nie jest potega 2...
                continue; // olej ja, nie mozemy tym banknotem rozmieniac
            // jezeli tym banktonem mozemy, to rozmien i to co zostalo tez rozmien, ale mamy juz
            // rozwiazanie dla tego co zostalo, wiec do liczby rozwiazan dodaj liczbe rozwiazan
            // tego co zostalo.
            // 
            // przyklad:
            //  solve(4) = solve(4-1) + solve(4-2) = solve(3) + solve(2)
            //  ale poniewaz jedziemy od poczatku, to solve(3) i solve(2) juz mamy
            numberOfSolutions += solutions[i-j];
        }
        // ustaw liczbe rozwiazan ostateczna dla tego i, ktorym jedziemy po tablicy, ale
        // jezeli to i jest potega dwojki, to dodaj 1 dlatego ze banknote np. 2 mozna
        // rozmieniac jako samo 2
        solutions[i] = numberOfSolutions + isPowerOfTwo(i);
    }
}

int main(int argc, char **argv)
{
    int n = 1024;
    if (argc > 1)
        n = atoi(argv[1]);
    init();
    solve(n);
    printf("Number of solutions: %lld\n", solutions[n] - isPowerOfTwo(n));
    return 0;
}

sr@cocaine:~/_work/_contest$ ./a.out 1024
Number of solutions: 299150343

#include <stdio.h>
#include <stdlib.h>

static long long solutions[1024+1];

void init()
{
    solutions[1] = 1; // (1)
    solutions[2] = 2; // (1,1) (2)
    solutions[3] = 3; // (1,1,1) (1,2) (2,1)
}

int isPowerOfTwo(long long x)
{
    return ((x > 0) && ((x & (x - 1)) == 0));
}

void solve(int n)
{
    for (int i = 4; i <= n; i++) // jedz po tablice rozwiazan od 4 do 1024 czyli rozwiazuj dla 4, dla 5, itd/
    {
        int numberOfSolutions = 0;
        for (int j = i-1; j > 0; j--) // jedz w tyl od tej liczby, ktora teraz rozwiazujesz
        {
            if (!isPowerOfTwo(j)) // jezeli liczba mniejsza od tej, ktora rozw. nie jest potega 2...
                continue; // olej ja, nie mozemy tym banknotem rozmieniac
            // jezeli tym banktonem mozemy, to rozmien i to co zostalo tez rozmien, ale mamy juz
            // rozwiazanie dla tego co zostalo, wiec do liczby rozwiazan dodaj liczbe rozwiazan
            // tego co zostalo.
            // 
            // przyklad:
            //  solve(4) = solve(4-1) + solve(4-2) = solve(3) + solve(2)
            //  ale poniewaz jedziemy od poczatku, to solve(3) i solve(2) juz mamy
            numberOfSolutions += solutions[i-j];
        }
        // ustaw liczbe rozwiazan ostateczna dla tego i, ktorym jedziemy po tablicy, ale
        // jezeli to i jest potega dwojki, to dodaj 1 dlatego ze banknote np. 2 mozna
        // rozmieniac jako samo 2
        solutions[i] = numberOfSolutions + isPowerOfTwo(i);
    }
}

int main(int argc, char **argv)
{
    int n = 1024;
    if (argc > 1)
        n = atoi(argv[1]);
    init();
    solve(n);
    printf("Number of solutions: %lld\n", solutions[n] - isPowerOfTwo(n));
    return 0;
}

sr@cocaine:~/_work/_contest$ ./a.out 1024
Number of solutions: 299150343