Розбір Algotester Beginners Contest 2026 | Статті

A. Банани по акції

Щоб отримати знижку, спершу потрібно купити \(k\) бананів за \(ak\) гривень. Якщо \(x<ak\), грошей на це не вистачає, тому можна купити лише \(\left\lfloor x/a\right\rfloor\) бананів за початковою ціною. Інакше купуємо перші \(k\) бананів, а решту грошей витрачаємо на банани по \(b\) гривень. Отже, відповідь: \[\begin{cases} \left\lfloor \dfrac{x}{a}\right\rfloor, & x<ak,\\[0.6em] k+\left\lfloor \dfrac{x-ak}{b}\right\rfloor, & x\ge ak. \end{cases}\] Для добутку \(ak\) потрібен 64-бітний цілий тип.

Складність розв’язку — \(O(1)\) за часом і пам’яттю.

B. Ланцюжок доміно

Спробуємо обидва способи покласти першу доміношку: без перевороту та з переворотом. Для кожного з них пройдемо решту доміношок зліва направо, зберігаючи число на правому кінці ланцюжка.

Наступну доміношку потрібно повернути так, щоб число зліва збігалося з кінцем ланцюжка. Якщо підходить лише одна половина, орієнтація визначена однозначно; якщо обидві, числа на половинах однакові й переворот нічого не змінює. Якщо не підходить жодна половина, ця спроба невдала. Отже, після вибору орієнтації першої доміношки жодного додаткового перебору не потрібно. Якщо хоча б одна з двох спроб дозволяє викласти всі доміношки, відповідь TAK, інакше — NI.

Складність розв’язку — \(O(n)\) за часом і \(O(n)\) за пам’яттю для збереження послідовності перед двома проходами.

C. Кешбек

Для кожної із шести доступних категорій порахуємо суму всіх покупок у ній, позначимо її \(A_j\). Покупки з іншими категоріями ігноруємо. Якщо підключити категорію \(j\), вона дасть \(p_jA_j/100\) гривень кешбеку.

Внески різних категорій незалежні, тому достатньо вибрати дві категорії з найбільшими значеннями \(p_jA_j\). Важливий саме загальний кешбек, а не лише відсоток чи сума покупок. Добуток \(p_jA_j\) — це кешбек у копійках, тож усі обчислення можна виконати в цілих числах. Суму двох найбільших добутків виводимо як гривні та копійки, залишаючи рівно дві цифри після крапки.

Категорій рівно шість, а довжини назв обмежені сталою, тому складність — \(O(n)\) за часом і \(O(1)\) за додатковою пам’яттю.

D. Спеціалізована вчена рада

Нехай \(c\) — кількість вчених із ЛНУ. Решту вчених збережемо в окремому списку можливих опонентів. Переберемо всі пари опонентів з індексами \(i<j\) і порахуємо кількість \(p\) пар, у яких вчені працюють у різних закладах. Для кожної такої пари трьох членів ради з ЛНУ можна вибрати \(\binom{c}{3}\) способами. Отже, за першим правилом існує \(\binom{c}{3}p\) складів ради. Якщо це число додатне, воно і є відповіддю: застосовувати друге правило заборонено.

Інакше переберемо всі трійки опонентів з індексами \(i<j<k\). Трійка підходить, якщо всі три номери закладів попарно різні. Якщо таких трійок \(q\), відповідь дорівнює \(\binom{c}{2}q\). Умови на індекси гарантують, що кожну пару та трійку пораховано рівно один раз.

Тут \(\binom{c}{2}=c(c-1)/2\), а \(\binom{c}{3}=c(c-1)(c-2)/6\); якщо людей для вибору не вистачає, відповідна кількість способів дорівнює нулю. Для відповіді потрібен 64-бітний цілий тип.

Складність розв’язку — \(O(n^3)\) за часом і \(O(n)\) за пам’яттю. За \(n\le 500\) маємо не більше ніж \(\binom{500}{3}<2{,}1\cdot 10^7\) трійок, тому такого перебору достатньо для ліміту 2 секунди. Також існує розв’язок за \(O(n+m)\) часу. Спробуйте придумати його.

E. Екранізація

Нехай \(c\) — кількість пробілів та символів \ у рядку. Спочатку \(c\) — це просто кількість пробілів у початковому реченні. Кожен пробіл залишається на місці й під час кожної операції отримує перед собою новий символ \. Кожен уже наявний символ \ при цьому подвоюється. Після кожної операції \(c\) збільшується вдвічі.

Якщо \(|s|>n\), відповідь 0. Якщо \(|s|\le n\) і \(c=0\), довжина не змінюється, тому відповідь \(-1\). В інших випадках моделюємо операції, зберігаючи лише довжину тексту та змінну \(c\). Спочатку довжина дорівнює \(|s|\), а \(c\) це кількість пробілів. За одну операцію довжина збільшується на \(c\), після чого подвоюємо \(с\). Зупиняємося, щойно довжина стане строго більшою за \(n\). Приріст довжини щоразу подвоюється, тому за \(n\le 10^9\) вистачить не більше 30 операцій. Сам рядок будувати не потрібно.

Складність розв’язку — \(O(|s|+\log n)\) за часом і \(O(1)\) за додатковою пам’яттю.

F. ФОП

Нехай новий річний дохід дорівнює \(b\). Зараз після сплати податку залишається \(a(100-x)/100\) гривень, а після збільшення доходу залишатиметься \(b(100-y)/100\). Потрібно, щоб \[b(100-y)>a(100-x), \qquad\text{тобто}\qquad b>\frac{a(100-x)}{100-y}.\] Тому мінімальний цілий дохід: \[\left\lfloor\frac{a(100-x)}{100-y}\right\rfloor+1.\] Оскільки \(y>x\), отримане число автоматично більше за \(a\). Нерівність строга, тому одиницю потрібно додати навіть тоді, коли ділення виконується без остачі.

Складність розв’язку — \(O(1)\) за часом і пам’яттю.

G. Emoji

Будь-який запис смайлика лежить між двома сусідніми двокрапками, адже в назві можуть бути лише літери. Два такі записи можуть мати спільну двокрапку, тому замінити їх обидва не завжди можливо. Наприклад, у :a:bbbb: вигідніше замінити другий запис, хоча перший трапляється раніше. Після заміни нових записів для замін не виникає: смайлик не бере участі в наступних операціях. Отже, потрібно вибрати набір записів, які не перетинаються.

Позначимо \(dp_i\) — найменшу довжину, до якої можна скоротити перші \(i\) символів; \(dp_0=0\). Якщо залишити символ \(i\) без змін, отримаємо перехід \(dp_i=dp_{i-1}+1\). Якщо в позиції \(i\) закінчується запис доступного смайлика, який починається в позиції \(l\), можна замінити весь запис одним символом: \[dp_i=\min\bigl(dp_i,\ dp_{l-1}+1\bigr).\] Кожна оптимальна відповідь закінчується або незаміненим символом, або смайликом, тому ці переходи враховують усі можливості. Відповідь — \(dp_n\).

Для перевірки назв достатньо зберегти їх у звичайній впорядкованій множині рядків, наприклад set у C++. На кожній двокрапці перевіряємо, чи є в множині непорожній фрагмент між нею та попередньою двокрапкою. Якщо є, застосовуємо перехід із заміною смайлика.

Нехай \(T=\sum |t_i|\). Сумарна довжина фрагментів між сусідніми двокрапками не перевищує \(n\). З урахуванням порівнянь рядків складність побудови множини та всіх перевірок — \(O\bigl((n+T)\log(k+1)\bigr)\) за часом; пам’ять — \(O(n+T)\). За \(n,T\le 2\cdot 10^5\) цього достатньо. Також існує розв’язок за \(O(n+T)\) часу. Спробуйте придумати його.

H. В ліс по гриби

Йти по гриби варто тоді й лише тоді, коли вночі падав дощ. Тому відповідь повністю збігається з вхідним рядком: для TAK виводимо TAK, для NI — NI.

Складність розв’язку — \(O(1)\) за часом і пам’яттю, оскільки довжина рядка обмежена сталою.

I. Як карта ляже

Кожна вибрана з руки карта * зрештою додає рівно одне число з колоди: усі проміжні карти * лише змушують брати наступну карту. Тому, якщо вибрати \(t\) зірочок, найгірший порядок колоди дасть суму \(t\) найбільших числових карт у ній. Такий порядок можливий, а більшої суми отримати не можна.

Відсортуємо числові карти в руці за зростанням, а числові карти в колоді — за спаданням. Нехай \(A_j\) — сума \(j\) найменших чисел у руці, а \(B_j\) — сума \(j\) найбільших чисел у колоді; \(A_0=B_0=0\). Ці префіксні суми обчислюються одним проходом після сортування.

Нехай у руці є \(q\) числових карт і \(z\) зірочок. Переберемо кількість вибраних зірочок \[\max(0,k-q)\le t\le\min(k,z).\] Для фіксованого \(t\) найвигідніше взяти \(k-t\) найменших числових карт із руки. Тоді найбільша можлива сума очок дорівнює \(A_{k-t}+B_t\). Якщо хоча б для одного допустимого \(t\) ця сума не перевищує \(s\), відповідь TAK, інакше — NI. Зірочки в колоді до масиву чисел не додаємо: самі по собі вони очок не дають.

Складність розв’язку — \(O(n\log n+m\log m)\) за часом і \(O(n+m)\) за пам’яттю. Числа на картах не перевищують 1000. Використавши це обмеження, можна отримати розв’язок за \(O(n+m+1000)\) часу. Спробуйте придумати його.

J. Платіжка

За місяць було спожито \(b-a\) кіловат-годин електроенергії. Кожна коштує \(x\) гривень, тому сума до сплати дорівнює \[(b-a)x.\]

Складність розв’язку — \(O(1)\) за часом і пам’яттю.

K. Доміношки

Йдемо зліва направо й підтримуємо \(R\) — найбільше значення \(x_j+h_j\) серед доміношок, які вже падають. Якщо \(x_i<R\), поточну доміношку зачепить одна з попередніх. Інакше її потрібно штовхнути вручну й збільшити відповідь на один. Після цього в обох випадках оновлюємо \(R\) до \(\max(R,x_i+h_i)\). Спочатку \(R=0\), а відповідь дорівнює нулю.

Кожен ручний поштовх необхідний: якщо \(x_i\ge R\), жодна попередня доміношка не може зачепити поточну, а наступні падають лише праворуч. Отже, алгоритм виконує мінімальну кількість ручних поштовхів. Зверніть увагу на строгу нерівність \(x_i<R\): правий кінець проміжку падіння не входить до нього.

Доміношки вже впорядковані за координатами, тому складність — \(O(n)\) за часом і \(O(1)\) за додатковою пам’яттю.

L. CAPS LOCK

Послідовно переглянемо всі натискання, зберігаючи стан Caps Lock, спочатку вимкнений. На символі # змінюємо стан на протилежний і нічого не друкуємо. Для літери друкуємо її у верхньому регістрі, якщо Caps Lock увімкнений, або без змін, якщо вимкнений. Після кожного кроку стан відповідає кількості вже оброблених перемикань, тому всі літери матимуть потрібний регістр. Якщо натискань літер не було, результат — порожній рядок.

Складність розв’язку — \(O(n)\) за часом і \(O(1)\) за додатковою пам’яттю, якщо виводити літери одразу; для збереження всього результату потрібно \(O(n)\) пам’яті.