Тренировочная сессия 1: разбор случаев на строке и сортировка при развороте гравитации СЕССИЯ

Что тренируем сегодня

Начинаем летний цикл тренировок — двадцать три сессии, которые постепенно поднимут уровень от базовой разминки до боевого контест-формата. Если за лето получилось отдохнуть от алгоритмов и сейчас кажется, что даже простая задача требует усилия — это совершенно нормально, у всех так после паузы. Первая сессия нарочно лёгкая: две задачи уровня CF ~900, без хитрых структур данных, только аккуратная работа с условием и базовыми приёмами — прямым проходом по строке и сортировкой массива.

Сегодня в фокусе два инструмента, которые встречаются в олимпиадных задачах постоянно: разбор случаев (проверка условия на каждом шаге линейного прохода) и симуляция через переформулировку (когда честно моделировать процесс не нужно — достаточно понять, что он эквивалентен более простой операции). Тренируемся возвращать беглость рук на клавиатуре и глаз на форматах ввода-вывода — сложность придёт в следующих сессиях.

---

Теория

Линейный проход с накоплением состояния. Идём по массиву или строке слева направо и на каждом шаге обновляем одну переменную — счётчик, сумму или флаг. Больше ничего запоминать не нужно.

Когда применять:

• в условии есть «подряд идущие», «непрерывный участок», «пока не встретится»;
• ответ зависит от истории прохода, а не от одного элемента отдельно.

Как решать:

1. Заводим переменную состояния (например, длину текущей серии одинаковых символов).
2. Идём по данным один раз, слева направо.
3. Если условие продолжает выполняться — состояние растёт.
4. Если условие нарушено — состояние сбрасывается в ноль.

Например, для строки 1000000001: серия единиц растёт с каждым новым символом 1, при первом 0 сбрасывается, а на последней 1 начинает расти заново.

Сложность: $O(n)$ по времени, $O(1)$ по памяти.

Где ошибаются: считают «сколько всего» вместо «какой длины именно сейчас» — это разные вопросы.

Симуляция через переформулировку. Когда в условии описан процесс («кубики падают», «жидкость перетекает»), не обязательно проигрывать его шаг за шагом — часто у процесса есть простой финальный результат.

Когда применять:

• процесс описан пошагово, но порядок промежуточных шагов не важен — важен только итог;
• честная симуляция была бы медленной или сложной в реализации.

Как решать:

1. Ищем, что не меняется в процессе, как бы он ни шёл (это называют инвариантом).
2. Показываем, что конечный результат полностью определяется этим инвариантом.
3. Вычисляем результат напрямую по инварианту, без пошагового моделирования.

Например: если кубики падают под гравитацией в столбце, неважно, в каком порядке они падали — итоговый порядок в столбце такой же, как если бы мы просто отсортировали их по весу.

Где ошибаются: пытаются найти переформулировку там, где порядок шагов реально влияет на результат (например, ресурсы ограничены и заканчиваются) — тогда честная симуляция надёжнее.

---

Задача 1 — CF ~900 — «Football»

Что дано

На вход подаётся непустая строка из символов 0 и 1 длиной не больше 100 символов — раскладка игроков двух команд на поле (гарантируется, что игрок хотя бы одной и другой команды есть). Ситуация считается опасной, если есть 7 или более подряд идущих одинаковых символов (то есть 7 подряд игроков одной команды). Нужно вывести YES, если ситуация опасная, и NO — если нет.

Разберём на примере

Возьмём строку 1000000001. Пройдём по ней слева направо и будем считать длину текущей серии одинаковых символов:

На позиции 7 серия нулей достигла длины 7 — значит, ответ YES. Дальше можно даже не досматривать строку до конца: как только где-то встретилась серия длины ≥ 7, ответ уже известен.

Для контраста возьмём строку 001001: серии здесь длиной максимум 2 (00, 1, 00, 1) — нигде не набирается 7 подряд, ответ NO.

Идея решения

Идея в одну фразу: идём по строке один раз, считаем длину текущей серии одинаковых символов подряд, при сбросе серии (символ отличается от предыдущего) обнуляем счётчик — если где-то счётчик достиг 7, ответ YES.

Почему это корректно: серия подряд идущих одинаковых символов — это в точности отрезок строки, где каждый следующий символ равен предыдущему. Как только встречается символ, отличный от предыдущего, старая серия закончилась и началась новая (длиной 1). Достаточно на каждом шаге хранить только длину текущей серии — предыдущие серии уже неважны, они не могут «дотянуться» до 7 задним числом. Это классический линейный проход с одной переменной состояния — O(n) по времени и O(1) по дополнительной памяти (не считая самой строки).

Альтернативный (тоже корректный) способ — проверить, содержит ли строка подстроку "0000000" или "1111111" (семь нулей или семь единиц подряд). При длине строки ≤ 100 это не имеет значения по производительности, но подход с счётчиком нагляднее показывает идею линейного разбора случаев и обобщается на любой другой порог, не только 7.

Псевдокод

прочитать строку s
если длина s == 0:
    // по условию гарантируется, что строка непустая — эта ветка не нужна,
    // но полезно держать её в уме как проверку понимания задачи
    вывести "NO"
    завершить

счётчик = 1
для i от 1 до длина(s) - 1:
    если s[i] == s[i - 1]:
        счётчик = счётчик + 1
    иначе:
        счётчик = 1
    если счётчик >= 7:
        вывести "YES"
        завершить

вывести "NO"

Код решения

Проверка на примерах

Крайние случаи

1. Строка минимальной длины, где встречаются обе команды — например, "10". Серии длиной 1, ответ NO. Код корректно обрабатывает: цикл for i in range(1, len(s)) просто не находит ни одного совпадения соседних символов.
2. Серия ровно длины 7 в самом конце строки — например, строка заканчивается семью одинаковыми символами. Важно не оборвать цикл раньше времени — счётчик должен успеть дойти до 7 на последней позиции. В решении выше цикл идёт до конца строки (или до срабатывания break), это учтено.
3. Несколько отдельных серий, каждая короче 7, но в сумме больше 7 символов той же команды не подряд — например, "000110000110000". Здесь серии нулей длиной 3, 4, 4 — по отдельности каждая меньше 7, и ответ должен быть NO, даже если суммарно нулей больше 7. Алгоритм это учитывает: счётчик сбрасывается при каждой смене символа, никакого «суммарного» подсчёта нет.

Типичные ошибки

1. Забыть инициализировать счётчик единицей, а не нулём. Если начать streak = 0 и не обработать первый символ отдельно, длина первой серии окажется на единицу меньше реальной.
2. Проверять условие > 7 вместо >= 7. Условие задачи — «хотя бы 7 подряд», то есть ровно 7 уже опасно.
3. Считать по всей строке количество нулей/единиц, а не длину подряд идущей серии. Это меняет смысл задачи — считать нужно именно непрерывный отрезок одинаковых символов, а не общее количество символов одной команды в строке.
4. Не читать строку целиком при наличии пробелов или переводов строк на конце ввода — в Python лишний \n в конце input()/readline() обычно не мешает (символы 0/1 не совпадают с \n), но привычка делать .strip() защищает от неожиданностей.

Сложность

Время: $O(n)$, где $n$ — длина строки (до 100). Память: $O(1)$ дополнительной памяти сверх самой строки.

---

Задача 2 — CF ~900 — «Gravity Flip»

Что дано

В коробке стоит $n$ столбцов кубиков в ряд, в $i$-м столбце — $a_i$ кубиков ($1 \le n \le 100$, $1 \le a_i \le 100$). Сначала гравитация тянет кубики вниз (столбцы просто стоят как есть). Затем гравитацию разворачивают на 90 градусов — теперь она тянет все кубики вправо. Нужно определить, сколько кубиков окажется в каждом столбце после разворота гравитации.

Разберём на примере

Возьмём вход:

4
3 2 1 2

Здесь 4 столбца с высотами 3 2 1 2. Представим это как решётку кубиков (каждая строка — один «слой» по высоте, снизу вверх):

Столбец:   1  2  3  4
Высота:    3  2  1  2
Кубики:    #  #     #
           #  #     #
           #

Когда гравитация поворачивает вправо, каждый кубик «скатывается» в сторону последнего столбца, пока не упрётся в другой кубик или в стенку. По сути каждый слой решётки (все кубики на одной высоте) должен собраться в правой части ряда. Если в каком-то слое было ровно $k$ кубиков, то после разворота они займут $k$ самых правых позиций этого слоя.

Ключевое наблюдение: неважно, из каких именно столбцов кубики скатились в новую позицию — важно только итоговое количество кубиков в каждом результирующем столбце. А это количество равно в точности отсортированным по возрастанию исходным высотам, расставленным слева направо. Проверим на примере: отсортируем 3 2 1 2 по возрастанию — получаем 1 2 2 3. Это и есть ответ.

Почему так получается интуитивно: столбец, в котором изначально было меньше всего кубиков, после гравитации, тянущей вправо, окажется самым левым (ему «конкурировать» не с кем — низкие столбцы не мешают друг другу пропускать чужие кубики). А столбец с максимальной высотой съедет в крайнее правое положение, потому что справа от него уже некуда падать. Между этими двумя крайностями столбцы упорядочиваются строго по высоте.

Идея решения

Идея в одну фразу: развернуть гравитацию вправо для столбцов кубиков эквивалентно сортировке высот столбцов по возрастанию.

Доказательство через инвариант: рассмотрим любой горизонтальный слой (уровень высоты $h$). В этом слое кубик стоит в столбце $i$ тогда и только тогда, когда $a_i \ge h$. Когда гравитация тянет вправо, все кубики этого слоя сдвигаются в его правую часть без потери количества — значит, после сдвига в слое $h$ кубик будет ровно в тех столбцах, которые находятся среди $k_h$ самых правых, где $k_h$ — число столбцов с $a_i \ge h$. Но именно так выглядит слой $h$ у отсортированного по возрастанию массива: сначала (слева) идут столбцы пониже, где слоя $h$ уже нет, а справа — столбцы повыше, где слой $h$ есть. Это верно для каждого слоя $h$ от 1 до максимума — значит, итоговая конфигурация столбцов совпадает с отсортированным массивом $a$.

Это ещё один пример того, как честная симуляция процесса не нужна — достаточно понять, к какой более простой операции он сводится. Сортировка занимает $O(n \log n)$, что тривиально укладывается в лимит времени при $n \le 100$.

Псевдокод

прочитать n
прочитать массив a из n чисел
отсортировать a по возрастанию
вывести элементы a через пробел

Код решения

Проверка на примерах

Крайние случаи

1. Один столбец ($n = 1$) — гравитации некуда «сдвигать» кубики относительно других столбцов, ответ совпадает со входом. Сортировка массива из одного элемента тривиально возвращает его же.
2. Все столбцы одной высоты — сортировка не меняет порядок (все элементы равны), вывод совпадает со входом.
3. Уже отсортированный или отсортированный в обратном порядке вход — оба случая корректно обрабатываются стандартной сортировкой без дополнительных условий (второй пример из условия — это как раз уже отсортированный случай).

Типичные ошибки

1. Сортировка по убыванию вместо возрастания. Гравитация вправо — это именно возрастающий порядок слева направо (самый низкий столбец — крайний слева).
2. Попытка честно симулировать падение каждого кубика отдельно (например, циклом «для каждого кубика ищем его новую позицию»). При ограничениях задачи ($n, a_i \le 100$) это не критично по времени, но не нужно — усложняет код и повышает риск ошибки в логике сдвига без выигрыша.
3. Забыть пробел-разделитель или лишний перевод строки в выводе. У Codeforces обычно допустимы лишние пробелы/переводы строк, но при сомнениях лучше выводить числа через один пробел без хвостового пробела перед переводом строки.
4. Чтение входа построчно, когда числа могут быть разбиты на несколько строк. Надёжнее читать весь ввод целиком и разбивать по пробельным символам (как сделано в Python-решении через sys.stdin.read().split()), а не полагаться на то, что все числа второй строки гарантированно на одной физической строке.

Сложность

Время: $O(n \log n)$ на сортировку. Память: $O(n)$ на хранение массива.

---

Самостоятельная тренировка

Прорешай эти четыре задачи самостоятельно — они того же уровня сложности, что и разобранные выше, и закрепляют похожие идеи (линейный разбор случаев и работу с массивом по формуле):

• Codeforces 318A «Even Odds» (~CF 900) — по данным $n$ и $k$ нужно определить, какое число окажется на $k$-й позиции в последовательности, где сначала выписаны все нечётные числа от 1 до $n$ по возрастанию, а затем все чётные.
• Codeforces 1374B «Multiply by 2, divide by 6» (~CF 900) — для каждого из нескольких чисел $n$ найти минимальное количество операций (умножить на 2 или разделить на 6, если делится нацело), чтобы получить 1, либо определить, что это невозможно.
• Codeforces 6A «Triangle» (~CF 900) — по длинам четырёх палочек определить, можно ли (используя ровно три из них) построить невырожденный треугольник, вырожденный треугольник (отрезок) или ни то ни другое.
• Codeforces 63A «Sinking Ship» (~CF 900) — по списку членов экипажа с заданными признаками вывести порядок эвакуации по фиксированным правилам приоритета.

Если застрянешь — разбери задачу с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

На следующей тренировке остаёмся на уровне CF ~1000 и переходим от разбора случаев на строке к целочисленной арифметике без ошибок округления — там пригодится аккуратность с делением и остатками.