1 4
1 5
2 5
2 3
3 6
3 7
4 5
6 7
1. Голосування
Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 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 делегатів є декілька, виведіть будь-який із них.
Приклади
| 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 за першу заявку.
У третьому прикладі кожен із трьох делегатів, присутніх на голосуванні, може бути послідовним.
2. Перегони
Максимальна оцінка: 100 балів
Обмеження на час: 0,2 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: race.in
Вихідний файл: race.out
Програма: race.*
Велосипедист готується до гірських велоперегонів з роздільним стартом (тобто на час). Він оцінив свою очікувану швидкість використання енергії (тобто потужність) у залежності від часу після початку гонки й хоче розробити відповідний графік харчування протягом перегонів. Єдиним джерелом енергії велосипедиста будуть вуглеводи у поживних батончиках. Всі батончики однакові та містять два типи вуглеводів: швидко засвоювані (моно- та дисахариди) й повільно засвоювані (полісахариди). Ефект від споживання одного батончика можна наблизити такою моделлю:
перші t1 секунд після споживання батончик дозволяє велосипедисту розвинути потужність a міліват («швидкі» вуглеводи);
наступні t2 секунд — потужність b міліват («повільні» вуглеводи). Після цього ефект від споживання батончика повністю зникає.
Для спрощення вважатимемо:
модель травлення і використання вуглеводів лінійна, тобто потужності від споживання різних батончиків у будь-який момент часу додаються;
надлишки енергії не накопичуються;
велосипедист може споживати батончики миттєво будь-коли під час або до початку перегонів.
Завдання
Знайти найменшу кількість батончиків, необхідних для того, щоб задовольнити енергетичні потреби велосипедиста на весь час перегонів.
Вхідні дані
Перший рядок вхідного файлу містить п’ять цілих чисел n, t1, t2, a, b — очікуваний час перегонів у секундах та параметри батончика, 1 ≤ n, t1, t2 ≤ 105, 1 ≤ a, b ≤ 109.
Другий рядок містить n цілих чисел p0, p1, ..., pn – 1 — величини бажаної потужності велосипедиста для кожної секунди після початку перегонів, 0 ≤ pj ≤ 109.
Вихідні дані
Єдиний рядок вихідного файлу має містити одне число — мінімальну необхідну кількість батончиків.
Приклади
| 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 |
3. Перехрестя
Максимальна оцінка: 100 балів
Обмеження на час: 1,5 сек.
Обмеження на пам’ять: 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 | |