1 лютого 2020 року відбувся 1-й тур ІІІ обласного етапу Всеукраїнської учнівської олімпіади з інформатики 2019/2020 н.р.

Вам дано 5 годин на рiшення 5 задач, кожна з яких оцiнюється в 100 балiв.

Ви можете зробити до 60 вiдправлень. Немає значення, як саме ви використаєте цi вiдправлення по задачах. Ви можете вiдправити будь-яку кiлькiсть рiшень на кожну задачу, але сумарна кiлькiсть вiдправлень по всiм задачам не має перевищувати 60.

Журi не гарантує, що iснують розв’язки на повний бал на таких мовах, як Pascal, Python та Java.

Пiд час олiмпiади суворо забороняється використовувати iнтернет, за виключенням сайту, на якому ви працюєте. Не можна використовувати будь-якi переноснi носiї iнформацiї.

Результати олiмпiади будуть доступнi на сайтi oi.in.ua пiсля змагання.

Зовсiм нещодавно мешканцi Потоколяндiї знайшли стародавню табличку розмiром 2 × 2, в якiй розташовано чотири числа A, B, C i D так:.

Вони вiдразу зрозумiли, що це дуже важлива iсторична знахiдка. Спершу вони вiднесли ї ї Козаку Вусу для того, щоб вiн визначив важливiсть цiєї таблички. На думку Козака Вуса, важливiсть таблички дорiвнює A · (B + C - D).

На жаль, правильне положення таблички невiдоме. Тому може статись таке, що однозначно визначити важливiсть таблички неможливо, оскiльки це значення залежить вiд того, скiльки разiв ї ї обернути.

Припустимо, що один оберт - це оберт за годинниковою стрiлкою на 90º.

Наприклад, якщо A = 41, B = 99, C = 100, D = 13, то важливiсть рiвна 41 · (99 + 100 - 13) = 7 626. А якщо ї ї один раз обернути, то 100 · (41 + 13 - 99) = -4 500.

Козак Вус хоче з’ясувати, яку максимальну можливу важливiсть може мати ця знахiдка. Але Вас вiн просить дiзнатись, яку мiнiмальну кiлькiсть обертiв потрiбно зробити для того, щоб важливiсть таблички була максимальною.

Перший рядок мiстить чотири цiлих числа A, B, C i D (-10⁸ ≤ A, B, C, D ≤ 10⁸) - числа на табличцi.

Виведiть мiнiмальну кiлькiсть обертiв, якi потрiбно зробити Козаку Вусу, щоб важливiсть таблички була максимальною.

У першому прикладi спочатку табличка має важливiсть 5, але, якщо обернути її один раз, то вона набуде максимальної важливостi, що рiвна 32.

У другому прикладi достатньо трьох обертiв, щоб табличка отримала своє максимальне значення важливостi, яке рiвне 171.

У останньому прикладi табличку повертати не треба, бо вона вже має максимальне значення важливостi, яке рiвне 18.

Кожний тест, крiм вхiдних, оцiнюється в 5 балiв.

Всiм вiдомо, що Козак Вус дуже захоплюється математикою. Сьогоднi, читаючи книгу «Конкретна математика», вiн знайшов дуже цiкаву задачу i вирiшив запропонувати Вам її розв’язати.

Є кiмната, яка має прямокутну форму. Одна з її сторiн має довжину n, а друга - m. Вам необхiдно з’ясувати, чи можливо роздiлити кiмнату на рiвно три окремi кiмнати з цiлими довжинами сторiн так, щоб загальний периметр цих кiмнат був рiвно p.

Наприклад, якщо n = 5, m = 8 i p = 46, то один з можливих варiантiв подiлу кiмнати такий:

Виведiть «YES» та розмiри кiмнат, якщо кiмнату можливо роздiлити на три окремi кiмнати, вiдповiдно до умови задачi, iнакше - «NO».

Перший рядок мiстить три цiлих числа n, m та p (1 ≤ n, m ≤ 10⁹, 1 ≤ p ≤ 10¹⁵) - довжини сторiн та периметр вiдповiдно.

Виведiть «YES», якщо кiмнату можливо роздiлити на три окремi кiмнати з цiлими довжинами сторiн так, щоб загальний периметр цих кiмнат був рiвний p, iнакше - «NO».

Якщо вiдповiдь «YES», тодi у кожному з наступних трьох рядкiв треба вивести розмiри вiдповiдної кiмнати. Розмiри можна виводити у будь-якому порядку. Якщо вiдповiдей декiлька, то виведiть будь-яку.

У першому прикладi можна подiлити кiмнату на три кiмнати з розмiрами 2 × 1, 1 × 1 та 1 × 1 вiдповiдно.

У другому прикладi неможливо подiлити кiмнату на три iз цiлими сторонами, так щоб загальний периметр був рiвний 17.

Третiй приклад пояснено в умовi.

Кожний тест, крiм прикладiв, оцiнюється вiд 1 до 4 балiв.

Сьогоднi Козак Вус зустрiвся зi своїм давнiм другом - Козаком Вухом. Вони дуже довго розмовляли, згадували своє дитинство та юнiсть. Так i зайшла мова про задачу, яку колись вони не змогли вирiшити на олiмпiадi з програмування.

Дано масив з n чисел. За один хiд можна одне з чисел збiльшити на 1. Вам необхiдно з’ясувати, за яку мiнiмальну кiлькiсть операцiй можливо отримати масив, який буде задовольняти такi умови:

Найбiльший спiльний дiльник множини додатних чисел = це найбiльше додатне число, що одночасно є дiльником усiх чисел з множини.

Перший рядок мiстить одне цiле число t (1 ≤ t ≤ 5) - кiлькiсть тестiв. Далi слiдує опис кожного тесту.

Перший рядок опису кожного тесту мiстить одне цiле число n (1 ≤ n ≤ 10⁴) - розмiр масиву.

Другий рядок опису кожного тесту мiстить n цiлих чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁴) - числа масиву.

Для кожного тесту в окремому рядку виведiть одне число - мiнiмальну кiлькiсть операцiй, якi необхiдно виконати для того, щоб масив задовольняв данi умови.

У першому прикладi можна перше та друге число збiльшити до 10, тодi найбiльший спiльний дiльник чисел з масиву буде рiвний два.

У першому тестi другого прикладу можна усi числа зробити рiвними 7.

ТУ другому тестi другого прикладу масив можна змiнити до масиву [4, 4, 8, 16, 16].