Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Задания IV тура NetOI-2015

Задача Garden2016.  Згідно з земельним кодексом,  кожен мешканець Країни Дурнів має право на землю. На останній сесії парламент прийняв поправки, згідно яких:

1.    Громадянин має право лише на одну ділянку землі;

2.    Кожна ділянка має форму n-кутника;

3.    Ділянка не може мати гострих кутів (гострі кути, за повір‘ям, негативно впливають на родючість землі);

4.    Земельний комітет призначає громадянину довжини  сторін ділянки;

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

Технічні умови. Програма Garden2016 читає з клавіатури спочатку натуральне число n  (n <=50), а далі у наступному рядку   n дійсних чисел через пропуски, не менших 1 і не більших 100000 – довжини сторін в порядку обходу багатокутника. Програма виводить на екран шукану площу. Гарантується, що вхідні дані завжди задовольняють вимоги пунктів 1-3. Результат не заокруглюйте, виводьте з максимально можливою точністю.

Приклад

Введення

6

 15.0  15.0  7.0  15.0  15.0  7.0

Виведення

3.8400000000000000E+0002 

Задача Substr. Епіграф Автор тексту цієї задачі випадково підслухав розмову двох «крутих» олімпійців-програмістів: «Ну, і що, що за «квадрат»? Але ж пройшло на 100%! Там тайм-ліміти нормальні… 2 секунди на будь-який тест...».

Знайдіть всі унікальні підрядки рядка S. Рядок S містить виключно малі і великі літери латинського алфавіту. У рядку може бути від 1 до 104 літер.

Технічні умови. Програма Substr читає з пристрою стандартного введення рядок S. Програма виводить на пристрій стандартного виведення ціле число - кількість унікальних підрядків введеного рядка.

Приклад

Введення

yaVasya

Виведення

24

 

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

Технічні умови Програма Sheep зчитує з пристрою стандартного введення 3 цілих числа: n- кількість кутів будівлі (натуральне число, не менше ніж 3 і не більше 10000), t- номер вершини, до якої прив’язана вівця, L – довжина ланцюга (натуральне число, L<=100000). Гарантується, що довжина ланцюга не перевищує півпериметра будівлі. Наступні n рядків містять координати вершин, а саме (i+1)-й рядок містить цілі координати i-тої вершини (для i>=1). Жодна з координат за абсолютною величиною не перевищує 10000. Вершини задано в порядку обходу многокутника за чи проти годинникової стрілки.

Програма виводить на пристрій стандартного виведення єдине число – площу випасу з максимально можливою точністю.

Sheep

Приклад

Введення

4 1 1

0 0

1 0

1 1

0 1

Виведення

2.35619449

Пояснення до прикладу. На рисунку чорним зображено будівлю, а жовтим – місця на яких може випасатись вівця.

 

Задача Hanoy2016. Ханойські вежі являють собою три стержні. На першому знаходиться N дисків різних розмірів. Верхній диск має розмір 1, наступний 2, і т.д., найнижчий диск має розмір N. Герой олімпіад Ваcиль Пупенко перекладає диски оптимальним способом з першого(стартового) на другий (цільовий) стержень за правилами ханойських веж (за один хід перекладається один диск, не можна класти більший диск на менший). Відомо розташування дисків на певному етапі операції. Допоможіть Васі порахувати кількість перекладань дисків, що вже відбулися.

 

Технічні умови. Програма Hanoy2016 читає з пристрою стандартного введення кількість дисків N (1<= N<=64) і далі через пропуск N чисел, кожне з яких дорівнює 1, 2 або 3 – розташування дисків, починаючи з найменшого. Програма виводить на пристрій стандартного виведення єдине число – кількість перекладань. Якщо задане розташування дисків не траплялось, вивести -1.

 

Приклади

 

Введення 2 3 2

 

Виведення 2

 

Введення 3 2 1 3

 

Виведення -1

 

Задача Scientist. На Великій-Великій Планеті (ВВП) Дуже Видатний Вчений (ДВВ) вирішив визначити найменшу висоту (він назвав її критичною), з якої має впасти Великий Горіх (ВГ), щоб він розбився. ДВВ збирається кидати горіхи, цілком однакові за міцністю (тому в них однакова критична висота!), з різних висот. Оскільки він працює на ВВП, висоти можуть бути дуже великими, і завжди вимірюються цілими числами! Якщо ВГ упав із певної висоти й не розбився, вчений його підбирає та продовжує експеримент, міцність ВГ при цьому не змінюється. Яка найменша кількість кидків гарантує вченому точне визначення критичної висоти? Можливі випадки, коли після успішного завершення експерименту у ДВВ залишиться певна кількість цілих горіхів.

Технічні умови. Програма Scientist читає з пристрою стандартного введення два цілих числа через пропуск -максимальну висоту h (1<=h<=109 ), для даного експерименту, та початкову кількість ВГ n (2<=n<=100). Шукану кількість кидків k програма має вивести на пристрій стандартного виведення.

Приклад

Введення

210 5

Виведення

8

Завдання підготували  В.Боднар, А.Зуєв, Й.Ентін, Г.Кравець Г.Непомнящий, О.Островський, Ю.Пасіхов

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"