Не будет. По сути ты спускаешься по дереву с вершиной 1024. Кажое принятое решение (степень 2) отсекает моря ложных решений.

таки вопрос: 512+256+256 == 256+512+256?

Да, это тоже самое по идее. В условиях задачи сказано о банкнотах и размене, какая разница как они будут расположены «в кошельке». Если брутфорс пойдет, то напишу брутфорс, спасибо!

тогда брутфорс вроде пойдет. главное, отсечение поставь: если взяли одну банкноту 128, остальные берем не больше 128. тогда и перебор небольшой (порядка 1024^2), и данное условие будет учтено

Когда напишешь брутфорс, почитай в Кормене о динамическом программировании

Ответ 1024?

Решение

От нечего делать накидал на скорую руку, тщательно не проверял, лишь пару простых примеров, но должно быть правильно. И да, это «динамическое программирование».

"""http://www.linux.org.ru/forum/development/9856320"""

#!/usr/bin/env python

import math

def dec_c(n):
    """Solve the problem for the given `n`."""

    m = int(math.log(n, 2)) + 1

    C = [[0] * (n + 1) for _ in xrange(m + 1)]
    for i in xrange(0, m + 1):
        C[i][0] = 1

    for i in xrange(1, m + 1):
        b = 1 << (i - 1)
        for j in xrange(1, n + 1):
            C[i][j] += C[i - 1][j]
            if j >= b:
                C[i][j] += C[i][j - b]

    return C[m][n]

if __name__ == '__main__':
    print dec_c(1024)           # 2320518948

Если найдете контрпример, заморочусь на исправление. Сейчас же тщательно проверять лень.

таки вопрос: 512+256+256 == 256+512+256?

Очевидно, нет. Так бы решение вообще простейшим было.

следующий уровень мастерства - отвечать, не читая даже ОП

но фиг его знает, не будет ли это хозяйство считать бесконечно долго

Ты потратил больше времени на пост на лоре, чем мог бы на написание тех пяти строк, которые это проверяют. Да и вообще, подумай над выводом явной формулы из рекурсивной.

Эм, не знаю, что значит «ОП». И я описАлся, имел ввиду, что это считается за одно разбиение (и вышеприведенное решение так и считает).

P.S. И да, уже понял, прочитав всю ветку. До этого посмотрел по диагонали, убедился лишь, что решения нет.

ну вообще эта задача является NP-полной.

Таблицей такое считать нужно (составить рекуррентное выражение). Backtracking тут не нужен.

во, оно (если багов нет).

на сумму степеней двойки - полиномиальная

да и на любые суммы, вроде бы, тоже. простая динамика.

на сумму степеней двойки - полиномиальная

с чего бы это?

это задача о сумме подмножеств. А она, как известно np полная.

ничего подобного.

если эту задачу можно выразить через задачу о сумме подмножеств, это еще не значит, что ее нельзя решить быстрее. а то так даже 2+2 окажется NP-полной

выше по треду решение. не знаю, правильное ли

можешь int заменить на long и пересчитать?

ничего подобного.

если эту задачу можно выразить через задачу о сумме подмножеств, это еще не значит, что ее нельзя решить быстрее. а то так даже 2+2 окажется NP-полной

не возражаю, но я пока не вижу, почему она полиномиальная. Пока что вижу, что сложность лежит в O(N^log N)

выше по треду решение. не знаю, правильное ли

я его еще не просматривал подробно, ибо пистон не очень знаю.

почему она полиномиальная

потому что реализуется парой вложенных циклов

c[i,j] - рекурсивная функция. всего N*log N значений в диапазоне до [1024,10]. каждое значение считается полиномиально

что такое c[i,j]?

c[i j] - число способов разбить сумму i баксов на банкноты, самая старшая из которых 2^j баксов

это мой вариант, возможно, не совпадающий с тем, что в листинге выше

Python автоматом до длинных расширяет, поэтому переполнения не произойдет.

P.S. Могу переписать, кому надо, на C или Жабке, если понятнее будет, беззнакового целого даже 32-битного, как оказалось, хватает, поэтому все останется так же просто (взял сходу Питон именно по причине возможного переполнения целого).

Ну и чуть позже, если надо, могу расписать суть решения вкратце, но вообще все просто, гуглить и разбираться с «динамическим программированием». Ознакомившись с принципом, все будет относительно очевидно, а без понимания оного, мое краткое объяснение может не убедить.

c[i j] - число способов разбить сумму i баксов на банкноты, самая старшая из которых 2^j баксов
это мой вариант, возможно, не совпадающий с тем, что в листинге выше

У меня именно так, только i и j местами поменять + технический момент — 2 ^ (j - 1) баксов.

Python автоматом до длинных расширяет

а нафига тогда 2 разных типа в спецификации? я думал, эту фичу только в python3 сделали. а оказывается, они просто убрали лишний тип?

понятно, что внизу (в вм) там скорее всего 2 типа. непонятно, нафига 2 типа было наверху

а нафига тогда 2 разных типа в спецификации? я думал, эту фичу только в python3 сделали. а оказывается, они просто убрали лишний тип?

понятно, что внизу (в вм) там скорее всего 2 типа. непонятно, нафига 2 типа было наверху

Честно говоря, не углублялся в этот вопрос. Во 2-й ветке Python'а куча не очень удачных проектных решений, тянущихся с самого начала истории языка, которые в 3-й ветке решили пофиксить. Почему изначально было 2 целых, не знаю (может изначально был только int, а потом, после, вдобавок появился long; может (из zen of python) «явное лучше неявного»). Но в 3-й ветке, да, целый тип решили унифицировать; внутри по прежнему это два разных случая, что и понятно, для эффективности.

Я уже написал по поводу твоего кода, но отправить не смог, ты удалил коммент...

Все верно, но небольшая ошибка.

    for (int i = numberOfBanknotes-1; i >= 0; i--)
    {
        if (banknotes[i] > prevBanknote)
            continue;
        numberOfSolutions++;
        exchange(banknote - banknotes[i], banknotes[i]);
    }

Убери лишний подсчет решений (неверный), все решения у тебя правильно подсчитываются первой инструкцией numberOfSolutions++.

Но для 1024 работать это решение будет долго.

Вот, раз ты на C++ (C) пишешь, перебил быстренько на чистый C, легче будет разобраться.

#include <stdio.h>
#include <math.h>

static unsigned long
dec_c(int n)
{
  static unsigned long C[12][1025];
  int i, j, b;
  int m = log(n) / log(2) + 1;

  for (i = 0; i <= m; ++i)
    C[i][0] = 1;

  for (i = 1, b = 1; i <= m; ++i, b <<= 1)
    for (j = 1; j <= n; ++j) {
      C[i][j] += C[i - 1][j];
      if (j >= b)
        C[i][j] += C[i][j - b];
    }

  return C[m][n];
}

int
main(int argc, char *argv[])
{
  int n = 1024;
  if (argc > 1)
    n = atoi(argv[1]);

  printf("%lu\n", dec_c(n));

  return 0;
}

Да, я уже заметил ошибку. Вот так все верно:

#include <list>
#include <algorithm>
#include <cstdio>
using namespace std;

static long long banknotes[] = { 1, // 2^0
                                 2, // 2^1
                                 4, // 2^2
                                 8, // 2^3
                                 16, // 2^4
                                 32, // 2^5
                                 64, // 2^6
                                 128, // 2^7
                                 256, // 2^8
                                 512 // 2^9
                               };

static int numberOfBanknotes = 10;

static long long numberOfSolutions = 0;

void printBanknote(long long banknote)
{
    printf("%lld + ", banknote);
}

void printSolution(list<int> solution)
{
    printf("Solution: ");
    for_each(solution.begin(), solution.end(), printBanknote);
    putchar('\n');
}

void exchange(long long banknote, long long prevBanknote)
{
    if (banknote == 0)
    {
        numberOfSolutions++;
        if (numberOfSolutions % 1000000 == 0)
            printf("Solution %lld\n", numberOfSolutions);
    }

    if (banknote <= 0)
        return;

    for (int i = numberOfBanknotes-1; i >= 0; i--)
    {
        if (banknotes[i] > prevBanknote)
            continue;
        exchange(banknote - banknotes[i], banknotes[i]);
    }
}

int main()
{
    exchange(1024, 1024);
    printf("Number of solutions %lld\n", numberOfSolutions);
}

Ответ мне выдало:

Number of solutions 2320518947

Правда это без повторений, т.е. 256+512+256=256+256+512. Если с повторениями, то я, почитав про динамическое программирование, делал бы так:

Одна одномерная таблица F[1024].

F[1] = 1 (т.к. банкноту достоинством 1 можно разменять один раз на себя же).
F[2] = 1,1 или 2 = 2
F[3] = 1,1,1; 2,1; 1,2
F[4] = 1 (self) + F[2] + F[3] 
F[5] = F[1] + F[3] + F[4]
F[6] = F[2] + F[4] + F[5]
F[7] = F[3] + F[5] + F[6]
F[8] = 1 (self) + f[4] + F[6] + F[7]

И так далее. Не понятно, почему у тебя двумерная таблица.

Даже это сделал (с повторениями):

#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;
}

И выписало для 1024:

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

Комментарии по польски для товарища, которому это объяснял.

Хотя что-то не так, с повторениями вышло меньше, чем без повторений. :-\

А что мешает идти прямо по степеням 2-ки?

#include <stdio.h>

static long long numbers[1024 + 1] = { 1 }; /* 1 method to collect 0 */

main()
{
  int i, j;
  for (j=1; j<1024; j*=2) {
    for (i=j; i <= 1024; i++) {
      numbers[i] += numbers[i-j];
    }
  }
  printf("%lld\n", numbers[1024]);
  return 0;
}

Будете смеятся, но результат тот же.

Ответ мне выдало:
Number of solutions 2320518947

У вас не учитывается решение из одной купюры: 1024. Тогда ответ будет как у меня.

И так далее. Не понятно, почему у тебя двумерная таблица.

Одномерная таблица как раз потому, что вы считаете перестановки разными решениями. Я выше и писал, что тогда решение будет совсем простое: хватает одномерной таблицы. У меня же два индекса: второй — разбиваемая сумма, а первый — максимальное достоинство купюры, которое используется для разбиения.

На сколько возможных вариантов можно разбить банкноту стоимостью 1024 имея в распоряжении бесконечное количество банкнот стоимостью 2^i, где i e [0..9]? => 1024 за пределами диапазона

Да, не обратил внимание, значит в моем решении небольшая ошибка, я считал любые степени 2-ки.

Хотя что-то не так, с повторениями вышло меньше, чем без повторений. :-\

Море решение для случая с повторениями (с учетом досадной ошибки использования купюры 1024):

#include <stdio.h>
#include <math.h>

static unsigned long
dec_c(int n)
{
  static unsigned long C[1025];
  int i, j;

  C[0] = 1;

  for (i = 1; i <= n; ++i)
    for (j = 1; j <= i && j <= 512; j <<= 1)
      C[i] += C[i - j];

  return C[n];
}

int
main(int argc, char *argv[])
{
  int n = 1024;
  if (argc > 1)
    n = atoi(argv[1]);

  printf("%lu\n", dec_c(n));

  return 0;
}

Выдает 12183728273700989960, что больше решения без повторений. Закономерно больше.

P.S. На переполнение не проверял.

Вообще-то рост значений при разрешении повторений там страшный. Очевидно за два шага (когда N велико) должно как минимум удваиваться. F(n) > F(n-1) + F(n-2) > F(n-2) + F(n-2) просто из-за вариантов с 1 и 2 копейками в конце. Посему 64 бита маловато.

А проверить стоило. Уже в пределах 80 должно вылезти.

Мда.. Переписал на Питоне:

sr@cocaine:~/_work/_contest$ ./with_repetitions.py 
Number of solutions 6126383508117712525206362746134193148994562697954356550542933068276648314416330110321776840794630768699705855119789093537549246283823973236762308505084164066693537445853239958343894758838583683685987973647066890139458139149640685927869056175108460424199

Вот сам код:

#!/usr/bin/env python

import sys

solutions = [0] * 1025

def init():
    solutions[1] = 1; # (1)
    solutions[2] = 2; # (1,1) (2)
    solutions[3] = 3; # (1,1,1) (1,2) (2,1)

def isPowerOfTwo(x):
    return ((x > 0) and ((x & (x - 1)) == 0))

def solve(n):
    for i in xrange(4, n+1):
        numberOfSolutions = 0
        for j in xrange(1, i):
            if isPowerOfTwo(j):
                numberOfSolutions += solutions[i-j]
        if isPowerOfTwo(i):
            numberOfSolutions = numberOfSolutions + 1
        solutions[i] = numberOfSolutions
    
if __name__ == '__main__':
    n = 1024

    if len(sys.argv) > 1:
        n = int(sys.argv[1])

    init()
    solve(n)

    numberOfSolutions = solutions[n]
    if isPowerOfTwo(n):
        numberOfSolutions = numberOfSolutions - 1
    
    print "Number of solutions %d\n" % (numberOfSolutions)

А проверить стоило.

Ну, я просто идею обозначить, суть. Иначе бы снова сразу на Python написал, чтоб не заморачиваться на длинную арифметику.

Ответ верный, но решение больно уж замороченное...

#!/usr/bin/env python

def dec_c(n):
    C = [1] + [0] * n

    for i in xrange(1, n + 1):
        j = 1
        while j <= i and j <= 512:
            C[i] += C[i - j]
            j <<= 1

    return C[n]

if __name__ == '__main__':
    import sys

    n = sys.argv[1] if len(sys.argv) > 1 else 1024
    print dec_c(n)

Скажите мне, чудо-программисты, вы ваши решения для 2, 4, 8 проверили?

Скажите мне, чудо-программисты, вы ваши решения для 2, 4, 8 проверили?

Спасибо за столько высокую оценку моих скромных способностей. Разумеется, на простых случаях проверил вручную.

Без повторений количества разбиений 2, 4 и 10, соответственно.