ibm написав:
Як ти робив (сам алгоритм) задачку з CD? В мене чомусь дало неправильну в-дь, хоча я, я здається все врахував... Задача нагадує якусь, звідси, яку я вже давно здав і Забобонного Гриця з обласної...

Доречі, задача D робилась динамікою, жадним?

Vladislav_Simonenko написав:
Розбиваєш на макс. за кількістю кучі (K == 13, тоді по 12). В тебе може залишитися одна купа. Якщо в ній не 13, то це відповідь. Якщо ж 13, то ти можеш перекласти один диск з якоїсь лівої групи, де максимум до неї, так щоб вийшло 14, але лише в тому випадку, якщо 1) така взагалі є 2) інші купи не по 14 дисків.

розкажіть як конкретно динамікою там робити задачу D?

Romko написав:
Я тільки не врахував умови про 14

ibm написав:
Кул! mMasters рулить не менше Остапа! 45 хвилин і 4 задачі!

І що тут поганого?

Та він (або вони) підглянули вчорашні задачі

Ostap написав:


Ідея така:
нехай маємо наше число М (потреба пального). Представимо його в двійковому вигляді, наприклад:
0010110

пробігаємося від старших бітів і шукаємо не нульовий елемент (4-тий біт на прикладі). Ми тепер маємо два варіанти: купити ємкість розміру 2^4 або не купувати, а перенести "борг" в молодші розряди - тобто купити цей об'єм меншими ємкостями. При переносі отримаємо таке представлення (вже не двійкове):
0002110
(одна ємкість об'єму 2^k перетворюється в дві 2^(k-1))
з такого стану ми маємо 3 переходи: купити 0, 1 або 2 ємкості об'єму 2^3 і перейти ми можемо у стани такі:
0000510
0000310
0000110
відповідно.

Отже охарактеризуємо стан динамічної системи:
1) k - позиція (біт) яку ми розглядаємо - від 31 до 0
2) величина "боргу" - скільки потрібно ще купити об'єму пального крім того, що описане бітами починаючи з k (поточної позиції) в напрямку молодших бітів. Борг може бути від 0 до S, де S - кількість ємкостей об'єму меншого за 2^k, оскільки більший борг ми заповнити точно не зможемо.

Отже маємо максимум 32х100000 = 3.2М різних можливих динамічних позицій.
З кожної позиції ми можемо побудувати такі переходи:
- купувати від 0 до min(борг(+1 якщо поточний біт виставлений), C[k]) ємкостей об'єму 2^k (тут C[k] - к-сть ємкостей об'єму 2^k) а решту боргу переносити на наступний розряд - в наступну динамічну позицію.

Крім цього інтуїтивно зрозуміло, що коли ми на певному кроці купуємо кілька ємкостей об'єму 2^k, то нам потрібно вибрати ті, які мають найменшу ціну. Тобто перш за все потрібно посортувати ємкості по цінах в кожній групі з однаковими об'ємами.

Весь цей алгоритм дуже просто реалізувати за допомогою рекурсії з мемоізацією.

прікольно, але є альтернатива...як на мене - простіша
for (i = 0 to 30)
{
i-й біт є в М -> вибрали надешевший і додали до результату (якшо такого не існує - розв'язку нема)
всі цестерни розміром і, що залишилися, посортували по ціні і попарно позєднували, утворивши цестерни розміром 2і.
}