Технокубок 2025-2026 1 Отбор Задача С DRAGON ASIAN FEST алгоритм реализация 2026-06-17

Повторяем ручное битовое построение и делаем реализацию и сдаём задачу https://cups.online/ru/tasks/3142 Ссылка на предыдущую часть https://www.youtube.com/watch?v=ZR0cdJsBpUU Задача C. VK Asian Dragon Fest Технокубок, первый отборочный этап, 2025/2026 Сцена — зеркальная площадка длиной L метров (L = 2^K). N драконов. Каждый дракон: старт x_i направление d_i = -1 (влево) или +1 (вправо) скорость: время за 1 метр = 2^{a_i} секунд целевая позиция t_i Движение с отражениями от стен (0 и L). Найти минимальное положительное целое T, чтобы в момент T все драконы оказались ровно в своих t_i. Если такого T нет, вывести -1. Гарантируется, что ответ (если есть) — целый. Формат ввода Первая строка: N и K (L = 2^K) Далее N строк: x_i d_i a_i t_i Формат вывода Одно целое число: T или -1. Примеры Пример 1 Ввод: 3 3 0 1 1 2 6 -1 2 5 5 1 0 7 Вывод: 4 Пример 2 Ввод: 3 3 0 1 1 5 6 -1 2 2 5 1 0 5 Вывод: -1 Пример 3 Ввод: 2 4 2 1 3 3 14 -1 4 3 Вывод: -1 0:00 – Введение: разбор примера с четырьмя драконами (L=16, параметры) 3:41 – Ручная проверка движения на окружности и отражениях 13:00 – Вывод формулы движения: (t_i - x_i) * d_i * 2^{a_i} ≡ T (mod C) 29:00 – Формула битового построения: 2^{B-1} * δ = (t_i - x_i) * d_i * 2^{a_i} - T_prev (mod 2^B) 35:25 – Первый шаг итераций: определение младшего бита (δ) для всех драконов 48:13 – Обнаружение ситуаций без решения (делимость левой части на 2^{B-1}) 1:11:55 – Начало реализации на C++: структуры данных, чтение входных данных 1:19:50 – Основной битовый цикл: перебор драконов, вычисление бита, обновление масок 1:35:30 – Обновление ответа T: T += δ * 2^{B-1} 1:47:51 – Ключевой момент: проверка делимости числителя – основа алгоритма