Вітаю Вас, Гість

Задача А. Цукерки

Рішення, що повністю моделюють процес взяття цукерок, тобто рішення яке зменшує число цукерок на 1 у кожній вазі у відповідності з описаним в умові алгоритмом, не буде вкладатися в обмеження по часу роботи програми і набиратиме до 70 балів.

Щоб отримати повне рішення зауважимо, що процес взяття цукерок містить цикл «ліва ваза, середня ваза, права ваза, середня ваза», який потім повторюється. За один прохід такого циклу число A зменшується на 1, число B зменшується на 2, число C зменшується на 1. Порахуємо, скільки разів буде виконано цикл - це мінімум з чисел A, [B/2] і C (під записом [B/2] мається на увазі ціла частина від ділення B на 2, тобто операція цілочисельного ділення). Запишемо кількість проходів циклу в змінну k і зменшимо значення змінних A і C на k, а значення змінної B на 2k. За k виконань циклу сумарно буде взято 4k цукерок.

Наступний прохід циклу не буде виконано повністю. Подивимось на значення змінних A, B, C в тому порядку, в якому беруться цукерки з відповідних ваз. Якщо A=0, то не можна на наступному кроці взяти цукерку з першої вази, і відповідь буде 4k. Якщо B=0, то буде взята цукерка з першої вази, але у другій вазі цукерки закінчились, тому відповідь буде 4k+1. Якщо ж C=0, то, аналогічно, можна взяти ще дві цукерки з лівої і  середньої вази, і відповідь буде 4k+2. Нарешті, якщо усі ці умови не виконались, то відповідь буде 4k+3.

 

Задача В. Вступна кампанія

Для кожного вікна зберігаємо час його звільнення (спочатку для усіх вікон це нуль).

 Перебираємо студентів в порядку зростання їх номерів.

Знаходимо вікно, в яке піде студент, тобто те, у якого час звільнення мінімальний. Якщо таких кілька, то вибираємо вікно з мінімальним порядковим номером.

Перераховуємо час звільнення вікна Tj: Tj = Tj + max{Ai, Bj}

Відповідь - максимум з усіх Tj.

 

Задача С. Красивий ряд

Для вирішення цієї задачі застосуємо метод динамічного програмування по бітмасках. Маска mask буде говорити нам зайняті позиції чисел, тобто якщо i — тий біт маски дорівнює одиниці, це означає, що число на позиції i, ми вже використали. Dp[mask][i]  - кількість способів розташувати маску mask, де i — останнє число, що було використано в масці. Відповіддю на задачу буде сума всіх позиції для маски, що складається повністю з 1. Для вирішення задачі побудуємо допоміжній масив — матрицю переходів. Перехід з i в j можливий, якщо числа мають однакову кількість одиниць в двійковій або в трійковій системі числення. Початкове значення для всіх i, dp[0][i] = 1. Переберемо маску mask та останнє число, що було використано i та нову позицію j, в яку будемо робити перехід, та для якої вірно, що j — тий біт маски дорівнює 0. Та зробимо перехід з dp[mask][i] в нову маску, де на позиції j тепер 1, та останнє число дорівнює  jdp[new_mask][j].

Задача D. Шоколадна фабрика "ПанСте"

Найпростішим у реалізації рішенням, на наш погляд, є перебір двійковим пошуком відповіді. Природньо, що якщо відповідь X, то можна отримати будь-яку кількість комплектів між 0 і X, і не можна отримати кількість X + 1, X + 2 і так далі. Тому двійковий пошук можна застосувати. Перевірити ж, чи можливо отримати деяку кількість комплектів K, можна таким чином.

Зафіксуємо якийсь один тип цукерок як допоміжний. Для всіх інших підрахуємо, у скількох з K комплектів він може брати участь: якщо кількість цукерок якогось типу Q менше K, цукерки цього типу можна використовувати тільки в Q комплектах, в іншому ж випадку їх вистачить на усі K комплектів. Всі типи цукерок, яких не вистачає на всі K комплектів, повинні бути заповнені тим типом цукерок, який був обраний допоміжним. Більше того, в одному комплекті повинно бути не більше одного такого заміщення. Відповідно, має виконуватися дві умови:

1) Загальна кількість відсутніх цукерок за всіма типами, крім допоміжного, не повинно перевершувати кількість цукерок цього самого допоміжного типу;

2) Загальна кількість відсутніх цукерок за всіма типами, крім допоміжного, не повинна перевершувати K.

Щоб краще зрозуміти логіку, розглянемо приклад з чотирма типами цукерок. Є всього 4 різних варіанти комплекту: (1,2,3), (1,2,4), (1,3,4) і (2,3,4). Скажімо, оптимальний варіант - видати A штук комплекту (1,2,3), B штук комплекту (1,2,4), C штук комплекту (1,3,4) і D штук комплекту (2,3,4). Тоді A + B + C не повинно перевершувати загальну кількість цукерок типу 1.

 

Задача E. Дужковедення

Зауваження: у правильної дужкової послідовності кількість відкритих і закритих дужок співпадає, а також на любому префіксі кількість відкритих дужок не менше, чим закритих.

Для кожної позиції i зарання обчислимо різницю кількості відкритих і закритих дужок на подрядку 1..i (balancei)

Підрядок i..j буде правильним, якщо:

1) balancei-1 = balancej

2) min(balancek) ≥ balancej, де k з проміжку i..j

Для пошуку мінімуму на відрізку можна застосувати дерево відрізків, що дає складність O(N log N), або ж знаходити мінімум в черзі, наприклад, з використанням двох стеків (O(N)).