ЗАВДАННЯ ФІНАЛЬНОГО (real-time) туру Всеукраїнської Інтернет-олімпіади з інформатики NetOI-2018
https://new.netoi.org.ua/index_ua.php?lng=ua&cid=1979 10 лютого 2019 р.
Задача Resistor. Майстер з ремонту комп‘ютерної техніки Василь, ремонтуючи чергову материнську плату, відразу визначив причину її несправності – згорів резистор опором R Ом. Ще вчора Василь хвалився своїм колегам, що в нього є всі резистори з цілочисельними номіналами, від 1 Ом до R*(R+1) Ом (не менше двох резисторів кожного номіналу). На жаль, вночі підступні ворожі диверсанти викрали у Василя всі резистори опором R Ом, але, на щастя, не взяли жодного іншого резистора. Майстер Василь пам‘ятає з курсу фізики 8 класу формули для розрахунку опору при послідовному і паралельному з‘єднанні провідників, тому може легко замінити відсутній резистор двома резисторами, з‘єднаними послідовно або двома резисторами, з‘єднаними паралельно, але він не може визначити, скількома способами можна здійснити таку заміну. Допоможіть Василеві.
Технічні умови. Програма Resistor читає з пристрою стандартного введення (клавіатури) єдине натуральне число R ( 1 ≤ R≤ 1016); Програма виводить на пристрій стандартного виведення єдине число – шукану величину.
Приклад:
Введення 3
Виведення 3
Задача Taxi. У фірмі відбулися термінові технічні роботи, що завершилися пізно вночі. K (2≤K≤16) співробітників, котрі зазвичай користуються громадським транспортом, вимагають від менеджера доставки додому на таксі. Автомобілів таксі достатньо, щоб відправити кожного співробітника окремо. Але менеджер вважає, що то занадто дорого, бо автомобіль таксі може брати відразу кількох пасажирів (від 1 до 4), і поїздка в одному й тому самому таксі кількох людей, що живуть недалеко один від одного, обходиться значно дешевше. З іншого боку, менеджер згоден, що було б нечемно примушувати співробітників чекати надворі, поки таксі відвозить їхніх колег і повертається за ними. Тому менеджер шукає найдешевший спосіб доставити усіх співробітників за місцями проживання, при дотриманні таких умов:
- K співробітників розбивають на групи, кожна з яких містить 1, 2, 3 чи 4 людини; як розподілити людей по групам, вирішує менеджер.
- Співробітники з кожної однієї групи сідають у одне таксі.
- Таксі з усією групою відвозить додому когось одного з цієї групи, він там виходить; потім таксі з рештою групи відвозить додому когось наступного, і так доки не розвезе усіх. Порядок (кого з групи відвозити першим, кого другим, тощо) також визначає менеджер.
- Сам менеджер не є одним з K співробітників і не включається до жодної групи. Він їздить власним автомобілем, і не бажає нікого підвозити.
Фірма та місця проживання співробітників знаходяться у вершинах зваженого графа, де більшість ребер неорієнтовані (дороги з двостороннім рухом), деякі — орієнтовані (односторонні). Довжини ребер задані відразу як вартості проїзду цього ребра в таксі. Гарантовано, що граф сильно зв’язний, тобто з будь-якої вершини графа є шлях (котрий, як правило, складається з кількох послідовних ребер) до будь-якої іншої.
Вартість поїздки на таксі включає в себе не лише оплату за подолану відстань, тобто суму довжин (вартостей) пройдених ребер, а ще й плату за посадку, яка береться за кожен автомобіль (незалежно від кількості людей та відстані).
Технічні умови. Програма Taxi читає з пристрою стандартного введення перший рядок, що містить кількість вершин N (5≤N≤20000), потім кількість ребер M (N≤M≤50000); потім йдуть M рядків, кожен з яких містить по чотири числа: спочатку 1 чи 2 задає одно- чи двосторонній рух; потім два числа u, v (u≠v, 1≤v≤N, 1≤u≤N) задають, які вершини з’єднує це ребро (якщо рух односторонній, то з u до v); останнє число рядка (від 5 до 5000) — вартість проїзду в таксі по цьому ребру. Наступний рядок вхідних даних містить плату за посадку (ціле число від 500 до 50000). Наступний рядок містить номер вершини (від 1 до N), де знаходиться фірма. Наступний рядок містить кількість співробітників K (2≤K≤16). Наступний рядок є останнім і містить K чисел (від 1 до N кожне) — номери вершин, де живуть співробітники. Різні співробітники можуть жити в одній вершині, але гарантовано, що ніхто з них не живе у вершині, де розміщена фірма. Програма виводить на пристрій стандартного введення єдине число — мінімальну сумарну вартість перевезення всіх співробітників.
Приклади
|
Введення |
Виведення |
|
6 7 2 1 2 200 2 1 3 1000 2 1 4 1200 2 2 3 900 2 6 2 1300 2 6 4 200 2 4 5 100 1000 1 4 2 3 5 6 |
4500 |
|
6 7 2 1 2 200 2 1 3 1000 2 1 4 1200 2 2 3 900 2 6 2 1300 2 6 4 200 2 4 5 100 500 1 4 2 3 5 6 |
3700 |
Примітка. У першому прикладі, вартості 4500 можна досягти, коли один автомобіль таксі розвозить усіх, висаджуючи у порядку 2-й, 1-й, 4-й, 3-й. У другому, вартості 3700 можна досягти, якщо задіяти два автомобілі, один з яких везе 1-го та 2-го (висаджуючи саме в такому порядку), інший — 3-го та 4-го.
Задача Pies Дуже егоїстичний суб'єкт (ДЕС) побачив N пиріжків, викладених у ряд. Як виявилося, кожен пиріжок має свою смачність, тобто смачності всіх пиріжків задані числами a1, a2, ..., aN. За кожну хвилину можна взяти і з'їсти один крайній (або перший, або останній) пиріжок; після цього першим чи останнім стає той, який досі був другим чи передостаннім відповідно. За кожну хвилину смачність кожного пиріжка, який ще не почали їсти, зменшується на K% (K ціле, з проміжку 1<=K<=50, одне й те саме для всіх пиріжків). Кожні K% рахуються не від початкової смачності, а від поточної; наприклад, при K=20 та початковій смачності 1000 через хвилину вона буде 800, ще через хвилину 640, потім 512, потім 409.6, і так далі. Тому ДЕС хотілося б з'їсти їх якомога швидше... але, на жаль, з'їсти за одну хвилину більше, ніж один пиріжок, просто фізично не виходить. ДЕС має чималий досвід у тому, щоб робити дії, насправді вигідні в першу чергу йому самому, й видавати їх за благодійництво. Тому він швидко здогадався, що можна практично миттєво, віддавати крайні пиріжки бідним (хоч один, хоч багато, хоч лише з будь-якого одного краю, хоч з обох, хоч взагалі не віддавати). Пиріжки, віддані бідним, вже не можна з'їсти, зате така дія дає можливість швидше дістатися до пиріжків, розміщених десь посередині. Дуже егоїстичного суб'єкта зовсім не цікавить, що саме дістанеться бідним, він лише намагається використати цей привід для максимізації суми смачностей пиріжків, які він з'їсть сам. Яку максимальну суму смачностей він може собі забезпечити?
Технічні умови Програма Pies читає з пристрою стандартного введення два цілих числа -- спочатку кількість пиріжків N (2<=N<=2019), потім відсоток щохвилинного погіршення смачностей K (1<=K<=50, ціле число), а далі в тому ж рядку рівно N чисел -- смачності пиріжків a1, a2, ..., aN, усі ці числа цілі, в межах від 1 до 123456789. Числа розділено пропусками. Програма виводить на пристрій стандартного виведення єдине дійсне число -- максимально можливу суму смачностей того, що може з'їсти дуже егоїстичний суб'єкт. Відповідь вважатиметься правильною, якщо АБСОЛЮТНА похибка не перевищуватиме 0,001.
Приклад
Введення
7 10 2 1 1 123456789 1 2 1
Виведення.
123456792.339
Примітка. Тут дуже вигідно з'їсти пиріжок смачності 123456789, поки він ще нічого не втратив, для чого на самому початку доводиться віддати бідним або всі три лівіші за нього, або всі три правіші; серед цих варіантів, краще віддати всі три правіші, бо три лівіших можуть дати суму смачностей 2*0.9+0.81+0.729 = 3.339, що більше, ніж максимально можлива для трьох правіших сума
0.9+2*0.81+0.729 = 3.249.
Задача SugarBoy. Цукрові хлопчики зовсім не люблять воду. Цукровий хлопчик Оллі застряв у системі печер і тунелів. Раптом в одній з печер пробилося джерело води. Оллі хоче знати, скільки часу у нього є, поки вода не дійде до нього. Можливо, що вода ніколи не дійде до нього, за що Оллі, безперечно, буде дякувати небесам. Оллі знає, як облаштовані печери і яким чином вода заповнює тунелі. Отже:
- усі печери – порожнисті сфери діаметром 1м. Центри печер на плані розміщені у цілочисельних точках;
- деякі печери з’єднані тунелями. Усі тунелі прямі і з’єднують межу однієї печери з межею іншої. Пряма, якій належить тунель, що з’єднує 2 печери, пройде через центри печер, які з’єднуються цим тунелем;
- джерело пробивається в центрі певної печери. Продуктивність джерела - 1 кубічний метр за секунду
- вода починає наповнювати стартову печеру. Щойно вода доходить до рівня певного тунелю, вся вода, що прибуває, витікає у цей тунель, поки не наповнить усю систему печер, у яку прокладено цей тунель. Як тільки це відбулося, у стартовій печері вода продовжує накопичуватися. Це відбувається до того моменту, поки рівень води не дійде до наступного тунелю. Далі все повторюється - спершу наповнюється система печер, до якого цей тунель іде, а потім вже продовжує наповнюватись поточна печера. Ніяка два тунелі не сполучені безпосередньо між собою;
- вода не тече з печери рівнем нижче у печеру рівнем вище:
- тунелі і печери розміщені таким чином, що у жодній печері немає тунелів з однаковим рівнем. Крім того, немає з’єднаних печер з однаковим рівнем (тобто горизонтальним тунелем);
- джерело у початковій печері перестає працювати, як тільки ця печера повністю заповниться.
Технічні умови. Програма SugarBoy читає з пристрою стандартного введення числа N, M, A, B (2 ≤ N ≤ 100, 0 ≤ M ≤ N*(N-1)/2 , 1 ≤ A, B ≤ N) ) - кількість печер і кількість тунелів, а також номер печери, де пробилося джерело і номер печери, де стоїть Оллі. Далі слідують N пар цілих чисел (кожне за модулем не перевищує 5000), кожна з яких задає позицію центру чергової печери. Після цього слідують рівно M пар цілих чисел - номери печер, які з’єднує черговий тунель. Програма має виводить два рядки. Перший рядок містить SAFE, якщо Оллі нічого не загрожує або ж DANGER, якщо вода рано чи пізно дійде до Оллі. У першому випадку другий рядок повинен містити час, за який джерело у початковій печері перестане наповнюватись. У другому випадку слід вивести час, через який перша крапля води потрапить до печери Оллі. У обох випадках виведіть шукану величину у секундах з абсолютною точністю не гірш ніж у 3 знаки після коми.
Приклади:
|
Введення |
Виведення |
Коментар |
|
2 1 1 2 0 0 2 2 1 2
|
SAFE 0.523598 |
Перша і друга печери хоч і з’єднані, але друга печера вище, тому вода туди не потрапить. Джерело перестане текти, коли перша печера (об’ємом приблизно у 0.523598 метрів кубічних) повністю заповниться, тобто через 0.523598 секунди |
|
6 6 1 4 1 2 5 0 2 -1 9 -1 4 -4 4 -2 1 2 2 4 2 6 6 5 3 6 3 5 |
DANGER 1.3135079 |
Через деякий час після початку заповнення 1ої печери вода потрапить до другої. Там вона через деякий час піде у печеру номер 6, звідки одразу потече у печеру номер 5. Після наповнення п’ятої печери почне заповнюватись і печера номер 6. Як тільки вона заповниться, вода почне наповнювати другу печеру (у якій вже є деяка кількість води). Як тільки вода наповнить печеру до рівня тунелю між 2 і 4 тунелями, цукровому хлопчику стане непереливки - у його печері стане занадто волого. |
Задача MainPoint. Міністерство спорту країни вирішило провести справжнє автораллі світового рівня і їм терміново слід вирішити усі організаційні питання. Міністерство намагається виконати певні вимоги до прокладання траси гонок. Чиновники люблять хизуватися цифрами, а тому прагнуть, аби траса була максимальної довжини, а Міністр бажає, щоб траса обов’язково пролягала через столицю. Крім того, аби зменшити ризики і інші неприємні моменти, було вирішено зробити трасу у формі опуклого багатокутника таким чином, щоб повороти (тобто вершини багатокутника) завжди були у якомусь із міст. За наданою мапою міст вам треба віднайти довжину максимального маршруту, який би відповідав вказаним вимогам.
Слід також зазначити, що чиновники Міністерства спорту вважають опуклими також багатокутники, що вироджені у лінію, якщо їх можна отримати, спроектувавши деякий “справжній” багатокутник на якусь із прямих. Тобто, багатокутник (0, 0) - (1, 1) з точки зору Міністерства також опуклий.
Технічні умови. Програма MainPoint читає з пристрою стандартного введення єдине натуральне число - кількість міст (2 ≤ N≤ 10000) . Далі в тому ж рядку через пропуски слідує рівно N пар чисел - координати чергового міста на мапі. Усі координати не перевищують за модулем 5000. Столицею будемо вважати перше з міст.
Програма виводить на пристрій стандартного введення єдине дійсне число з точністю у 3 знаки після коми - максимальна довжина протяжності маршруту, який би задовольнив чиновників.
Приклади
|
Введення |
Виведення |
Коментар |
|
3 0 2 0 0 0 4
|
8.0000000 |
У даному випадку траса вироджена у лінію, але з точки зору чиновників це все одно опуклий багатокутник. |
|
5 0 0 -1 0 4 0 0 3 0 -3 |
16.0000000 |
Найкраща траса: |
Завдання підготували В. Бондар, Г .Непомняший, І. Порубльов, Ю.Пасіхов М. Стречень,