Субота, 15.05.2021, 17:52
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 60
Головна » 2020 » Лютий » 1 » III ЕТАП ВСЕУКРАЇНСЬКОЇ ОЛIМПIАДИ З IНФОРМАТИКИ, I ТУР
22:28
III ЕТАП ВСЕУКРАЇНСЬКОЇ ОЛIМПIАДИ З IНФОРМАТИКИ, I ТУР
1 лютого 2020 року відбувся 1-й тур ІІІ обласного етапу Всеукраїнської учнівської олімпіади з інформатики 2019/2020 н.р.

Загальна iнформацiя
Вам дано 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сля змагання.

Задача A. Козак Вус i важлива знахiдка

Назва вхідного файлу:lesson.in
Назва вихідного файлу:lesson.out
Обмеження використання часу:0.25 second
Обмеження використання пам'яті:256 megabytes

Зовс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 (-108A, B, C, D ≤ 108) - числа на табличцi.
Формат вихідних даних:
Виведiть мiнiмальну кiлькiсть обертiв, якi потрiбно зробити Козаку Вусу, щоб важливiсть таблички була максимальною.
Приклади
lesson.inlesson.out
5 3 4 61
2 9 -4 133
2 6 3 00
Примiтка
У першому прикладi спочатку табличка має важливiсть 5, але, якщо обернути її один раз, то вона набуде максимальної важливостi, що рiвна 32.
У другому прикладi достатньо трьох обертiв, щоб табличка отримала своє максимальне значення важливостi, яке рiвне 171.
У останньому прикладi табличку повертати не треба, бо вона вже має максимальне значення важливостi, яке рiвне 18.
Оцiнювання
Кожний тест, крiм вхiдних, оцiнюється в 5 балiв.


Задача B. Козак Вус i цiкава задача

Назва вхідного файлу:room.in
Назва вихідного файлу:room.out
Обмеження використання часу:0.25 second
Обмеження використання пам'яті:256 megabytes

Вс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 ≤ 109, 1 ≤ p ≤ 1015) - довжини стор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ть будь-яку.
Приклади
room.inroom.out
2 2 14



YES
2 1
1 1
1 1
2 3 17 NO
5 8 46



YES
5 3
2 5
3 5
Прим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нюється вiд 1 до 4 балiв.


Задача C. Козак Вус i НСД

Назва вхідного файлу:gcdarray.in
Назва вихідного файлу:gcdarray.out
Обмеження використання часу:0.5 second
Обмеження використання пам'яті:256 megabytes

Сьогоднi Козак Вус зустрiвся зi своїм давнiм другом - Козаком Вухом. Вони дуже довго розмовляли, згадували своє дитинство та юнiсть. Так i зайшла мова про задачу, яку колись вони не змогли вирiшити на олiмпiадi з програмування.
Дано масив з n чисел. За один хiд можна одне з чисел збiльшити на 1. Вам необхiдно з’ясувати, за яку мiнiмальну кiлькiсть операцiй можливо отримати масив, який буде задовольняти такi умови:
  • aiai+1 для всiх i вiд 1 до n - 1.
  • найбiльший спiльний дiльник усiх чисел бiльший за 1.
Найбiльший спiльний дiльник множини додатних чисел = це найбiльше додатне число, що одночасно є дiльником усiх чисел з множини.
Формат вхідних даних:
Перший рядок мiстить одне цiле число t (1t5) - кiлькiсть тестiв. Далi слiдує опис кожного тесту.
Перший рядок опису кожного тесту мiстить одне цiле число n (1n104) - розмiр масиву.
Другий рядок опису кожного тесту мiстить n цiлих чисел a1, a2, . . . , an (1ai104) - числа масиву.
Формат вихідних даних:
Для кожного тесту в окремому рядку виведiть одне число - мiнiмальну кiлькiсть операцiй, якi необхiдно виконати для того, щоб масив задовольняв данi умови.
Приклади
gcdarray.ingcdarray.out
1
3
9 1 16
10


2
4
5 7 3 6
5
4 2 8 16 10
7
8



Примiтка
У першому прикладi можна перше та друге число збiльшити до 10, тодi найбiльший спiльний дiльник чисел з масиву буде рiвний два.
У першому тестi другого прикладу можна усi числа зробити рiвними 7.
ТУ другому тестi другого прикладу масив можна змiнити до масиву [4, 4, 8, 16, 16].
Оцiнювання
ОбмеженняДодатковi обмеженняБали
11 ≤ n ≤ 104Усi числа парнi 10
21 ≤ n ≤ 10-20
31 ≤ n ≤ 103-30
41 ≤ n ≤ 104-40


Переглядів: 444 | Додав: ivv
Всього коментарів: 0
avatar