VK Cup 2022 - Квалификация (Engine) |
---|
Finished |
В этой версии задачи размеры копируемых файлов не превышают $$$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$$$ включительно, что существует момент времени, в который оба прогресс-бара одновременно показывают это число. Выведите эти числа в порядке возрастания.
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число копируемых файлов.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{10}$$$) — размеры файлов в байтах в том порядке, в котором они будут копироваться.
Выведите в возрастающем порядке все числа от $$$0$$$ до $$$100$$$ включительно такие, что существует момент времени, в который на обоих прогресс-барах одновременно показывается это число.
1 6
0 16 33 50 66 83 100
2 100 500
0 95 96 97 98 99 100
4 10000000000 2 2 9999999998
0 50 99 100
6 170 130 400 256 30 100
0 17 43 44 84 90 99 100
В первом тесте копируется всего один файл, поэтому оба прогресс-бара всегда показывают одинаковые значения.
Во втором тесте первый прогресс-бар сразу же уйдёт вперёд, потом сбросится в ноль и начнёт догонять второй прогресс-бар заново. В конце копирования прогресс-бары некоторое время будут показывать одно и то же число.
Обратите внимание, что третий тест в этой версии задачи отличается от третьего теста в предыдущей версии задачи.
Name |
---|