1. Завдання олімпіади

Завдання ІІІ етапу Всеукраїнської олімпіади з інформатики у Вінницькій області

Час виконання – 5 годин.

Задача Boxes2023 Петрик - великий любитель наводити порядки серед своїх речей. Найбільша мрія Петрика - скласти усе, що він має, у одну велику коробку. Зараз він має три коробки з розмірами дна A*A, B*B, C*C і однаковою висотою. Петрик хоче придбати велику коробку розміру X*Y і тієї ж висоти, у яку б вмістилися всі три коробки разом. Звісно, що у Петрика не так багато грошей, тому він хоче зекономити, придбавши коробку з найменшою площею дна. Оскільки рахувати Петрик ще не навчився, він звернувся до вас за допомогою.Зверніть увагу, що коробки не можна класти на бік, ставити одна на одну або вкладати одна в одну, а всі стінки вкладених коробок повинні бути після упаковки або паралельні, або перпендикулярні стінкам придбаної  коробки.

Технічні умови. Програма Boxes2023 читає з клавіатури (стандартного пристрою введення) три натуральних числа A, B, C (1≤A,B,C≤10⁹) - розміри коробок.

Програма Boxes2023 виводить на екран єдине натуральне число - мінімальну можливу площу дна коробки, яка вмістить у собі усі три коробки.

Приклад:

Задача Privacy2023 В умовах війни дотримуватися правил кібербезпеки слід дуже ретельно. На жаль, користувачі месенджера BIBER часто цим нехтують, вкладаючи в тексти своїх повідомлень електронні адреси та номери телефонів третіх осіб, а це дуже цікавить ворожі спецслужби, які можуть перехоплювати такі текстові повідомлення. Розробники  BIBER вирішили самі убезпечувати  користувачів, додавши  до месенджера програму робота-«секретчика». Робот отримує текст - набір слів, розділених знаками « _».  Слово може містити літери латинської абетки, цифри, розділові знаки і символи «@».

Для забезпечення безпеки робот має приховувати номери телефонів та електронні адреси в тексті, а саме;

• номери телефонів, які починаються зі знаку «+» і продовжуються довільним непорожнім набором цифр
• адреси електронної пошти, які містять рівно один символ «@», ліворуч і праворуч від якого міститься довільна ненульова кількість літер, цифр та крапок

Вам доручено розробити робота, тобто програму, яка замінює слова, що підпадають під формат номеру телефона або електронної пошти, на три зірочки (***).

Технічні умови.  Програма Privacy читає з клавіатури (стандартного пристрою введення) єдиний рядок S (1 ≤ |S| ≤ 5*10⁴), де |S| - довжина рядка. Рядок складається з літер, цифр латинської абетки, а також знаків «@», «_» (нижнє підкреслення), “.” (крапка), «+» (плюс), «-»    (мінус).

Програма виводить на екран рядок з виконаними замінами слів-особистих даних.

Приклад:

  Задача  Spam.  Відомо, що на скриньку електронної пошти часто приходять листи рекламного характеру, листи зі шкідливими вкладеннями або посиланнями, які власник скриньки зовсім не очікував. Такі листи називаються спамом. У Васі є поштова скринька на одному з безкоштовних поштових серверів, і він, як усі нормальні люди, не любить спам. Розмір екрану обмежений і тому перша сторінка списку листів поштової скриньки не може відобразити всю пошту: користувач пошти може бачити не більше M листів і, очевидно, це будуть найсвіжіші з них.

Вася досить довго не перевіряв свою пошту і в його скринці накопичилося N листів, частина з яких є спамом. Якщо він бачить небажану пошту на першій сторінці, то виділяє всі спамерські листи, натискає кнопку «видалити», і виділені об'єкти переміщаються в папку «Видалені». Після цього на першій сторінці відображуються M найсвіжіших листів з решти і серед них може знову опинитися спам. У цьому випадку Вася знову виділяє небажану пошту і видаляє її зі скриньки описаним вище методом. Як тільки на першій сторінці перестане відображатися спам, Вася буде задоволений.

Технічні умови. Програма SPAM спочатку зчитує з клавіатури (стандартного пристрою введення) два цілих числа N і M (1≤N≤200000, 1≤M≤100000). Далі зчитується рядок, що містить N чисел (0 або 1), які визначають тип листа (1 – спам, 0 – ні) в порядку від найсвіжіших до найдавніших.  Програма SPAM виводить на екран два цілих числа – кількість листів, що будуть видалені, та кількість натискань на кнопку «видалити».

Приклад:

Задача Trex.Буратіно прийшов на Поле чудес, маючи P золотих монет та мішечок солі. Лисиця Аліса та кіт Базіліо повідомили йому, що якщо на цьому полі закопати T золотих монет (не обов’язково всі) і сказати заклинання «Трекс-пекс-фекс», то кількість монет подвоїться і можна буде викопати 2T золотих. Але якщо перед закопуванням T монет їх посолити, то після виголошення заклинання Буратіно викопає 2Т+1 монету. Буратіно має K порцій солі. Скільки разів потрібно сказати «Трекс-пекс-фекс», щоб отримати рівно S золотих?

Технічні умови. Програма Trex зчитує з клавіатури (стандартного пристрою введення) три цілих числа P, K, S (0≤K≤100, 0≤P,S≤10⁹). Програма виводить на екран число N – мінімальну кількість заклинань «Трекс-пекс-фекс», а потім N рядків, кожен з яких містить пару чисел – кількість закопаних монет та число 1 або 0. Одиниця виводиться, якщо золоті потрібно солити, і нуль – якщо ні. У випадку існування різних послідовностей дій Буратіно з мінімальною кількістю заклинань «Трекс-пекс-фекс» можна вивести будь-яку з них. Якщо отримати задану кількість монет неможливо, виводиться єдине число −1.

Приклад:

Задача Highway Пан Бізнесюк збирається у ділову поїздку з рідної Логарифмічної області країни Олімпія у далеке місто Експоненціальськ, причому їхати він буде власним мерседесом. Автомагістраль, що з’єднує Логарифмічну область з Експоненціальськом, складається з N послідовних фрагментів. Всередині кожного фрагменту можна їхати або по безплатній дорозі, витрачаючи a_i секунд, або по платній, витрачаючи c_i олімпійських центів та b_i секунд. Між цими фрагментами є транспортні розв’язки, через які можна з’їхати з однієї дороги на іншу. Такі переміщення вимагають q_i секунд (без різниці, з платної дороги на безплатну чи з безплатної на платну). При продовженні руху по тій самій дорозі таких затримок не виникає. Розпочати та завершити рух можна як по платній так і безплатній дорозі, тому розв’язки є  лише між першим  та  другим, другим та третім, …, (N–1) - м та N-м фрагментами. Пан Бізнесюк давно знає гасло «час – це гроші» і на даний момент оцінює одну секунду свого часу у K олімпійських центів, а тому пана Бізнесюка цікавить мінімізація величини P + K · T, де P – загальна сума сплачених дорожніх зборів, T – загальний витрачений час, зміст величини K пояснений у попередньому реченні.

Технічні умови.  Програма HIGHWAY зчитує з клавіатури у першому рядку два цілих числа N (2≤N≤60) та K (0≤K≤2023). Далі у другому рядку зчитується три цілих числа a1, b1 та c1 – час руху по безплатній та платній дорогах першого фрагменту та ціна проїзду по платній дорозі. У кожному з наступних N–1 рядків зчитується по чотири цілі числа qi, ai, bi та ci – час на переміщення між дорогами, час руху по безплатній та платній дорогах цього фрагменту і ціна проїзду по платній дорозі відповідно. Усі значення a_i, b_i та c_i (1≤i ≤N) у межах  від 1 до 10¹². Усі значення q_i (2≤i ≤N) у межах від 0 до 10⁹.

Приклад: