Розбір завдань другого кваліфікаційного раунду RCC 2016



29 травня відбувся другий кваліфікаційний раунд чемпіонату Russian Code Cup 2016, який вперше проводиться англійською мовою. На цей раз учасникам знову потрібно було протягом двох годин розв'язати п'ять задач. У другому кваліфікаційному раунді билися 3891 людина, і 200 кращих отримали право брати участь у відбірковому раунді, який відбудеться 19 червня. А сьогодні ми пропонуємо вам ознайомитися з рішеннями запропонованих завдань.

  1. Петя і підручник
  2. Григорій і банк
  3. Генератори імен
  4. Футболки
  5. Тестування мостів
Завдання A. Петя і підручник
Умова

Обмеження по часу 2 секунди
Обмеження по пам'яті 256 мегабайт

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

У підручнику n сторінок, пронумерованих від 1 до n, які скріплені палітуркою так, що i n i + 1 сторінки пов'язані один з одним — якщо вирвати одну з них, друга теж випадає з підручника. Петі дуже подобається процес виривання сторінок підручника, однак він все-таки хоче його контролювати, а саме в деякі моменти часу йому цікаво знати, який номер у p-ї по порядку сторінки з решти. Допоможіть йому з цим завданням.

Формат вхідних даних

Вхідні дані містять декілька тестових наборів. У першому рядку задано кількість тестів t (1 ≤ t ≤ 1000).

Кожен з наступних t тестів описується наступним чином: у першому рядку опису тесту містить два числа n, q (2 ≤ n ≤ 100, n — парне; 1 ≤ q ≤ 100) — кількість сторінок у підручнику і кількість запитів відповідно. У наступних q рядків містяться запити двох типів:

  • — i — Петя вириває сторінку з номером i;
  • ? p — Петя хоче дізнатися, який номер у p-ї по порядку з решти сторінок.
Гарантується, що в запиті першого типу ту сторінку існує, а в запиті другого типу поточне кількість сторінок не менше p.

Формат вихідних даних

На кожен запит другого типу в окремому рядку виведіть номер шуканої сторінки.

Приклади

Вхідні дані
2
4 4
? 3
— 2
? 2
? 1
6 5
— 3
? 3
— 1
? 2
? 1

Вихідні дані
3
4
1
5
5
2

Рішення

У цій задачі треба було просто написати те, що просять. Досить зберігати масив isDeleted розмір n, isDeleted[i] означає, вирвана вже сторінка з номером i. Для обробки першого запиту достатньо присвоїти isDeleted[i] isDeleted[n i + 1] значення false, а для обробки другого запиту — знайти індекс p-го true у масиві isDeleted.

Асимптотика рішення: O(t • q • n).

Завдання Ст. Григорій і банк
Умова

Обмеження по часу 2 секунди
Обмеження по пам'яті 256 мегабайт

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

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

Григорій повинен обробити n запитів на одержання грошей від покупців і m запитів на відправку грошей продавцям. Григорій знає розклад роботи банку, а також може домовитися з кожним покупцем і продавцем про те, коли будуть перераховані гроші.

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

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

Формат вхідних даних

Вхідні дані містять декілька тестових наборів. У першому рядку задано кількість тестів t (1 ≤ t ≤ 1000).

Кожен з тестів описується наступним чином: у першому рядку опису тесту містяться числа n m (1 ≤ n, m ≤ 100) — кількість покупців і продавців відповідно. У другому рядку міститься n чисел aі (1 ≤ aі ≤ 1000) — сума, яку повинен перерахувати i-й покупець. У третьому рядку міститься m чисел bj (1 ≤ bj ≤ 1000) — сума, яку потрібно перерахувати j-му продавцю. В останньому рядку опису тесту міститься рядок s (довжина s дорівнює n + m, s містить n символів + m символів). s[k] одно +, якщо в k-й день банк дозволяє тільки приймати перекази грошей, а якщо банк працює тільки на відправку переказів, то s[k] одно -.

Формат вихідних даних

Для кожного тесту у окремому рядку виведіть відповідь на нього — мінімальну можливу кількість продавців, з якими Григорій не зможе розплатитися.

Приклади

Вхідні дані
3
2 1
1 5
4
+-+
1 3
1
2 2 2
-+--
2 2
2 2
3 3
+-+-

Вихідні дані
0
3
1

Рішення

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

Нехай у нас є пара покупців aі aj, i < j aі < aj. i j — позиції в обраній випадкової розстановці. Якщо поміняти їх місцями, очевидно, що відповідь не погіршиться, так як кількість грошей на рахунку Григорія збільшиться на відрізку i j. Тому вигідно, щоб покупці переводили гроші в порядку убування aі.

Аналогічно можна довести, що якщо є два продавці, з якими можна розрахуватися, то вигідніше їх ставити в порядку зростання bj.

Єдиний тонкий момент — це наявність продавців, з якими не виходить розплатитися. Очевидно, що якщо Григорій не може розплатитися з x продавців, то вигідніше, щоб вони були найбільш дорогими.

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

Завдання С. Генератори імен
Умова

Обмеження по часу 2 секунди
Обмеження по пам'яті 256 мегабайт

Видатний письменник усіх часів Хенк Морбукс вже придумав, про що він буде писати наступний бестселер, але ще не визначився з іменами k своїх персонажів. Як і для попередніх книжок, імена він буде отримувати поділом спеціально придуманої рядка k різних і пустих частин. Допоможіть Хенку зрозуміти, чи можна розбити задану рядок k різних імен.

Формат вхідних даних

Перший рядок файлу містить кількість тестів t (1 ≤ t ≤ 1000).

Кожен тест описується двома рядками. У першій рядку опису тесту міститься рядок довжини не більше 100, що складається з літер англійського алфавіту. У другому рядку міститься одне додатне число k (1 ≤ k ≤ 5) — на яке число різних рядків потрібно розділити задану.

Формат вихідних даних

Результат кожного тесту повинен бути виведений в описаному нижче форматі.

Якщо розбити вихідну рядок можна описаним способом, то вихідний файл повинен містити k + 1 рядків. Перший рядок має містити YES. (i + 1)-й рядок має містити i-е ім'я. Вихідна рядок повинна виходити конкатенацией рядків у порядку виводу.

Якщо розбити вихідну рядок описаним способом можна, то вихідний файл повинен містити одну рядок NO.

Приклади

Вхідні дані
3
aaa
2
aaa
3
abc
3

Вихідні дані
YES
a
aa
NO
YES
a
b
c

Рішення

Насамперед відзначимо, що для будь-якого k всі рядки довжиною більше або дорівнює k(k + 1)/2 можна розбити на k різних. Для цього ми візьмемо підрядка довжиною 1, 2, ..., k – 1 і n k(k – 1)/2. Так як k ≤ 5, то ми навчилися розбивати всі рядки довжиною не менше 15. А для рядків довжини менше 15 ми запускаємо перебір по всьому k – 1 позиціях, в яких її розбиваємо, і перевіряємо, чи правда, що в отриманому розбитті всі рядки різні.

Завдання D. Футболки
Умова

Обмеження по часу 2 секунди
Обмеження по пам'яті 256 мегабайт

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

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

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

Хлопці завжди викреслюють оптимально, тобто кожен намагається зробити так, щоб у підсумку залишилася футболка, яка йому подобається найбільше. Тому хлопці вирішили попросити вас, щоб ви написали програму, яка буде знаходити номер футболки, який залишиться в підсумку.

Формат вхідних даних

Вхідні дані містять декілька тестових прикладів. Перший рядок містить одне число t (1 ≤ t ≤ 50) — кількість тестів. Далі йдуть описи тестів.

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

У наступному рядку знаходиться перестановка від 1 до n — переваги футболок Іллі.

У наступному рядку знаходиться перестановка від 1 до n — переваги футболок Вані.

У наступному рядку знаходиться перестановка від 1 до n — переваги футболок Влада.

Хлопці ходять в наступному порядку: Ілля, Ваня, Влад.

Формат вихідних даних

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

Приклади

Вхідні дані
3
4
1 3 2 4
4 1 2 3
1 2 3 4
5
1 3 2 4 5
5 3 2 1 4
1 3 2 4 5
3
1 2 3
1 2 3
1 2 3

Вихідні дані
1
3
1

Рішення

Для вирішення цього завдання використовуємо динамічне програмування підмножини. Позначимо dp[i][mask] оптимальний номер футболки, якого може досягти i-й учасник, якщо він робить хід і йому доступні футболки, відповідні встановленим біт в числі mask. Для перерахунку переберемо, яку футболку він викреслить, і з'ясуємо, яку він отримає футболку, використовуючи значення dp[(i + 1)%3][mask1], де mask1 виходить з mask обнуленням відповідного біта.

Завдання Е. Тестування мостів
Умова

Обмеження по часу 4 секунди
Обмеження по пам'яті 256 мегабайт

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

Перед відкриттям цих мостів для всіх необхідно перевірити їх надійність. Для цього протягом q днів двоє робітників проїдуть з фіксованою швидкістю 1 по деякому шляху з одного острова на інший. Кожен з них проїде по своєму шляху, можливо починаючи в різні моменти часу. Міст вважається протестованим i-й день, якщо в той день обидва робочих їхали по ньому одночасно протягом деякого ненульового проміжку часу. Для кожного з q днів тестування визначте, чи був в той день протестований хоча б один міст.

Формат вхідних даних

Перший рядок містить два числа n q (1 ≤ n, q ≤ 105, n ≥ 2) — число островів і днів тестування відповідно. Наступні n – 1 рядків описують мости в форматі uі vі lі (1 ≤ uі, vіn, 1 ≤ lі ≤ 109) — кінці мосту і його довжина. Кожна з наступних q рядків містить описи двох шляхів робітників. Кожен шлях задається трьома числами bі, eі, sі (1 ≤ bі, eіn, 1 ≤ sі ≤ 109, bіeі) — початкова і кінцева вершина шляху, а також час, в яке робітник почне рух.

Формат вихідних даних

Виведіть q рядків з відповідями на запити. В i-му рядку виведіть YES, якщо в i-й день був протестований хоча б один міст, і NO інакше.

Приклади

Вхідні дані
8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3

Вихідні дані
YES
YES
NO
NO
NO
YES

Рішення

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

Як знайти перетин двох шляхів? Для цього спроектуємо» кожен з кінців другого шляху на перший шлях. Проекцією вершини u на шлях st назвемо вершину, що лежить на шляху st, яка є найближчою до u по відстані в дереві. Цією вершиною може бути одна з наступних вершин:

  • s або t;
  • LCA(s, t);
  • LCA(s, u), якщо вона лежить на шляху st;
  • LCA(t, u), якщо вона лежить на шляху st.
Шлях між проекціями кожної з вершин другого шляху на перший і буде шуканим перетином, позначимо його через s't'.

Після цього слід розглянути два випадки:

  • Шляхи йдуть цим перетину в різних напрямках. В цьому випадку можна знайти момент часу, коли обидва робочих опиняться в одній точці (не варто забувати, що він може бути напівцілим). Після цього залишилося перевірити, що цей момент часу відповідає ребру, а не вершині.
  • Шляхи йдуть в одному напрямку. У такому разі можна показати, що якщо обидва робітників у якийсь момент часу перебували на одному ребрі, то це вірно і для ребра з максимальною довжиною на шляху s't'. Якщо максимальна довжина ребра на s't' дорівнює M, відповідь YES тоді і тільки тоді, коли |t1 t2| < M, де t1 t2 — час початку руху.
У рішенні, описаному вище, використовувалися пошук LCA, пошук максимального ребра на шляху і відстані між двома вершинами. Все це можна реалізувати, наприклад, за допомогою техніки двійкових підйомів за O((n + q)logn) часу і O(nlogn) пам'яті.

***
Чемпіонат Russian Code Cup входить в число ініціатив Mail.Ru Group, спрямованих на розвиток російської IT-галузі і об'єднаних ресурсом IT.Mail.Ru. Платформа IT.Mail.Ru створена для тих, хто захоплюється IT і прагне професійно розвиватися в цій сфері. Проект об'єднує чемпіонати Ai Cup Russian, Russian Code Cup Russian Developers Cup, освітні проекти Технопарк в МДТУ їм. Баумана, Техносфера в МДУ їм. М. в. Ломоносова і Технотрек в МФТІ. Крім того, на IT.Mail.Ru можна з допомогою тестів перевірити свої знання з популярних мов програмування, дізнатися важливі новини зі світу IT, відвідати або подивитися трансляції з профільних заходів та лекції на IT-тематику.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.