«Не всё спокойно в Найт-Сити»: в задания интернет-олимпиады по информатике включили условия по Cyberpunk 2077
Университет ИТМО, под эгидой которого проходит конкурс, постоянно составляет задачи по известным фильмам и играм — ранее для этого использовались Death Stranding, «Джокер» и «Звёздные войны».
Я правда не школьник, а программист, который пишет всякое энтерпрайзное говно для банков, и мой мозг давно атрофировался - могу читать писать из кафки, а простейшие алгоритмы сразу ставят в тупик. Но наверняка идея такая:
1) Создать две коллекции с оффсетами относительно k/2 справа и слева;
2) Если элементы совпадают, значит нашли пару чисел, которые дают в сумме k - можно увеличить счетчик с результатом;
3) В этих коллекции можно и нужно выкинуть дубликаты.
4) SortedSet - идеальный вариант для коллекции
5) Есть неприятный случай когда есть элементы = k/2. Вроде это как особый случай и надо выкинуть n-1 всех таких элементов
Набросок алгоритма - говнокодище:
Это стандартная задача на кодерских интервью (2-Sum https://leetcode.com/problems/two-sum).
В формулировке как здесь, впрочем:
Изначально все кнопки находятся в активном состоянии
и
...если и только если на момент конца обратного отсчета на ней найдутся две кнопки в активном состоянии...
Если они существуют, то они обязательно найдутся, поскольку все кнопки уже и так в активном состоянии (задача не говорит что _только_ они должны быть в активном).
То есть, ответ либо 0, либо "никогда" - если последнее возможно, то тогда это 2-sum со стандартным решением (хеш таблица в которую записываются элементы, и на каждом шаге проверять есть ли там уже k-x)
Вроде вся идея с сетами накрывается в тот момент, когда у тебя встречаются повторы чисел. Придётся считать их количество. Другими словами: при заданной сумме 4 и числах 1 1 3 3 в твоём варианте выйдет ответ 1 и бомба бабахнет.