Предлагаем попробовать свои силы в задачах, которые решали школьники и студенты в рамках квалификационного тура чемпионата Moscow Programming Contest 2019 – самого большого конкурса по программированию, который на данный момент проходил в России, организатором которого выступил МФТИ. В нем приняло участие 2284 человека. По итогам представленных задач были отобраны 100 команд, которые участвовали уже в финале чемпионата.
***
Задача 1. Арифметическая магия
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Дэвид Блейн попросил зрителя задумать два числа. Затем он попросил перемножить два числа, большие каждого из задуманных на единицу, вычесть из результата сначала одно задуманное число, затем другое, а затем – их произведение, а полученный результат возвести в N-ю степень.
После чего Дэвид внимательно вгляделся в лицо зрителя и правильно назвал получившийся результат. Ваша задача — повторить фокус Дэвида. По заданному N угадайте получившееся у зрителя число.
Входные данные
Входные данные содержат одно целое число N (0 ≤ N ≤ 1000).
Вывод
Выведите одно число – получившийся у зрителя результат.
Пример
| стандартный ввод | стандартный вывод |
| 3 | 1 |
Обозначим числа за X и Y. Тогда значение равно (X+1)(Y+1) − XY − X − Y = 1. 1 в любой целой неотрицательной степени равно 1. Так что для решения этой задачи надо просто вывести 1.
Задача 2. Большие перемены
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
В Тридевятом царстве N городов. Король хочет соединить города N – 1 двусторонними авиалиниями так, чтобы:
- Каждая авиалиния соединяла два различных города.
- Из каждого города можно было добраться до любого другого напрямую или с пересадками.
Назовём доступностью города количество городов, с которыми он напрямую соединён авиалиниями. Король также требует, чтобы максимальное значение доступности среди всех городов королевства было как можно большим.
Сколько существует различных способов соединить города требуемым образом?
Входные данные
Входные данные содержат одно целое число N – количество городов (2 ≤ N ≤ 109).
Вывод
Выведите одно целое число – ответ на задачу.
Пример
| стандартный ввод | стандартный вывод |
| 3 | 3 |
Поясним пример к задаче. Максимальное возможное значение доступности для трёх городов равно 2. Возможны три различных варианта соединения, при котором оно достигается: (1,2)(2,3), (1,3)(2,3), (1,2)(1,3).
Максимальное значение доступности равно N − 1 и достигается, если соединить какой-то город (назовём его столицей) со всеми остальными. Действительно, все требования выполняются (перелететь между любыми двумя городами можно с пересадкой в столице). Доступность не может превышать N − 1, так как для каждого города существует N − 1 город, не совпадающий с ним. Поэтому количество способов при N > 2 равно количеству вариантов выбрать столицу, то есть N. При N = 2 существует единственный способ соединения городов, который и будет максимальным, так что при N = 2 ответ равен 1.
Задача 3. Совпадения
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Участников ICPC (Intergalactic Collegiate Programming Contest) поселили в только что построенную гостиницу. Всего в гостинице N одноместных комнат, занумерованных целыми числами от 1 до N без пропусков. Для каждого участника известен номер его паспорта – целое число от 1 до 109 включительно. Номера паспортов у участников с разных планет могут совпадать.
Ожидая заселения, несколько участников заметили, что возможна забавная ситуация: номер паспорта может совпасть с номером комнаты. После чего участники задались вопросом – а какое наибольшее число таких совпадений было бы возможно, если специально расселять участников так, чтобы максимизировать это значение?
По заданному количеству комнат в гостинице и списку номеров паспортов участников найдите ответ на этот вопрос.
Входные данные
Первая строка входных данных содержит одно целое число N (1 ≤ N ≤ 105). i-я из последующих N строк содержит целое число ai – номера паспорта i-го участника (1 ≤ ai ≤ 109).
Вывод
Выведите одно целое число – наибольшее количество совпадений номеров паспортов с номерами комнат, которое возможно получить при расселении участников по комнатам.
Примеры
| стандартный ввод | стандартный вывод |
| 5 1 3 5 7 5 |
3 |
| 4 1000000000 1000000000 1000000000 1000000000 |
0 |
Очевидно, что если у участника номер паспорта больше N, то совпадение невозможно. Если несколько участников имеют номер, не превосходящие N, то в соответствующую комнату можно заселить только одного участника, для остальных совпадение уже невозможно (комната занята). Таким образом, ответ – количество различных чисел среди ai, не превосходящих N. Подсчитать их можно, например, заведя булевский вектор из N элементов, помечая там те числа, которые уже были, и в случае изменения значения элемента увеличивая счётчик возможных совпадений на единицу.
Задача 4. Драфт НБА
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Перед каждым сезоном НБА проходит драфт, то есть церемония выбора игроков командами.
Перед драфтом скаутские службы команд детально изучают потенциальных новичков. Одна из команд поручила вам написать программу для обработки собранных данных в соответствии с внутрикомандными стандартами.
Каждый из новичков до этого провёл как минимум один сезон в студенческих лигах, так что для каждого игрока известны пять основных целочисленных параметров:
- Рост игрока – ожидаемый диапазон от 190 до 220 см.
- Размах рук (иначе говоря, wingspan) – ожидаемый диапазон от 200 до 250 см.
- Среднее количество очков за матч – ожидаемый диапазон от 10 до 20.
- Среднее количество подборов за матч – ожидаемый диапазон от 2 до 6.
- Среднее количество передач за матч – ожидаемый диапазон от 3 до 7.
Таким образом, каждый из параметров может оказаться ниже ожидаемого диапазона, в нижней половине ожидаемого диапазона, в верхней половине ожидаемого диапазона (середина входит в верхнюю половину) и выше ожидаемого диапазона.
Перед драфтом требуется распределить игроков по следующим категориям:
- уникальный игрок (таких ещё называют «единорогами» — unicorn) с сочетанием выдающихся физических данных и игровых навыков;
- игрок, достойный выбора в первом раунде;
- игрок, достойный выбора во втором раунде;
- игрок, которого не стоит выбирать вообще.
Если у игрока три параметра выше ожидаемого диапазона, причём среди них обязательно есть рост или размах рук, то игрок считается «единорогом» (категория 0)
Игрока рекомендуется выбирать в первом раунде драфта (категория 1), если верно одно из следующих утверждений:
- У игрока два параметра выше ожидаемого диапазона и ещё один – как минимум в верхней половине ожидаемого диапазона.
- У игрока все параметры как минимум в ожидаемом диапазоне и не менее трёх – как минимум в верхней половине.
Игрока рекомендуется выбирать во втором раунде драфта (категория 2), если верно одно из следующих утверждений:
- У игрока один параметр выше ожидаемого диапазона и ещё один — как минимум в верхней половине ожидаемого диапазона.
- У игрока три параметра как минимум в верхней половине ожидаемого диапазона.
В остальных случаях тратить выбор драфта на этого игрока не рекомендуется (категория 3).
Вам заданы параметры некоторых из 32 игроков текущего драфта (для объективности имена игроков не указаны). Ваша задача – для каждого игрока определить категорию, под которую он подпадает для вашей команды на драфте.
Входные данные
Первая строка входных данных содержит одно целое число N— количество игроков (1 ≤ N ≤ 32). Описание каждого игрока состоит из 5 целых чисел: роста h (150 ≤ h ≤ 250), размаха рук w (150 ≤ w ≤ 270), среднего количества очков s за матч (5 ≤ s ≤ 35), среднего количества подборов r за матч (0 ≤ r ≤ 10), среднего количества передач p за матч (0 ≤ p ≤ 10). Каждое число задаётся в отдельной строке.
Вывод
Для каждого игрока в порядке их следования во входном файле выведите одно число – категорию на драфте, в которую этот игрок попадает в соответствии с критериями вашей команды.
Пример
| стандартный ввод | стандартный вывод |
| 3 230 190 16 7 9 205 225 15 5 2 210 210 30 9 9 |
0 2 1 |
В этой задаче надо просто сделать то, что описано в условии: посчитать для каждого параметра, в какую категорию он попадает, и затем в нужном порядке проверить все варианты.
Задача 5. Думский регламент
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
В Тридевятом Царстве уже много лет как установилась конституционная монархия. В парламент Тридевятого царства входят 26 партий, обозначаемых строчными буквами английского алфавита от «a» до «z». Заседание парламента в соответствии с регламентом проходит по следующей схеме:
- В начале заседания никаких законопроектов на повестке дня не стоит.
- Любая партия (в том числе и та, которая внесла текущий законопроект) в любой момент времени может внести на обсуждение новый законопроект.
- При вносе партией нового законопроекта обсуждение предыдущего приостанавливается и начинается обсуждение нового. После того, как парламентарии голосуют за новый законопроект, обсуждение законопроекта, прерванного им, продолжается.
- Дискуссия по любому законопроекту обязана завершиться голосованием по этому законопроекту.
- В конце заседания не должно остаться внесённых законопроектов, дискуссия по которым не завершена.
Вам дана запись о событиях на сессии парламента. Каждое событие является либо внесением нового законопроекта, либо голосованием за какой-то законопроект, причём в обоих случаях известен номер партии, этот законопроект предложившей. События даны в том порядке, в котором они происходили. Проверьте, может ли данная запись о событиях соответствовать какому-либо заседанию, удовлетворяющему порядку проведения, описанному выше.
Входные данные
Первая строка входных данных содержит одно целое число K – количество строк в записи сессии (1 ≤ K ≤ 1000). Каждая строка соответствует одному из двух событий:
- Add x – партия x внесла на голосование законопроект.
- Vote x – прошло голосование за документ, внесённый партией x.
Здесь x – строчная буква английского алфавита от «a» до «z», задающая партию.
Вывод
Выведите «Yes», если существует корректный порядок проведения заседания, который мог привести к такой записи, и «No», если ни при каком корректном порядке проведения заседания данная запись появиться не могла.
Примеры
| стандартный ввод | стандартный вывод |
| 4 Add a Add b Vote a Vote b |
No |
| 8 Add z Vote z Add x Add y Add x Vote x Vote y Vote x |
Yes |
| 1 Vote z |
No |
Обратим внимание на следующие факты:
- Пустая запись является корректной.
- Если две записи являются корректными, то их слияние тоже является корректным. Действительно, получится заседание, в котором к моменту окончания первой записи быди приняты все внесённые законопроекты, а затем заседание продолжилось внесением очередного законопроекта и также корректно завершилось.
- Если запись является корректной, её можно «вставить» внутрь обсуждения одного законопроекта и получить корректную запись. Это прямо следует из третьего пункта регламента.
Несложно показать, что любую запись можно получить из пустой с помощью действий 2 или 3. Действительно, пусть у нас есть некая корректная запись. Рассмотрим первый законопроект. Он или был поставлен на голосование последним (тогда был применено третье действие – вся оставшаяся запись была вставлена в обсуждение этого законопроекта), или был поставлен на голосование в какой-то момент раньше. Тогда к моменту после голосования по первому законопроекту все внесённые законопроекты уже «закрыты», то есть часть записи от внесения законопроекта на обсуждение до голосования представляет собой корректную запись. Аналогично оставшаяся часть представляет собой корректную запись (так как к моменту её начала никаких законопроектов на повестке дня не стоит, то стартовые условия выполняются, остальные же требования следуют из корректности первоначальной записи), и в этом случае было применено второе действие. В каждом случае получаем переход к записи меньшей длины; будем продолжать действовать таким образом, пока не дойдём до пустой записи.
Тем самым мы показали, что условие задачи эквивалентно правильной скобочной последовательности с 26 типами скобок. Для проверки того, что скобочная последовательность является правильной, лучше всего использовать стек: в начале обсуждения законопроекта мы кладём на стек букву, соответствующую внёсшей его партии, по окончании – сравниваем вершину стека с буквой, соответствующей партии, законопроект которой поставлен на голосование (если не равны – запись некорректна) и снимаем букву со стека. Если в какой-то момент времени была попытка взять вершину пустого стека – запись некорректна. Если по завершении всей записи стек не пуст – какие-то законопроекты не поставлены на голосование и запись некорректна. Во всех остальных случаях запись корректна.
Задача 6. Правильный подмногоугольник
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Задан правильный N-угольник. Требуется выбрать наименьшее количество его вершин, которые также образуют правильный многоугольник.
Входные данные
Входные данные содержат одно целое число N (3 ≤ N ≤ 1012).
Вывод
Выведите одно число — наименьшее количество вершин заданного многоугольника, которые образуют правильный многоугольник.
Пример
| стандартный ввод | стандартный вывод |
| 5 | 5 |
| 21 | 3 |
Если N делится на k > 2, то можно выбрать k вершин так, чтобы они образовывали правильный многоугольник. Таким образом, нужно найти наименьшее k > 2, на которое делится N.
Если N делится на 3, ответ равен 3.
Иначе, если N нечётно, перебором √N до ищем наименьший простой делитель, он и будет ответом. Если не нашли, ответ равен i.
Иначе, если N делится на 2, но не делится на 4, перебором до √N ищем наименьший нечётный простой делитель. Если не нашли, ответ равен N/2.
Иначе N делится на 4 и ответ равен 4.
Задача 7. Есть ли делитель?
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
На форуме, на котором обсуждаются задачи олимпиад по информатике, ввели следующий аналог капчи. Участнику выдаётся строка из N десятичных цифр (без ведущих нулей). В качестве ответа требуется ввести такое основание системы счисления B, что в этой системе счисления выданная запись будет соответствовать составному числу (назовем его D), а также число X, большее 1 и меньшее D, являющееся делителем D.
При этом B и X не должны превосходить 109.
По заданной строке десятичных цифр найдите любую пару чисел B и X, удовлетворяющую ограничениям, или ответьте, что решения в заданных ограничениях не существует.
Входные данные
Входные данные состоят из непустой строки длиной до 3 ⋅ 106 символов, составленной из цифр от 0 до 9 и не начинающейся с 0.
Вывод
Если решение существует, выведите два числа – основание системы счисления B и делитель X, записанные в десятичной системе счисления. Оба числа должны удовлетворять ограничениям 2 ≤ B, X ≤ 109. Если решения не существует, выведите –1.
Примеры
| стандартный ввод | стандартный вывод |
| 1 | -1 |
| 4 | 10 2 |
| 19 | 11 2 |
Если строка состоит из одного символа, то ответ −1 в случае, если число не является составным (1 2 3 5 7), и 10 (к примеру) в случае, если является (то есть 4 6 8 9).
Если строка состоит из более чем одного символа, то работает ответ (B = S + 1, X = S), где S –сумма цифр (так как Xk − 1 = (X − 1) · (Xk−1 + . . . + X + 1), то остаток числа в S + 1-ичной системе от деления на S равен остатку от деления на S суммы его цифр, то есть 0 по построению).
Задача 8. ICPC
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Словарь тау-китянского языка состоит из всех слов, длина которых не превосходит N. Слова записываются строчными буквами английского алфавита. В тау-китянском словаре – в отличие от земных – слова сначала упорядочены по длине, а только затем по алфавиту, то есть сначала идут однобуквенные слова от «a» до «z», затем двухбуквенные – от «aa» до «zz» и так далее.
Алиса выписала подряд все слова тау-китянского языка в том порядке, в котором они перечислены в словаре, и получила длинное слово. Сколько раз в этом слове встретится подстрока «icpc»?
Входные данные
Входные данные содержат одно целое число N (1 ≤ N ≤ 109) – максимальная длина слова в тау-китянском языке.
Вывод
Выведите одно число — остаток от деления количества вхождений подстроки «icpc» на 109 + 7.
Примеры
| стандартный ввод | стандартный вывод |
| 3 | 0 |
| 5 | 134 |
Рассмотрим все K-значные слова. «icpc» может находиться на одной из K − 3 позиций, при этом все остальные буквы могут быть произвольными (при таком подходе мы считаем вхождения на конкретной позиции, что автоматически решает вопрос учёта слов со многими «icpc»). Таким образом, слов с «icpc» будет 26K – 4 · (K − 3). Кроме того, возможны три стыка: cXicp|cXicq, pcXic|pcXid, cpcXi|cpcXj, где X — произвольный набор из K − 4 букв, то есть ещё добавляется 26K – 4 · 3 слова. Итого получается 26K − 4 · K вхождений на блок K-значных чисел.
Просуммировав все такие значения для K от 4 до N по заданному модулю, получим ответ к задаче. Покажем, что сумма сворачивается в формулу. Обозначим за F(N) сумму 1 + 26 + … + 26N; F(N) = (26N+1 − 1)/(26 − 1). Тогда наша сумма равна
Но 26k · F(N − 4 − k) = (26N−4−k+1 · 26k − 26k)/(26 − 1) = (26N−3 − 26k)/(26 − 1). Таким образом, после суммирования получим в числителе (N − 3) · 26N−3 − 1− 26 − 262 … = (N − 3) · 26N−3 − F(N−4).
Задача 9. Составление задач
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 6 секунд |
| Memory limit: | 512 мебибайт |
Для составления задач на очередное соревнование организаторы пригласили P опытных участников этих же соревнований. Каждый из них знает некоторый набор задач. Участники любят делиться идеями задач, поэтому каждая задача может быть известна нескольким участникам. К сожалению, если участник знает хотя бы одну задачу из выбранного на соревнование комплекта, то он не может принять в нём участие.
Организаторы заинтересованы в массовости соревнования, поэтому они хотят выбрать задачи так, чтобы как можно больше участников могли принять в нём участие. При этом набор задач должен быть не пуст, и, по возможности, как можно больше.
Организаторы не являются программистами, поэтому испытывают проблемы с тем, чтобы набрать задачи требуемым образом, поэтому просят вас помочь им.
Входные данные
В первой строке входных данных записаны три целых числа P, T и M (1 ≤ P, T ≤ 105; 0 ≤ M ≤ min(106, P · T)) – количество участников, задач и пар участник-задача, которую он знает, соответственно.
В следующих M строках описаны задачи, которые известны участникам. В каждой строке записаны два целых числа u и v (1 ≤ u ≤ P; 1 ≤ v ≤ T) – номер участника и номер одной из известных ему задач. Гарантируется, что для каждого участника каждая известная ему задача описана ровно один раз.
Вывод
В первой строке выведите два числа P0 и T0 – искомое количество участников и задач. Обратите внимание – в первую очередь требуется максимизировать количество участников, а при максимальном числе участников – количество задач.
Во второй строке выведите T0 чисел – номера задач в набранном комплекте. Все номера должны быть различными натуральными числами, не превосходящими T. Если возможно несколько оптимальных решений, выведите любое.
Примеры
| стандартный ввод | стандартный вывод |
| 3 4 6 1 1 1 2 2 2 2 3 3 3 3 4 |
2 1 1 |
| 3 5 6 1 1 1 2 2 1 2 3 3 1 3 3 |
3 2 4 5 |
Обратите внимание – в этой задаче требуется считать из входного потока много данных. Для этого в программе на языке C++ следует добавить в начало функции main следующие три строчки:
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);В программе на языке Java следует отказаться от использования класса Scanner.
Очевидно, что нас интересуют только задачи, которые знает как можно меньше людей. Две задачи из этого набора могут войти в контест только если их знает одинаковый набор человек. Поэтому мы для каждого набора человек считаем, какие задачи известны именно этому набору и берем максимальное по размеру получившееся множество. Асимптотика времени работы оценивается как O(m · log(n)) .
Задача 10. Порталы
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Вы очнулись в тёмной комнате и сразу поняли, что оказались в лабиринте, из которого надо выбраться! Лабиринт представляет собой прямоугольник из N строк по M клеток в каждой, некоторые из которых заняты стеклянными или сплошными стенами, причем весь лабиринт окружают сплошные стены. Если смотреть на карту лабиринта, то строки пронумерованы от 1 до N сверху вниз, а столбцы пронумерованы от 1 до M слева направо. Вы находитесь в одной из не занятых стеной клеток лабиринта, а в какой-то свободной клетке (возможно, в стартовой) находится выход.
Немного побродив по комнате, вы обнаружили портальную пушку, которая предназначена для установки на стене порталов одного из двух цветов — оранжевого или синего. В каждый момент времени может быть не более одного портала каждого цвета, поэтому, когда устройство выставляет новый портал, старый портал того же цвета исчезает. Изначально порталов нет. Стоя в клетке, вы можете выстрелить портальной пушкой в одном из четырех направлений, при этом выстрел пролетает сквозь стеклянные стены и портал создастся на ближайшей в этом направлении стороне сплошной стены. Если вы попробуете поставить портал на стороне стены, где уже стоит какой-то портал, то ничего не изменится, но будет считаться, что портальная пушка сработала.
Также вы можете передвигаться по лабиринту по любым свободным клеткам, двигаясь в одном из четырёх направлений и входить в находящийся рядом с вами портал – при этом он должен находиться на видимой вами стороне стены в соседней с вами клетке. В таком случае вы мгновенно оказываетесь возле второго портала. Если выход из этого портала ведёт в стеклянную стену, а такое могло случиться, если сплошная и стеклянная стена были рядом, и выстрел портальной пушки пролетел сквозь стеклянную стену и остался на сплошной, то вы погибнете.
Вы опасаетесь, что портальная пушка может выйти из строя, поэтому хотите пройти лабиринт, используя ее как можно меньше раз. Напишите программу, которая рассчитает минимально возможное количество использований устройства, позволяющее вам выйти из лабиринта.
Входные данные
В первой строке входных данных через пробел записаны два целых числа N и M (3 ≤ N, M ≤ 1000) – число строк и столбцов клеток в лабиринте. В каждой из следующих N строк записаны M символов, описывающих лабиринт. Символ «W» описывает сплошную стену, символ «G» — стеклянную, а символ «.» – свободную клетку. Гарантируется, что все граничные клетки заняты сплошной стеной.
В следующих двух строках записаны по два числа rS, cS, rE, cE (2 ≤ rS, rE ≤ N – 1;2 ≤ cS, cE ≤ M – 1) – номера строк и столбцов стартовой клетки, и клетки с выходом соответственно. Гарантируется, что эти клетки являются свободными. Нумерация клеток начинается с единицы с левого верхнего угла.
Вывод
Если добрать до выхода невозможно даже используя портальную пушку, выведите только «-1 -1» (без кавычек). Иначе, в первой строке выведите два числа P и S — количество выстрелов портальной пушки и число пройденных шагов соответственно. Вам требуется минимизировать только число P, количество шагов не должно превосходить 2 · n · m. В следующих P + S строках выведите последовательность ваших действий. Действие описывается двумя символами, типом действия («M», «O» или «B») и его направлением («U», «D», «R» или «L»), выведенными подряд. Типы действий:
- «M» – передвинуться на одну клетку в выбранном направлении. Вы не можете идти в клетку, в которой находится стена, на которой с вашей стороны нет портала.
- «O» – поставить оранжевый портал на ближайшей сплошной стене в выбранном направлении.
- «B» – поставить синий портал на ближайшей сплошной стене в выбранном направлении.
Направление может принимать значения «U», «D», «R» или «L» – вверх, вниз, вправо и влево соответственно.
Примеры
Разобьём таблицу на компоненты связности так, будто у нас нет портальной пушки. Между компонентами связности мы можем перемещаться только с ее помощью. Будем каждую компоненту связности считать отдельной вершиной. Добавим все необходимые рёбра между компонентами. Заметим, что каждая клетка даёт нам не более 4 ребёр – вдоль каждого из возможных направлений. Поэтому ребер в данном графе будет не более 4·n·m. В полученном графе длина пути до финальной вершины есть количество использований портальной пушки. Это позволяет нам запустить на таком графе обход в ширину для поиска кратчайшего расстояния. Затем остаётся только восстановить ответ.
Отдельным случаем стоит выделить ситуацию, когда комната, в которой игрок начинает целиком окружена стеклянными стенами. Тогда игрок никак не может ее покинуть, потому что ему некуда поставить первый портал, и если конечная клетка находится в другой компоненте, то попасть в нее никак не получится.
Задача 11. «Контакт» для двоих
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 2 секунды |
| Memory limit: | 512 мебибайт |
Лось Валера очень любит играть в «Контакт» – широко популярную словесную игру; однако поиграть в нее в последнее время удается нечасто, ведь в игре должны участвовать не менее трех игроков, а собраться вместе как минимум втроем из-за нехватки времени и нестыкующихся графиков крайне затруднительно…
В силу этого, лось Валера придумал новую игру — «Контакт для двоих». Суть ее заключается в следующем. Один из игроков загадывает некоторое непустое слово S, которое второй игрок должен отгадать, и сообщает первую букву этого слова. Второй игрок, пытаясь угадать слово, называет одно за другим слова, начинающиеся на заданную букву, а первый игрок сообщает ему, верное ли слово, причем второй игрок не должен повторяться. Если второй игрок назвал некоторое наперед заданное число K слов и так и не угадал слово, то первый игрок сообщает вторую букву слова; после этого, второй игрок может называть лишь слова, начинающиеся с этих двух букв и не названные им ранее (в том числе и когда он знал лишь одну букву). Если после появления второй буквы, второй игрок сумеет назвать еще K слов, то первый игрок сообщает третью букву, и т.д. Если в какой-то момент оказывается, что первый игрок уже назвал все буквы своего слова, а второй после этого назвал K слов, начинающихся с него, но само слово не назвал, то первый игрок просто сообщает, что уже открытые буквы и образуют загаданное слово, и игра заканчивается.
Чтобы игра была интереснее, лось Валера, играя за первого игрока, старается загадать такое слово, чтобы второй игрок сделал как можно больше попыток угадать его (удачная попытка также считается). Однако сам процесс игры зависит от словарного запаса второго игрока, а также от выбранного числа K. Так как лось Валера хорошо знает своих друзей, то для каждого из них Валера может выписать все слова, которые тот знает. Конечно же, чтобы не расстраивать второго игрока, Валера всегда загадывает слово, которое игрок знает. Однако, не так-то просто выбрать это слово и число K. Поэтому Валера решил написать программу, которая по заданному словарю и Q парам «загаданное слово – значение K» определяет, какое максимальное число слов может назвать второй игрок, пока игра не закончится угадыванием слова вторым игроком или сообщением слова первым.
Лось Валера справился с задачей. Справитесь ли вы?
Входные данные
В первой строке записано единственное целое положительное число N – количество слов в словаре потенциального второго игрока. В каждой из следующих N строк записано одно непустое слово этого словаря, состоящее из строчных букв английского алфавита. Суммарная длина слов не превосходит 2 · 105.
Обратите внимание: слова могут быть одинаковыми по написанию, например, потому что они различаются при произношении ударениями: к примеру, в русском языке слова «замОк» и «зАмок» разные слова, хотя пишутся одинаково. В языке, на котором лось Валера и его друзья любят играть в «Контакт», количество возможных акцентов, делающих одинаково записываемые слова разными по звучанию, очень велико. Во время игры участники полностью различают одинаково записываемые слова, произнося их по-разному.
В (n + 2)-й строке содержится целое число Q, (1 ≤ Q ≤ 2 · 105) – количество исследуемых пар «загаданное слово – значение K». В следующих Q строках записаны по два целых числа w и k (1 ≤ w, k ≤ n) – номер загаданного слова из словаря и предполагаемое значение K. Cлова нумеруются в том порядке, в котором они заданы выше, начиная с единицы.
Вывод
Для каждой из Q пар выведите в отдельное строке единственное целое число– максимальное количество слов, которые может назвать второй игрок.
Примеры
| стандартный ввод | стандартный вывод |
| 6 asassin assistant astronaut abrakadabra abbey automaton 9 1 1 1 2 1 3 4 1 4 2 4 3 6 1 6 2 6 3 |
3 5 6 3 4 5 2 3 4 |
| 3
aa ab ab |
2 2 3 3 3 2 |
| 7
pit pitbul piter pitstop pitlane petroleum pistol 1 2 |
6 7 5 5 7 4 |
Построим бор на словах из словаря. Пусть для каждой вершины бора v sz(v) есть количество слов, заканчивающихся в поддереве вершины v, включая саму вершину v. Все значения sz(v) можно насчитать за O(SUMLEN), где SUMLEN – суммарная длина всех строк.
Пусть задан запрос (s, k), где s – строка словаря длины n, а ее путь в боре состоит из вершин v0, v1, . . . , v|s|. Заметим, что ответ для нее не превосходит k · |s|. Предположим, что мы можем назвать c ≤ k · |s| слов в процессе игры. Тогда очевидно, что sz(v1) ≥ c, sz(v2) ≥ c − k, sz(v3) ≥ c − 2 · k, . . . , sz(v|s|) ≥ c − (|s| − 1) · k (ибо мы обязаны назвать как минимум c − (i − 1) · k в поддереве вершины vi, i = 1,2,…,|s|).
С другой стороны, докажем, что эти условия не только необходимы, но и достаточны. Заметим, что оптимальной с точки зрения максимизации слов стратегией для второго игрока является называть каждый раз слово с как можно меньшим общим префиксом с угадываемым словом, который только возможен с учетом уже названного лосем Валерой слова. Предположим, что второй игрок, используя эту стратегию, назвал некоторое количество слов c + 1 ≤ k · |s|, остановившись на l-ом раунде, 1 ≤ k ≤ |s|.
Пусть 0 ≤ l’ < l – номер последнего раунда, в котором назывались только слова, «ответвляющиеся» от s непосредственно после l‘-го раунда, или 0, если таких раундов не было. Тогда в поддереве вершины vl’+1 были названы все слова, причем исключительно в раундах, начиная с l‘ +1, и их оказалось ровно c + 1− l’ · k; следовательно, sz(vl’+1) = c + 1 − l‘ · k > c − l’ · k. Следовательно, если c слов назвать невозможно, то и вышеописанные условия не выполняются. Таким образом, эквивалентность доказана.
Вышедоказанное утверждение дает возможность отвечать на запрос за O(|s|), находя минимум из чисел sz(vi) − k · (i − 1) на пути строки s, что, конечно, недостаточно эффективно. Однако заметим, что sz(vi) ≥ sz(vi+1) для любого i, причем строгое неравенство выполняется, только если в вершине vi заканчивается некоторое слово и/или происходит ответвление. Таких событий на пути не более 2 · √SUMLEN в противном случае, суммарная длина слов в словаре окажется больше, чем √SUMLEN, что противоречит условию); следовательно, если для каждой вершины предподсчитать заранее следующую вершину с ответвлением (отметим, что она не зависит от самого слова s), то время ответа на запрос сократится до O(√SUMLEN). Таким образом, итоговая сложность решения O(SUMLEN + Q · √SUMLEN).
Задача 12. Ближайшие точки
| Input file: | стандартный ввод |
| Output file: | стандартный вывод |
| Time limit: | 4 секунды |
| Memory limit: | 512 мебибайт |
На прямоугольной декартовой плоскости задан прямоугольник A с вершинами в точках (0; 0) и (X, Y), стороны которого параллельны осям координат, где X, Y – целые положительные числа. Нестрого внутри этого прямоугольника отмечены K точек p1, p2, . . . , pK с целочисленными координатами. Точка p с целочисленными координатами, лежащая в A, называется хорошей, если расстояние от p до p1 окажется не больше, чем расстояние от p до любой из точек pi, 1 ≤ i ≤ K.
Внимание, вопрос: сколько существует хороших точек?
Входные данные
Первая строка входных данных содержит три целых положительных числа X, Y, K, 1 ≤ X, Y, K ≤ 2 · 105 – размеры прямоугольника и количество отмеченных точек. i-я из следующих K строк (i = 1, 2,…,K) содержит по два целых числа xi, yi (0 ≤ xi ≤ X, 0 ≤ yi ≤ Y) – координаты i-й точки. Гарантируется, что все точки попарно различны.
Вывод
Выведите одно целое неотрицательное число – ответ на задачу.
Примеры
| стандартный ввод | стандартный вывод |
| 4 4 5 2 2 1 1 1 3 3 3 3 1 |
5 |
| 6 6 6 0 0 1 0 2 0 3 0 4 0 5 0 |
7 |
Как известно из школьной геометрии, геометрическое множество точек, более близких к точке p, нежели к точке q, есть открытая полуплоскость, граница которой является серединным перпендикуляром отрезка pq. За O(n log n) можно найти пересечение этих полуплоскостей и прямоугольника, после чего с помощью сканирующей прямой легко вычислить для каждого целого x,0 ≤ x ≤ X, диапазонов, таких, что точка (x, y) лежит строго внутри. Такое решение работает за O(n log n + X).
Однако этот алгоритм является не самым приятным и простым в реализации.
На наш взгляд, более приятным является использование дерева Ли-Чао. С его помощью легко для каждого x от 0 до X найти самый высокий y, таких, что (x, y) лежит на границе полуплоскости, «смотрящей вверх», а также самый низкий y на границе полуплоскости, «смотрящей вниз»; это можно сделать за O(n log X). После этого, ответ можно найти тривиальным образом за O(X), а общая асимптотика такого решения – O(n log X + X).
Отметим, что решение с использованием типов данных с плавающей точкой, наподобие double или даже long double в С++ могли приводить к потере точности в ответе. В силу этого, рекомендуется выполнять все вычисления в рациональной арифметике. Ограничения в задаче подобраны таким образом, что при аккуратной реализации, достаточно было хранить числитель и знаменатель в виде 64-битных целых чисел.
