На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Доброго вечорп! Усіх з наступачим новим роком!
Чи буде змінений ТЛ на першій задачі Treats?
Бо, на скільки мені відомо, на повний бал заходить розв’язок з асимптотикою O(b + n *（2 ^ n）), хоча існує розв’язок за O(n *（2 ^ n）).
Дякую за увагу.
Відредаговано b0rys (2018-12-31 23:03:07)
Поза форумом
b0rys написав:
Бо, на скільки мені відомо, на повний бал заходить розв’язок з асимптотикою O(b + n *（2 ^ n）), хоча існує розв’язок за O(n *（2 ^ n）).
Расскажите пожалуйста, как решать за O(b + n *（2 ^ n）) и как за O(n *（2 ^ n）
Поза форумом
AntonR написав:
Расскажите пожалуйста, как решать за O(b + n *（2 ^ n）) и как за O(n *（2 ^ n）
Обидва розв’язка мають однакову ідею:
Вирішуємо задачу на префіксі（для відрізка просто різниця）
Від загальної кількості（без обмежень на кількість в коробці）віднімемо варіанти де з коробки взяли більше ніж можливо（метод включення виключення）
Кількість варіантів рахуємо методом куль та перегородок（чи я як він там）
Поза форумом