Копирование файлов II
Contest: VK Cup 2022 - Квалификация (Engine)
Difficulty rating: 1400
Tags: *special, binary search, brute force, math

В этой версии задачи размеры копируемых файлов не превышают $$$10^{10}$$$ байт.

Вы копируете с одного сервера на другой $$$n$$$ файлов размером $$$a_1, a_2, \ldots, a_n$$$ байт. Файлы копируются последовательно в заданном порядке.

При копировании вы видите два прогресс-бара: первый показывает процент скопированных данных в текущем файле, а второй — общий процент скопированных данных по всем $$$n$$$ файлам. Оба процента отображаются округлёнными вниз до целого числа. Значения на прогресс-барах обновляются после копирования каждого байта.

Формально, после копирования байта номер $$$x$$$ из файла номер $$$i$$$ первый прогресс-бар показывает $$$\lfloor \frac{100 \cdot x}{a_i} \rfloor$$$ процентов, а второй — $$$\lfloor \frac{100 \cdot (a_1 + a_2 + \ldots + a_{i - 1} + x)}{a_1 + a_2 + \ldots + a_n} \rfloor$$$ процентов. В самом начале копирования оба прогресс-бара показывают $$$0$$$ процентов.

Найдите все такие целые числа от $$$0$$$ до $$$100$$$ включительно, что существует момент времени, в который оба прогресс-бара одновременно показывают это число. Выведите эти числа в порядке возрастания.

Input format:
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число копируемых файлов.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{10}$$$) — размеры файлов в байтах в том порядке, в котором они будут копироваться.

Output format:
Выведите в возрастающем порядке все числа от $$$0$$$ до $$$100$$$ включительно такие, что существует момент времени, в который на обоих прогресс-барах одновременно показывается это число.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
В первом тесте копируется всего один файл, поэтому оба прогресс-бара всегда показывают одинаковые значения.

Во втором тесте первый прогресс-бар сразу же уйдёт вперёд, потом сбросится в ноль и начнёт догонять второй прогресс-бар заново. В конце копирования прогресс-бары некоторое время будут показывать одно и то же число.

Обратите внимание, что третий тест в этой версии задачи отличается от третьего теста в предыдущей версии задачи.

Example input:
1
6

Example output:
0
16
33
50
66
83
100

Example input:
2
100 500

Example output:
0
95
96
97
98
99
100

Editorial:
В первой версии задачи достаточно перебрать каждый байт, проверить, совпали ли значения прогресс-баров, и выбрать только уникальные значения среди совпадающих.
Пример решения первой версии на Python:
Во второй версии перебор всех байтов недостаточно эффективен. Вместо этого переберём значения от $$$1$$$ до $$$100$$$ для каждого файла и определим, существует ли такой момент в процессе копирования этого файла, что оба прогресс-бара показывают данное значение.
Для этого нужно решить систему из двух уравнений: $$$\begin{cases} \lfloor \frac{100 \cdot x}{a_i} \rfloor = v \\ \lfloor \frac{100 \cdot (x + p_i)}{s} \rfloor = v \end{cases}$$$
Здесь $$$x$$$ — искомое число байт (момент копирования), $$$v$$$ — целевое значение в процентах, $$$p_i = a_1 + a_2 + \ldots + a_{i-1}$$$, а $$$s = a_1 + a_2 + \ldots + a_n$$$.
Преобразуем уравнения в неравенства: $$$\begin{cases} v \le \frac{100 \cdot x}{a_i} < v + 1 \\ v \le \frac{100 \cdot (x + p_i)}{s} < v + 1 \end{cases}$$$
Преобразуем далее, используя то, что $$$x$$$ должно быть целым числом: $$$\begin{cases} x \ge \max(\lceil \frac{v \cdot a_i}{100} \rceil, \lceil \frac{v \cdot s}{100} \rceil - p_i) \\ x \le \min(\lceil \frac{(v + 1) \cdot a_i}{100} \rceil - 1, \lceil \frac{(v + 1) \cdot s}{100} \rceil - 1 - p_i) \\ \end{cases}$$$
Наконец, вычислим оба значения в правых частях неравенств и сравним между собой, чтобы узнать, существует ли подходящее для нас $$$x$$$. Для вычисления $$$\lceil \frac{a}{b} \rceil$$$ можно использовать формулу $$$(a + b - 1) \operatorname{div} b$$$, где $$$\operatorname{div}$$$ — целочисленное деление.
Также вместо решения неравенств в явном виде можно было воспользоваться бинарным поиском.
Пример решения второй версии на Python: