Задача A: обезвреживание бомбы

Интернет-олимпиада, Сезон 2020-2021, Первая личная олимпиада Университет ИТМО, 31 января 2021 года Задача A. Обезвреживание бомбы Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт В городе Найт-Сити творится много странных событий. Прямо сейчас Вы рискуете жизнью, чтобы обезвредить бомбу в самом центре города Уотсон. Быстро изучив бомбу, Вы заметили, что на ней есть ровно n кнопок, на каждой из которых написано натуральное число. Числа кнопка может быть в активном и неактивном состоянии, переключение состояния происходит по нажатию, которое занимает ровно одну секунду. Изначально все кнопки находятся в активном состоянии. От доверенного информатора Вы знаете, что бомба взорвется если и только если на момент конца обратного отсчета на ней найдутся две кнопки в активном состоянии с суммой чисел на них ровно k. Разумеется, ее интересует, за какое минимальное время бомбу можно обезвредить. Свой мозговой имплант для быстрых вычислений Вы повредили на прошлом задании, и теперь ему нужна ваша помощь, чтобы узнать какое минимальное количество нажатий кнопок придется совершить, чтобы бомба не взорвалась. Формат входных данных В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10⁹). В следующей строке даны n чисел, которые написаны на кнопках (1 ≤ aᵢ ≤ 10⁹). Формат выходных данных Выведите единственное число — минимальное количество нажатий на кнопки, необходимое для обезвреживания бомбы.

На изображении показан скриншот условия задачи с интернет-олимпиады ИТМО: герою нужно обезвредить бомбу в Найт-Сити, переключая кнопки с числами. Шутка строится на абсурдно драматичном оформлении обычной алгоритмической задачи и отсылке к взрывчатке, хотя решение сводится к поиску минимального числа нажатий. EN: The image shows a screenshot of an ITMO online olympiad problem statement: the protagonist must defuse a bomb in Night City by toggling numbered buttons. The joke comes from the absurdly dramatic framing of an ordinary algorithmic problem and its explosive premise, even though the solution boils down to finding the minimum number of button presses.

• @ithueti / 3639 2021-02-01