Шкільна олімпіада 2018 (розбір) | Articles

A. Хелловін

Виведемо суму цін найдешевших цукерок з кожного мішка.

Код розв’язку C++

Код розв’язку Python

B.Кольорові кульки

Якщо $a > b$, поміняємо $a$ й $b$, G й Y. Без обмеження загальності вважаємо, що $a \le b$. Виведемо $b-a$ разів G, потім — $a$ разів YG.

Код розв’язку C++

Код розв’язку Python

C. Нова кухня

Якщо $n$ і $m$ — непарні, то площа кухні також непарна, тому не вийде замостити всю підлогу. Нехай тепер хоча б одне із чисел $n$ і $m$ парне. Якщо $m$ непарне, то замостимо підлогу вертикальними плитами, якщо ж парне — горизонтальними.

Код розв’язку C++

Код розв’язку Python

D. Знайди паліндром

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

Паліндром парної довжини має два однакові центральні символи, а не один. Цей випадок розглядається так само.

Складність розв’язку: $O(n^2)$.

Код розв’язку C++

Код розв’язку Python