Завдання 2-го етапу всеукраїнської олімпіади школярів з інформатики

10-11  клас

Задача Kvadro. З кожним днем популярність квадрокоптерів зростає, різноманітність моделей і їх можливостей не перестають вражати уяву. Безпілотники стають невід'ємною частиною в багатьох сферах діяльності людини. Василь вирішив налагодити власний бізнес з виробництва квадрокоптерів. Він з'ясував, що за квадрокоптер, у якого N лопастей, покупці готові заплати-ти А+В*N гривень, але при цьому покупець не буде купувати квадрокоптер, якщо його вартість буде більша за С гривень. Визначте максимальне число лопастей квадрокоптера, який зможе придбати покупець.

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

Приклад

- - - - - - - - - - - - - - - - -

Задача Diagonals.  Опуклий  багатокутник має N вершин, з додатковим властивістю: він не має трьох діагоналей, що перетинаються в одній точці. Знайдіть кількість перетинів між парами діагоналей у такому багатокутнику. На малюнку показано один такий багатокутник з 6 вершин.
Технічні  умови.  Програма Diagonals  читає з пристрою стандартного введення одне ціле число N,  (3≤N≤100) – кількість вершин багатокутника. Програма виводить на пристрій стандартного виведення кількість перетинів між парами діагоналей.

Примітка: багатокутник опуклий, якщо всі його внутрішні кути менше 180 градусів

Приклади

- - - - - - - - - - - - - - - - -

Задача Guardian. На військовому полігоні є система окопів, що з літака виглядають, як відрізки прямих. Вночі, коли більшість солдатів  спить, троє вартових стоять в траншеях. Два вартових можуть побачити один одного, якщо є траншея по прямій  між ними і немає третього вартового в цій траншеї. З міркувань безпеки, охоронці повинні бути розміщені так, щоб кожен вартовий бачив двох інших. Скільки є способів розміщення вартових?

Технічні умови. Програма Guardian читає з пристрою стандартного введення ціле число N (1 ≤ N ≤ 20) – кількість траншей. Кожен з наступних  N рядків містить по 4  цілих числа (всі менші або рівні  1000 по модулю),  X1, Y1,  X2 ,Y2 - координати кінців відповідної прямої траншеї. Програма виводить на пристрій стандартного виведення єдине число – шукану кількість способів розміщення вартових.

Приклади

 - - - - - - - - - - - - - - - - -

Задача Carriage.  У плацкартному вагоні 54 місця, нумерованих числами від 1 до 54. Вагон розбитий на 9 купе. Перші 36 місць розташовані по ліву сторону від проходу, місця 1-4 знаходяться в першому купе, місця 5-8 - у другому і т.д.  У дев'ятому купе знаходяться місця з номерами 33-36. Праворуч від проходу знаходяться бічні місця, їх номери від 37 до 54, причому вони нумеруються в протилежному напрямку: місця 37 і 38 знаходяться навпроти дев'ятого купе, а місця 53 і 54 - навпроти першого. На малюнку наведена схема всіх місць у вагоні.

Група школярів їде на екскурсію  і буде всю дорогу спілкуватися. Тому їм потрібно купити місця в декількох поспіль купе разом з прилеглими бічними місцями.  Дано номери вільних місць в поїзді. Визначте, найбільшу кількість купе, які йдуть підряд і повністю вільні, разом з прилеглими бічними місцями.

Технічні умови. Програма Carriage читає з пристрою стандартного введення   в одному рядку через пропуск число N (0 ≤ N ≤ 54) - кількість вільних місць у вагоні. Наступні N чисел містять номери вільних місць - різні числа від 1 до 54 в довільному порядку. Програма  виводить на пристрій стандартного виведення єдине ціле число - найбільшу кількість купе, які йдуть підряд і повністю вільні (купе - 4 місця зліва від проходу і 2 бічних місця) в цьому вагоні. 

Приклади