Задачи для олимпиадного программирования

Задача 1. Арифметическая магия

Дэвид Блейн попросил зрителя задумать два числа. Затем он попросил перемножить два числа, большие каждого из задуманных на единицу, вычесть из результата сначала одно задуманное число, затем другое, а затем – их произведение, а полученный результат возвести в N-ю степень.

После чего Дэвид внимательно вгляделся в лицо зрителя и правильно назвал получившийся результат. Ваша задача — повторить фокус Дэвида. По заданному N угадайте получившееся у зрителя число.

Входные данные

Входные данные содержат одно целое число N (0 ≤ N ≤ 1000).

Вывод

Выведите одно число – получившийся у зрителя результат.

Пример

Задача 2. Большие перемены

В Тридевятом царстве N городов. Король хочет соединить города N – 1 двусторонними авиалиниями так, чтобы:

• Каждая авиалиния соединяла два различных города.

• Из каждого города можно было добраться до любого другого напрямую или с пересадками.

Назовём доступностью города количество городов, с которыми он напрямую соединён авиалиниями. Король также требует, чтобы максимальное значение доступности среди всех городов королевства было как можно большим.

Сколько существует различных способов соединить города требуемым образом?

Входные данные

Входные данные содержат одно целое число N – количество городов (2 ≤ N ≤ 10⁹).

Вывод

Выведите одно целое число – ответ на задачу.

Пример

Поясним пример к задаче. Максимальное возможное значение доступности для трёх городов равно 2. Возможны три различных варианта соединения, при котором оно достигается: (1,2)(2,3), (1,3)(2,3), (1,2)(1,3).

Задача 3. Совпадения

Участников ICPC (Intergalactic Collegiate Programming Contest) поселили в только что построенную гостиницу. Всего в гостинице N одноместных комнат, занумерованных целыми числами от 1 до N без пропусков. Для каждого участника известен номер его паспорта – целое число от 1 до 10⁹ включительно. Номера паспортов у участников с разных планет могут совпадать.

Ожидая заселения, несколько участников заметили, что возможна забавная ситуация: номер паспорта может совпасть с номером комнаты. После чего участники задались вопросом – а какое наибольшее число таких совпадений было бы возможно, если специально расселять участников так, чтобы максимизировать это значение?

По заданному количеству комнат в гостинице и списку номеров паспортов участников найдите ответ на этот вопрос.

Входные данные

Первая строка входных данных содержит одно целое число N (1 ≤ N ≤ 10⁵). i-я из последующих N строк содержит целое число a_i – номера паспорта i-го участника (1 ≤ a_i ≤ 10⁹).

Вывод

Выведите одно целое число – наибольшее количество совпадений номеров паспортов с номерами комнат, которое возможно получить при расселении участников по комнатам.

Примеры

Задача 4. Драфт НБА

Перед каждым сезоном НБА проходит драфт, то есть церемония выбора игроков командами.

Перед драфтом скаутские службы команд детально изучают потенциальных новичков. Одна из команд поручила вам написать программу для обработки собранных данных в соответствии с внутрикомандными стандартами.

Каждый из новичков до этого провёл как минимум один сезон в студенческих лигах, так что для каждого игрока известны пять основных целочисленных параметров:

• Рост игрока – ожидаемый диапазон от 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). Каждое число задаётся в отдельной строке.

Вывод

Для каждого игрока в порядке их следования во входном файле выведите одно число – категорию на драфте, в которую этот игрок попадает в соответствии с критериями вашей команды.

Пример

Примечание У первого игрока из примера к задаче рост выше ожидаемого диапазона, кроме того, выше ожидаемого ещё два параметра. Так что этот игрок является «единорогом». Второму игроку для выбора в первом раунде не хватает количества передач – оно у него ниже ожидаемого диапазона, а все остальные навыки в верхней половине этого диапазона. Так что команда будет выбирать этого игрока во втором раунде. У третьего игрока три параметра выше ожидаемого диапазона, но так как среди них нет ни роста, ни размаха рук, «единорогом» этот игрок не является и будет выбран в первом раунде.