codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1769B1.md (3997B)


      1 Source: https://codeforces.com/problemset/problem/1769/B1
      2 
      3 B1. Копирование файлов I
      4 
      5 ограничение по времени на тест
      6 
      7 2 секунды
      8 
      9 ограничение по памяти на тест
     10 
     11 512 мегабайт
     12 
     13 ввод
     14 
     15 стандартный ввод
     16 
     17 вывод
     18 
     19 стандартный вывод
     20 
     21 В этой версии задачи размеры копируемых файлов не превышают $1000$ байт.
     22 
     23 Вы копируете с одного сервера на другой $n$ файлов размером $a_1, a_2, \ldots, a_n$ байт. Файлы копируются последовательно в заданном порядке.
     24 
     25 При копировании вы видите два прогресс-бара: первый показывает процент скопированных данных в текущем файле, а второй — общий процент скопированных данных по всем $n$ файлам. Оба процента отображаются округлёнными вниз до целого числа. Значения на прогресс-барах обновляются после копирования каждого байта.
     26 
     27 Формально, после копирования байта номер $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$ процентов.
     28 
     29 Найдите все такие целые числа от $0$ до $100$ включительно, что существует момент времени, в который оба прогресс-бара одновременно показывают это число. Выведите эти числа в порядке возрастания.
     30 
     31 Входные данные
     32 
     33 В первой строке задано одно целое число $n$ ($1 \le n \le 100$) — число копируемых файлов.
     34 
     35 Во второй строке заданы $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1000$) — размеры файлов в байтах в том порядке, в котором они будут копироваться.
     36 
     37 Выходные данные
     38 
     39 Выведите в возрастающем порядке все числа от $0$ до $100$ включительно такие, что существует момент времени, в который на обоих прогресс-барах одновременно показывается это число.
     40 
     41 Примеры
     42 
     43 Входные данные
     44 
     45 ```
     46 1
     47 6
     48 ```
     49 
     50 Выходные данные
     51 
     52 ```
     53 0
     54 16
     55 33
     56 50
     57 66
     58 83
     59 100
     60 ```
     61 
     62 Входные данные
     63 
     64 ```
     65 2
     66 100 500
     67 ```
     68 
     69 Выходные данные
     70 
     71 ```
     72 0
     73 95
     74 96
     75 97
     76 98
     77 99
     78 100
     79 ```
     80 
     81 Входные данные
     82 
     83 ```
     84 4
     85 1000 2 2 998
     86 ```
     87 
     88 Выходные данные
     89 
     90 ```
     91 0
     92 50
     93 99
     94 100
     95 ```
     96 
     97 Входные данные
     98 
     99 ```
    100 6
    101 170 130 400 256 30 100
    102 ```
    103 
    104 Выходные данные
    105 
    106 ```
    107 0
    108 17
    109 43
    110 44
    111 84
    112 90
    113 99
    114 100
    115 ```
    116 
    117 Примечание
    118 
    119 В первом тесте копируется всего один файл, поэтому оба прогресс-бара всегда показывают одинаковые значения.
    120 
    121 Во втором тесте первый прогресс-бар сразу же уйдёт вперёд, потом сбросится в ноль и начнёт догонять второй прогресс-бар заново. В конце копирования прогресс-бары некоторое время будут показывать одно и то же число.