[Solution] File Copy II Codeforces Solution VK Cup

B2. File Copy II

test time limit

2 seconds

memory limit per test

512 megabytes

input

standard input

conclusion

standard output

In this version of the task, the sizes of copied files do not exceed1010${\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">10</span></span>}}^{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">10</span></span>}}$byte.

You are copying from one server to another𝑛$n$files size𝑎1,𝑎2,…,𝑎𝑛$a_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">2</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>\dots <span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}}$byte. The files are copied sequentially in the specified order.

When copying, you see two progress bars: the first shows the percentage of copied data in the current file, and the second shows the total percentage of copied data for all𝑛$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}$files. Both percentages are displayed rounded down to a whole number. The values ​​on the progress bars are updated after each byte is copied.

Formally, after copying the byte number𝑥$x$from file number𝑖$i$first progress bar shows⌊100⋅𝑥𝑎𝑖⌋$<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\lfloor </span></span>\frac{100\cdot x}{a_i}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\rfloor </span></span>$percent, and the second⌊100⋅(𝑎1+𝑎2+…+𝑎𝑖−1+𝑥)𝑎1+𝑎2+…+𝑎𝑛⌋$<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\lfloor </span></span>\frac{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\cdot </span></span>({\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">2</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>\dots <span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}-\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">x</span></span>})}{{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">2</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\dots </span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">+</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_n}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\rfloor </span></span>$percent. At the very beginning of copying, both progress bars show0$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">0</span></span>}$percent.

Find all such integers from0$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">0</span></span>}$to100$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}$inclusive, that there is a point in time at which both progress bars show this number at the same time. Print these numbers in ascending order.

Input data

The first line contains one integer𝑛$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}$ (1≤𝑛≤100$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}\le \mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}$) is the number of copied files.

The second line contains𝑛$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}$integers𝑎1,𝑎2,…,𝑎𝑛${\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">2</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\dots </span></span><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">,</span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">n</span></span>}}$(1≤𝑎𝑖≤1010$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">1</span></span>}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">a</span></span>}}_{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">i</span></span>}}<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">\le </span></span>{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">10</span></span>}}^{\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">10</span></span>}}$) — file sizes in bytes in the order in which they will be copied.

Output

Print in ascending order all numbers from0$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">0</span></span>}$to100$\mathrm{<span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;"><span\; style="transition:\; none\; 0s\; ease\; 0s;\; vertical-align:\; inherit;">100</span></span>}$inclusive such that there is a moment in time at which this number is simultaneously shown on both progress bars.