Завдання ІІІ (міського) етапу 2014 року

Завдання ІІІ (міського) етапу 2014 року

1. Лижний спорт

Максимальна оцінка: 200 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: skiing.in
Вихідний файл: skiing.out
Програма: skiing.*

      Як відомо, нещодавно Україна подала заявку на проведення зимових Олімпійських ігор 2022 року. Щоб збільшити шанси перемоги цієї заявки над іншими, нам потрібно спроектувати якнайдосконаліші олімпійські об’єкти. Одним із таких об’єктів є лижна траса, яку прокладатимуть уздовж фрагмента вузького плоскогір’я. Плоскогір’я є низкою пологих підйомів і спусків. Якщо його розбити на ділянки завдовжки 1 км, кожну ділянку можна охарактеризувати як підйом або як спуск. На оптимальній для спортсменів трасі кількість ділянок-підйомів і кількість ділянок-спусків мають збігатися.

      Завдання
      Знаючи, в якій послідовності йдуть підйоми і спуски плоскогір’я, визначте довжину найдовшої потенційної траси, тобто такого фрагмента плоскогір’я, що містить однакову кількість підйомів і спусків.

      Вхідні дані
      У першому рядку вхідного файлу вказано натуральне число n — кількість кілометрових ділянок плоскогір’я. У другому рядку записано n чисел, що задають рельєф плоскогір’я. Кожне з цих чисел — або одиниця (підйом), або нуль (спуск). Плоскогір’я не є круглим, тобто перша та остання його ділянки не сполучені між собою.

У 40 % тестів 2 ≤ n ≤ 100.
У 30 % тестів 100 < n ≤ 10 000.
У 30 % тестів 10 000 < n ≤ 1 000 000.

Усі тести мають однакову вартість.

      Вихідні дані
      Єдиний рядок вихідного файлу повинен містити довжину в кілометрах найдовшого фрагмента плоскогір’я, що містить однакову кількість підйомів і спусків. Якщо жодного такого фрагмента немає, виведіть число 0.

      Приклади

skiing.in	skiing.out
`6 1 1 1 0 0 1`	`4`
`5 0 1 1 1 1`	`2`
`4 0 0 0 0`	`0`
`6 1 0 1 0 1 0`	`6`

      Пояснення до прикладів
      У першому прикладі фрагмент 1 1 0 0 довжини 4 містить по два під-йоми та спуски. Таку саму властивість має і фрагмент 1 0 0 1. Довших фрагментів, що містять однакову кількість підйомів і спусків, задана послідовність не має.
      У другому прикладі фрагмент 0 1 довжини 2 містить по одному підйому і спуску. Довших фрагментів із рівною кількістю підйомів і спусків немає.
      У третьому прикладі, як видно, жоден фрагмент не містить однакової кількості підйомів і спусків.
      У четвертому прикладі найдовшим фрагментом, що містить рівну кількість підйомів і спусків, є вся послідовність.

2. Голосування

Максимальна оцінка: 200 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: election.in
Вихідний файл: election.out
Програма: election.*

      По завершенні прийому заявок на проведення Олімпіади під час спеціального засідання Міжнародного олімпійського комітету проходять вибори заявки-переможця. Процедура голосування така. Спершу всі делегати, присутні на засіданні, голосують за будь-яку одну з n отриманих заявок-претендентів. Заявку, що набрала найменше голосів, виключають зі списку, після чого голосування повторюють — уже між n – 1 претендентом. Далі знову виключають заявку, що набрала найменше голосів, і голосування проводять ще раз. Цю процедуру повторюють доти, доки не залишиться єдина заявка, яка й стає переможцем.
      Назвімо послідовним такого делегата, що має список уподобань (перестановку чисел від 1 до n) і в кожному раунді голосує за ту заявку, що з-поміж тих, які ще залишилися, стоїть першою в його списку. Дехто з делегатів може й не бути послідовним і голосувати, наприклад, випадковим чином.

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

      Вхідні дані
      У першому рядку вхідного файлу вказано натуральне число n — кількість поданих заявок. Далі йде n рядків, що містять невід’ємні цілі числа: перший з цих рядків відповідає заявці, що перемогла; наступний рядок — заявці, що вибула в останньому раунді; …; передостанній рядок — заявці, що вибула другою; останній рядок — заявці, що вибула першою. Число на позиції j в рядку, що відповідає деякій заявці, дорівнює кількості делегатів, які проголосували за дану заявку в j-му раунді. Таким чином, в k-му рядку вхідного файлу записано n + 2 – k чисел, 3 ≤ k ≤ n + 1, а у другому рядку записано n – 1 число. Відомо, що кількість голосів, відданих за заявку, яка вибула в деякому раунді, строго менша за кількість голосів, яку здобула в цьому раунді будь-яка інша заявка. Сума голосів у кожному з раундів однакова і дорівнює кількості делегатів, присутніх на засіданні. І кількість заявок, і кількість делегатів не менші за 2 і не перевищують 100.

      Вихідні дані
      У першому рядку вихідного файлу виведіть число m — найбільшу можливу кількість послідовних делегатів. Наступні m рядків повинні задавати приклад уподобань, які могли мати m послідовних делегатів. У кожному з цих рядків має міститися по n чисел — перестановка чисел від 1 до n, що відповідає порядку уподобань відповідного делегата. Число 1 відповідає при цьому заявці, що перемогла; число 2 — заявці, що вибула в останньому раунді; …; число n – 1 — заявці, що вибула другою; число n — заявці, що вибула першою. Лівіше у списку повинні стояти номери привабливіших заявок, а правіше — менш привабливих, тобто делегат щоразу голосуватиме за ту заявку, номер якої стоїть якомога ближче до початку його списку. Порядок m рядків, що задають уподобання послідовних делегатів, може бути довільним. Якщо можливих прикладів уподобань m делегатів є декілька, виведіть будь-який із них.
      Якщо перший рядок вихідного файлу, створеного вашою програмою, міститиме правильну відповідь (найбільшу можливу кількість послідовних делегатів), але наступні рядки будуть порожніми, відсутніми або задаватимуть неправильний приклад уподобань, то за відповідний тест буде нараховано 40 % балів.

      Приклади

election.in	election.out
`3 1 2 2 1 0`	`2 1 2 3 2 1 3`
`5 3 1 2 7 3 6 9 5 3 5 1 2 0 1`	`6 1 2 3 4 5 2 1 3 4 5 2 1 3 4 5 2 1 3 4 5 3 2 1 4 5 5 2 1 3 4`
`2 2 1`	`3 1 2 1 2 2 1`

      Пояснення до прикладів
      У першому прикладі маємо трьох делегатів: 1 + 2 + 0 = 2 + 1 = 3. Усі три не можуть бути послідовними, бо інакше проголосували б у другому раунді так само, як і в першому. Разом із тим два з трьох делегатів можуть бути послідовними, при цьому один з них серед трьох заявок надає перевагу першій, а інший — другій. Непослідовний же делегат у першому раунді голосує за другу заявку, а в другому — за першу.
      У другому прикладі маємо 12 делегатів:
3 + 3 + 3 + 2 + 1 = 1 + 6 + 5 + 0 = 2 + 9 + 1 = 7 + 5 = 12.
Щонайбільше шість із них можуть бути послідовними і голосувати відповідно до вподобань, поданих у прикладі вихідного файлу. Тоді результати голосування, подані у прикладі вхідного файлу, досягаються, якщо інші шість непослідовних делегатів голосують таким чином: у першому раунді по 2 за першу, третю і четверту заявки; у другому раунді 2 за другу і 4 за третю заявку; у третьому раунді 1 за першу і 5 за другу заявку; в останньому раунді всі 6 за першу заявку.
      У третьому прикладі кожен із трьох делегатів, присутніх на голосуванні, може бути послідовним.

3. Олімпійське містечко

Максимальна оцінка: 200 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: village.in
Вихідний файл: village.out
Програма: village.*

      Якщо Україна хоче здобути право приймати Олімпійські ігри, нам треба подбати не лише про спортивні споруди, але й про туристичну інфраструктуру, а також про житловий комплекс, де мешкатимуть під час Ігор спортсмени, — про Олімпійське містечко. Одним із аспектів створення сучасного Олімпійського містечка повинні стати «розумні» програмні засоби, що забезпечуватимуть комфортне буття олімпійців. Одну з таких програм маєте написати саме ви.
      Уявімо, що на Олімпіаду прибула команда, яка складається з парної кількості спортсменів, і її вирішили розселити у двомісні номери. Звісно, у кожного спортсмена є побажання стосовно того, з яким саме членом команди він або вона хотіли б поселитися в одному номері.

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

      Вхідні дані
      У першому рядку вхідного файлу записано парне натуральне число n — кількість членів команди. Усіх спортсменів занумеровано натуральними числами від 1 до n. У другому рядку вказано n натуральних чисел у межах від 1 до n кожне: k-те з цих чисел задає номер члена команди, з яким би хотів поселитися k-й спортсмен (цей номер, природно, не дорівнює самому числу k).

У 40 % тестів 4 ≤ n < 20.
У 30 % тестів 20 ≤ n ≤ 2000.
У 30 % тестів 2000 < n ≤ 200 000.

      Усі тести мають однакову вартість.

      Вихідні дані
      У вихідний файл виведіть єдине число — найбільшу кількість спортсменів, побажання яких може задовольнити деяке розселення.

      Приклади

village.in	village.out
`4 2 1 4 1`	`3`
`8 2 3 4 5 6 7 8 1`	`4`
`6 3 3 5 3 3 3`	`2`

      Пояснення до прикладів
      У першому прикладі можна задовольнити побажання трьох членів команди, якщо першого спортсмена поселити з другим, а третього — з четвертим. За будь-якого іншого розміщення або другий, або четвертий спортсмен не будуть мешкати разом із першим, тому задовольнити побажання водночас усіх чотирьох членів команди неможливо.
      У другому прикладі можна задовольнити побажання чотирьох спортсменів, приміром, із непарними номерами: першого поселити з другим, третього з четвертим, п’ятого з шостим, а сьомого — з восьмим. Задовольнити ж відразу п’ятьох членів команди не вийде: жодні два спортсмени не хочуть мешкати разом, тому в кожній з чотирьох кімнат житиме щонайбільше один задоволений спортсмен.
      У третьому прикладі задоволеними можуть виявитися щонайбільше двоє спортсменів: третій та лише один серед решти членів команди, хто хоче з ним жити. Щоб задовольнити двох спортсменів, третього потрібно, очевидно, поселити з п’ятим.

4. Перегони

Максимальна оцінка: 200 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: race.in
Вихідний файл: race.out
Програма: race.*

Велосипедист готується до гірських велоперегонів з роздільним стартом (тобто на час). Він оцінив свою очікувану швидкість використання енергії (тобто потужність) у залежності від часу після початку гонки й хоче розробити відповідний графік харчування протягом перегонів. Єдиним джерелом енергії велосипедиста будуть вуглеводи у поживних батончиках. Всі батончики однакові та містять два типи вуглеводів: швидко засвоювані (моно- та дисахариди) й повільно засвоювані (полісахариди). Ефект від споживання одного батончика можна наблизити такою моделлю:

перші t₁ секунд після споживання батончик дозволяє велосипедисту розвинути потужність a міліват («швидкі» вуглеводи);
наступні t₂ секунд — потужність b міліват («повільні» вуглеводи). Після цього ефект від споживання батончика повністю зникає.

Для спрощення вважатимемо:

модель травлення і використання вуглеводів лінійна, тобто потужності від споживання різних батончиків у будь-який момент часу додаються;
надлишки енергії не накопичуються;
велосипедист може споживати батончики миттєво будь-коли під час або до початку перегонів.

      Завдання
      Знайти найменшу кількість батончиків, необхідних для того, щоб задовольнити енергетичні потреби велосипедиста на весь час перегонів.

      Вхідні дані
      Перший рядок вхідного файлу містить п’ять цілих чисел n, t₁, t₂, a, b — очікуваний час перегонів у секундах та параметри батончика, 1 ≤ n, t₁, t₂ ≤ 10⁵, 1 ≤ a, b ≤ 10⁹.
      Другий рядок містить n цілих чисел p₀, p₁, ..., p_{n – 1} — величини бажаної потужності велосипедиста для кожної секунди після початку перегонів, 0 ≤ p_j ≤ 10⁹.

      Вихідні дані
      Єдиний рядок вихідного файлу має містити одне число — мінімальну необхідну кількість батончиків.

      Приклади

race.in	race.out
`7 2 3 5 2 3 4 5 5 5 4 5`	`4`
`5 10 10 1 10 10 10 10 10 10`	`1`

5. Вибирання каменів

Максимальна оцінка: 200 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 64 MБ
Вхідний файл: stones.in
Вихідний файл: stones.out
Програма: stones.*

      Середньовічні європейці вперше отримали опис Китаю від Марко Поло, який відвідав країну за правління першого імператора монгольської династії Юань — Хубіла́я. Подорожуючи Китаєм, одного дня Марко побачив двох китайців, які сиділи на узбіччі дороги під вербою і перекладали камінці, не помічаючи нічого навколо. Марко попросив їх пояснити, що вони роблять. Йому розповіли правила старовинної гри «цзяньшицзи» (вибирання каменів), у яку вони саме грали.
      На початку гри є 2 купи камінців. Два гравці по черзі забирають камінці з цих куп: або лише з однієї групи довільну додатну кількість, або з обох куп однакову додатну кількість. Переможцем вважають того, хто зробить останній хід.
      Марко помітив, що один з гравців крутив у руках табличку з таким чудернацьким зображенням.

Цей гравець після ходу суперника кидав погляд на табличку і одразу робив хід у відповідь. І майже постійно вигравав.

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

      Вхідні дані
      Єдиний рядок вхідного файлу містить 2 невід’ємних цілих числа — кількості камінців у обох купках. Ці кількості не перевищують 10⁷ + 7.

      Вихідні дані
      Єдиний рядок вихідного файлу має містити 3 невід’ємних цілих числа. Перше / друге / третє число — найбільша кількість камінців, яку потрібно забрати відповідно з першої / другої / кожної купки, щоб здійснити виграшний хід. Якщо якогось виграшного ходу немає, то відповідне число дорівнює нулю.

      Примітка. Виграшний хід — це хід, що призводить до поразки суперника в кінці гри незалежно від дій суперника після даного ходу за умови, що даний гравець і надалі буде дотримуватися виграшної стратегії, тобто робити виграшні ходи.

      Приклади

stones.in	stones.out
`3 4`	`0 0 2`
`5 3`	`0 0 0`
`3 6`	`0 1 0`

      Примітка. 36 % балів буде присуджено за успішне проходження тестів, у яких числа у вхідному файлі менші за 19.

6. Перехрестя

Максимальна оцінка: 200 балів
Обмеження на час: 2 сек.
Обмеження на пам’ять: 64 MБ
Вхідний файл: crossing.in
Вихідний файл: crossing.out
Програма: crossing.*

      Перший китайський імператор монгольської династії Юань — Хубіла́й (онук Чингісхана), якого монголи прозивали кага́н Сеце́н — проводив завойовницькі війни. Тому постійно потребував грошей, які намагався отримати від купців, стягуючи мито. Хитрі купці часто обминали перехрестя з митарями. А завойовників-монголів було замало, щоб перекрити всі перехрестя. Тому митарів намагалися ставити так, щоб їх неможливо було оминути.

      Завдання
      З’ясуйте, які перехрестя повністю розбивають систему шляхів на не зв’язані між собою складові.

      Вхідні дані
      Всі пункти системи доріг — перехрестя й закінчення доріг — занумеровано послідовними натуральними числами у межах від 1 до деякого натурального числа n включно, n ≤ 1234567. Кожний рядок вхідного файлу містить пару натуральних чисел — номерів пунктів, які сполучено дорогою без пунктів між кінцями. Таким чином перераховано всі такі дороги по одному разу. Цими дорогами з будь-якого пункту можна потрапити у будь-який інший пункт. Кількість доріг не перевищує 1234567.

      Вихідні дані
      Єдиний рядок вихідного файлу має містити у порядку зростання номери усіх пунктів, вилучення кожного з яких (лише одного) разом з дорогами, що з нього виходять (входять у нього), призводить до розбиття системи шляхів на не зв’язані між собою складові (щонайменше на дві). Інакше кажучи, після такого вилучення перестає справджуватися передостаннє речення опису вхідних даних. Купець не зможе оминути митаря на такому перехресті, якщо рухатиметься з однієї складової системи доріг до іншої. Вхідні дані гарантують існування щонайменше одного такого перехрестя.

      Приклад

crossing.in	crossing.out	ілюстрація
`1 2 1 4 1 5 2 5 2 3 3 6 3 7 4 5 6 7`	`2 3`