Чистая реализация без лишних условий — задача «Alice, Bob and Candies» РАЗБОР

Implementation-задачи полосы CF 1100–1500 — это упражнения не на алгоритм (который часто очевиден), а на чистоту реализации. Соблазн расписать всё «случай за случаем» через вложенные if'ы заметно снижает шанс пройти все тесты с первого раза: каждое лишнее ветвление — это потенциальный источник off-by-one, забытого симметричного случая или ошибки на границах массива.

Эта задача — учебный пример того, как два указателя и один аккумулятор полностью заменяют 5–6 веток рассуждения «если конфет хватает / если кончились / если очередь Alice / если очередь Bob / если ход первый». Алгоритм — за один проход массива, за линейное время и без специальной обработки конца игры.

---

Что дано

В коробке стоит ряд из $n$ конфет, $i$-я конфета имеет вес $a_i$. Двое — Alice и Bob — едят их по очереди:

• Alice всегда ест с левого края оставшегося ряда.
• Bob всегда ест с правого края оставшегося ряда.
• Первой ходит Alice; на самом первом ходу она съедает только одну конфету (вес 1-й конфеты от левого края).
• На каждом следующем ходу игрок должен съесть минимально возможное непустое количество подряд идущих конфет со своего края так, чтобы суммарный вес съеденного на этом ходу был строго больше, чем съел соперник на предыдущем ходу.
• Если конфет на оставшемся ряду не хватает, чтобы превысить вес соперника, игрок съедает все оставшиеся конфеты, и игра заканчивается.

Нужно вывести три числа:

1. Общее количество ходов, сделанных в игре.
2. Суммарный вес съеденного Alice.
3. Суммарный вес съеденного Bob.

Ограничения

• $1 \le t \le 5000$ — количество тестов.
• $1 \le n \le 1000$ — длина ряда конфет в одном тесте.
• $1 \le a_i \le 1000$ — вес каждой конфеты.
• Время — 2 секунды, память — 256 МБ.
• Сумма $n$ по всем тестам $\le 2 \cdot 10^5$.

Формат ввода

t
n_1
a_1 a_2 ... a_{n_1}
n_2
a_1 a_2 ... a_{n_2}
...

Формат вывода

Для каждого теста — одна строка из трёх чисел через пробел.

Примеры

Будем разбирать на нескольких показательных входах.

Пример A (типичный): $n = 11$, $a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]$. Ответ: 6 23 21.

Пример B (один элемент): $n = 1$, $a = [1000]$. Ответ: 1 1000 0.

Пример C (всё одинаковое): $n = 3$, $a = [1, 1, 1]$. Ответ: 2 1 2.

Пример D (возрастающий): $n = 13$, $a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$. Ответ: 6 45 46.

Пример E (Bob не может превысить): $n = 2$, $a = [2, 1]$. Ответ: 2 2 1.

Пример F (большая «семёрка» в середине): $n = 6$, $a = [1, 1, 7, 1, 1, 1]$. Ответ: 4 9 3.

Пример G (все единицы): $n = 7$, $a = [1, 1, 1, 1, 1, 1, 1]$. Ответ: 4 4 3.

Разберём пример A руками

$a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]$. Левый указатель $l = 0$, правый указатель $r = 10$. Веса съеденного: last = 0 (никто ещё не ел).

Итог: 6 ходов, Alice = $3 + 6 + 14 = 23$, Bob = $5 + 8 + 8 = 21$. Сходится с эталоном.

Ключевое наблюдение из ручного прогона: последний ход Bob — особый. Bob набирает $3 + 5 = 8$, что меньше предыдущего веса Alice (14), но после этих двух конфет массив уже пуст. По правилам Bob съедает всё оставшееся; это тот самый «специальный» случай, который при наивной реализации хочется отдельно обрабатывать через if. На самом деле он естественно обрабатывается тем же циклом, если правильно сформулировать условие выхода.

---

Идея решения

Алгоритм в одну фразу.

Два указателя $l$ (слева) и $r$ (справа), переменная last — вес съеденного на предыдущем ходу. На каждом ходу игрок $\to$ внутренний цикл, добирающий конфеты со своего края, пока накопленный вес не превысит last или указатели не сошлись. Внешний цикл — пока $l \le r$.

Внутренний цикл — это вся реализация хода. Он сам обрабатывает три случая, которые без него потребовали бы трёх if:

1. Игрок успел набрать $> \text{last}$ — выход из внутреннего цикла, ход успешен.
2. Массив кончился до того, как набрали $> \text{last}$ — внутренний цикл всё равно выходит (по условию $l \le r$), игрок ест всё что собрал. Внешний цикл на следующей итерации увидит $l > r$ и завершится.
3. На самом первом ходу last = 0 — Alice ест ровно одну конфету (любая положительная конфета даёт сумму $\ge 1 > 0$), внутренний цикл выходит после первой добавки.

Все три случая закрываются одной формулировкой условия внутреннего цикла. В этом и состоит «чистая реализация»: вместо отдельных веток алгоритм опирается на инвариант, который верен во всех ситуациях.

Почему это работает корректно

• Условие «строго больше». Внутренний цикл идёт «пока съеденное меньше или равно last и массив ещё не исчерпан». Выход происходит ровно в тот момент, когда либо условие нарушено (eaten > last, ход успешный), либо массив пуст (l > r, ход «доедание»).
• Минимальность набора. Цикл добирает конфеты по одной за итерацию. На момент превышения last мы останавливаемся — добавлять ещё одну конфету уже не нужно. Это и есть «минимально возможное непустое количество».
• Чередование игроков. Переменная turn (0 — Alice, 1 — Bob) флипается после каждого хода: turn ^= 1. Никакой двойной логики «если ход чётный / если ход нечётный» — один и тот же код для обоих игроков, отличается только указатель и счётчик-аккумулятор.

---

Решение: псевдокод

для каждого теста:
    прочитать n и массив a
    l ← 0; r ← n - 1
    alice_total ← 0; bob_total ← 0
    last ← 0
    moves ← 0
    turn ← 0   # 0 = Alice (ест слева), 1 = Bob (ест справа)

    пока l ≤ r:
        eaten ← 0
        пока l ≤ r и eaten ≤ last:
            если turn = 0:
                eaten ← eaten + a[l]
                l ← l + 1
            иначе:
                eaten ← eaten + a[r]
                r ← r - 1
        если turn = 0:
            alice_total ← alice_total + eaten
        иначе:
            bob_total ← bob_total + eaten
        last ← eaten
        moves ← moves + 1
        turn ← turn XOR 1

    вывести moves, alice_total, bob_total

Сложность одного теста: $O(n)$ — каждый из указателей сдвигается ровно $n$ раз суммарно по всем итерациям внутреннего цикла. С учётом $\sum n \le 2 \cdot 10^5$ — итог $O(\sum n)$ по всем тестам.

---

Код решения

Комментарии по реализации.

• Быстрый ввод обязателен. В Python — sys.stdin.buffer.read().split() через единственное чтение буфера, иначе $5000$ тестов с $n \le 1000$ ($\sim 2 \cdot 10^5$ чисел) могут упереться в TL через input() в цикле. В C++ — ios::sync_with_stdio(false) достаточно.
• turn ^= 1 — самый компактный способ переключить 0/1. Альтернативы: turn = 1 - turn, turn = (turn + 1) % 2. Все эквивалентны.
• Тип для сумм. Максимум eaten — сумма всех весов до $1000 \cdot 1000 = 10^6$, в int32 укладывается с запасом. В Python int автоматически большой, в C++ держим long long для аккумуляторов — привычка окупается на чуть более жёстких ограничениях.
• Идиомы ++moves, eaten += a[l++] в C++ — типичны для соревновательного кода. Не стоит злоупотреблять, но в горячем цикле читаемы.

---

Проверим на всех 7 примерах из условия

Прогоняем алгоритм по каждому из примеров A–G и сравниваем с эталонными ответами.

A: $n = 11$, $a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]$

Уже разобрали в «руками на примере». Ходов 6, Alice 23, Bob 21. 6 23 21 ✓.

B: $n = 1$, $a = [1000]$

Ход 1 (Alice): eaten = 0 ≤ 0 = last, добираем $a[0] = 1000$, l = 1. Теперь l = 1 > 0 = r, выход из внутреннего. alice = 1000, last = 1000, ход 1.

Внешний: l = 1 > 0 = r, выход. 1 1000 0 ✓.

C: $n = 3$, $a = [1, 1, 1]$

Ход 1 (Alice): добираем $a[0] = 1$, l = 1. eaten = 1 > 0 = last — выход. alice = 1, last = 1.

Ход 2 (Bob): eaten = 0 ≤ 1, добираем $a[2] = 1$, r = 1. eaten = 1 ≤ 1, добираем $a[1] = 1$, r = 0. Теперь l = 1 > 0 = r, выход внутреннего. bob = 2, last = 2.

Внешний: l > r, выход. 2 1 2 ✓.

D: $n = 13$, $a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$

Ход 1 (Alice): $1$. alice = 1, last = 1. Ход 2 (Bob): $13$. bob = 13, last = 13. Ход 3 (Alice): $2 + 3 + 4 + 5 = 14 > 13$. alice = 15, last = 14. Ход 4 (Bob): $12 + 11 = 23 > 14$. bob = 36, last = 23. Ход 5 (Alice): $6 + 7 + 8 + 9 = 30 > 23$. alice = 45, last = 30. Ход 6 (Bob): $10$ (массив исчерпан, $10 \le 30$, но l > r). bob = 46.

6 45 46 ✓.

E: $n = 2$, $a = [2, 1]$

Ход 1 (Alice): $2$. alice = 2, last = 2. Ход 2 (Bob): добираем $a[1] = 1$, r = 0. eaten = 1 ≤ 2, продолжаем — но l = 1 > 0 = r, выход. bob = 1, last = 1.

2 2 1 ✓.

F: $n = 6$, $a = [1, 1, 7, 1, 1, 1]$

Ход 1 (Alice): $1$. alice = 1, last = 1. Ход 2 (Bob): $a[5] = 1$ ($\le 1$), r = 4. $a[4] = 1$, сумма $2 > 1$. bob = 2, last = 2. Ход 3 (Alice): $a[1] = 1$ ($\le 2$), l = 2. $a[2] = 7$, сумма $8 > 2$. alice = 9, last = 8. Ход 4 (Bob): $a[3] = 1$ ($\le 8$), r = 2. Теперь l = 3 > 2 = r, выход. bob = 3.

4 9 3 ✓.

G: $n = 7$, $a = [1, 1, 1, 1, 1, 1, 1]$

Ход 1 (Alice): $1$. alice = 1, last = 1. Ход 2 (Bob): $a[6] = 1$ ($\le 1$), r = 5. $a[5] = 1$, сумма $2 > 1$. bob = 2, last = 2. Ход 3 (Alice): $a[1] = 1$ ($\le 2$), l = 2. $a[2] = 1$, сумма $2$ ($\le 2$), l = 3. $a[3] = 1$, сумма $3 > 2$. alice = 4, last = 3. Ход 4 (Bob): $a[4] = 1$ ($\le 3$), r = 3. l = 4 > 3 = r, выход. bob = 3.

4 4 3 ✓.

Все 7 примеров сходятся. Алгоритм корректен.

---

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

1. $n = 1$ — одна конфета

Alice съедает её на первом ходу (любая положительная даёт eaten = a[0] > 0 = last). Внешний цикл сразу выходит. Ход 1, Alice = $a[0]$, Bob = 0. Покрыт примером B.

2. Указатели сходятся ровно после первого набора

Как в примере E ($n = 2$): после первого хода Alice указатели $l = 1, r = 1$. Bob делает свой ход, после внутреннего цикла $l = 1, r = 0$, и внешний цикл завершается.

3. Игрок не может превысить, и массив пуст ровно в этот момент

Как в примере F: на 4-м ходу Bob берёт одну конфету ($a[3] = 1$), eaten = 1 ≤ 8 = last, но указатели сходятся. Bob съедает $1$ — это легитимный последний ход, игра заканчивается.

4. Все одинаковые конфеты

Пример G — все единицы. Каждый ход суммарный вес растёт ровно на 1: Alice 1, Bob 2, Alice 3, Bob (остаток). Видно, как даже на простейшем входе чередование $+1$ съедает массив за минимальное число ходов.

5. Одна гигантская конфета в середине

Пример F с $a[2] = 7$. На 3-м ходу Alice цепляет именно её и резко обгоняет Bob. После такой «гиганта» оставшийся массив игрока часто оказывается недостаточным для ответа — игра заканчивается на следующем ходу.

6. Очень длинный возрастающий массив

Пример D — сумма $\frac{n(n+1)}{2} = 91$ распределяется неравномерно: первые ходы дают маленькие суммы, к середине обе стороны набирают «крупными порциями». В таких случаях ходов получается мало (6 на $n = 13$), даже несмотря на длинный массив.

---

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

1. Отдельная ветка для «массив кончился, игрок не дотянул». Соблазн написать что-то вроде if l > r and eaten <= last: alice_total += eaten; break. Это работает, но удваивает логику добавления в счётчик. Если внутренний цикл правильно сформулирован — этот случай уже обрабатывается естественно: цикл выходит сам, а добавление в счётчик случается одно — в общей ветке после внутреннего цикла.
2. Условие внутреннего цикла «eaten < last» вместо «eaten <= last». Тогда при равенстве eaten == last мы не добавим следующую конфету и завершим ход, хотя по правилам нужно строго больше. Получится ход, в котором сумма равна предыдущей, что нарушает условие задачи.
3. Перепутанные направления. Alice ест с левого края (увеличиваем l), Bob — с правого (уменьшаем r). Симметричная ошибка часто проявляется на тестах, где результаты Alice и Bob поменялись местами — пример D: ожидаем 45 46, выводим 46 45.
4. Забыть обнулить eaten в начале каждого хода. Тогда вес ходов накапливается, и второй ход стартует с уже ненулевого аккумулятора. Пример E: Alice ест $2$, Bob «должен» съесть $> 2$. Если eaten = 2 ещё с предыдущего хода, цикл сразу не входит, Bob ест 0. Безусловно WA.
5. Использовать eaten = 0 глобально (одна переменная на всю игру). Должен быть локальный аккумулятор хода. Глобальный вариант приводит к ошибке из п. 4 в усиленной форме.
6. Перепутать last и eaten в условии. Условие — «пока съеденное на текущем ходу не превышает съеденное на предыдущем». Сравнивать нужно eaten <= last, не last <= eaten (это всегда true в нужных моментах) и не last < eaten (это только проверяет, превысили ли — но не управляет циклом).
7. int вместо long long для накопителей в C++ на чуть более жёсткой задаче. Здесь в данных всё помещается в int32, но привычка к 64-битным аккумуляторам полезна.

---

Анализ сложности

• Время: $O(n)$ на тест. Внутренний цикл сдвигает один из указателей за каждую итерацию, оба указателя суммарно сдвигаются не более $n$ раз. Внешний цикл — не более $n$ итераций.
• Память: $O(n)$ на тест (массив $a$).
• С учётом всех тестов: $O(\sum n) = O(2 \cdot 10^5)$, что укладывается в TL 2 секунды с большим запасом.

---

Что ещё полезно потренировать

Задачи с похожей структурой (два указателя на массиве + аккумулятор, или симуляция игры с очередями) — все с возраст-нейтральных платформ.

• Codeforces 363B «Fence», $\sim 1100$ — скользящее окно длины $k$ с минимальной суммой. Тоже один проход массива, no nested if'ов.
• Codeforces 339B «Xenia and Ringroad», $\sim 1100$ — симуляция перемещения по кругу. Хорошая тренировка чистоты — соблазн писать «if впереди / if позади» убирается одной формулой по модулю.
• acmp.ru, раздел «Одномерные массивы» — много задач уровня 1100–1400 на «два указателя» или «один проход с аккумулятором». Старые задачи серии — отличная тренировка дисциплины «один цикл вместо пяти if'ов».
• Codeforces 1399C «Boats Competition», $\sim 1300$ — два указателя на отсортированном массиве с подсчётом пар. Чистая реализация — без вложенных условий, аналогично сегодняшней задаче.

Для следующего шага — попробовать задачу, где один цикл заменяет уже 3–4 ветки рассуждений: типичный пример — задачи на «движение фигур по полю с ограничениями» или «обход с двумя стеками».

---

Итого

• Идея: два указателя $l, r$, аккумулятор last. Внешний цикл while l ≤ r, внутренний — while l ≤ r and eaten ≤ last. Чередование игроков через turn ^= 1.
• Сложность: $O(n)$ на тест, $O(\sum n)$ суммарно.
• Чистота: ни одного if для «массив кончился», «первый ход», «игрок не дотянул» — все три случая обрабатываются единым условием внутреннего цикла.
• Типичные ловушки: < вместо <= в условии цикла, забытое обнуление eaten на новом ходу, перепутанные направления указателей, отдельная ветка для конца игры.