Помогите с задачей, тайм лимит на 3-м тесте

Question

Вы копируете с одного сервера на другой n файлов размером a1,a2,…,an байт. Файлы копируются последовательно в заданном порядке.

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

Формально, после копирования байта номер x из файла номер i первый прогресс-бар показывает ⌊100⋅x/a[i]⌋ процентов, а второй — ⌊100⋅(a[1]+a[2]+…+a[i−1]+x)/a[1]+a[2]+…+a[n]⌋ процентов. В самом начале копирования оба прогресс-бара показывают 0 процентов.

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

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

Во второй строке заданы n целых чисел a1,a2,…,an (1≤a[i]≤1010) — размеры файлов в байтах в том порядке, в котором они будут копироваться.

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

Вот мой код:

```
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q;
    cin >> q;
    vector<int> a(q);
    int sum_all = 0;
    for(int i =0; i < q; ++i){
        cin >> a[i];
        sum_all += a[i];
    }
    int sum_x =0;
    set<int> eq;
    for(int i =0; i < q; ++i){
        for(int j =0; j <= a[i]; ++j){
            int ans =(100 * j) / a[i];
            int ans_2 = (100 * (sum_x + j))/sum_all;
            if(ans == ans_2){
                eq.insert(ans);
            }   
        }
        sum_x += a[i];    
    }
    //cout << eq.size() << endl;
    for(auto i : eq){
        cout << i << endl;
    }
}

```

Answer 1

TODO: перевести на С++.

Внутри файла оба бара не убывают. В начале файла измеряем оба процента. Если один меньше, то вычисляем номер байта на котором он станет равным или большим второго. Делаем прыжок - до этого байта равенства баров наступить не может. Если бары равны, печатаем значение и прыгаем к следующему проценту. Решение принято на контесте:

def percent(i, n):
    return 100 * i // n
 
 
def first_position(p, n):
    return (n * p + 99) // 100
 
 
def search(a):
    n = sum(a)
 
    yield 0
    p = 0
 
    i = 0
    for f in a:
        j = 1
        while j <= f:
            pi = percent(j + i, n)
            pj = percent(j    , f)
 
            if pi < pj:
                j = first_position(pj, n) - i
            elif pj < pi:
                j = first_position(pi, f)
            else:
                if pi > p:
                    yield pi
                    p = pi
                j = min(first_position(p + 1, n) - i, first_position(p + 1, f))
 
        i += f
 
 
input()
print(*search(tuple(map(int, input().split()))), sep='\n')

БЛОГ НА HUSL

Помогите с задачей, тайм лимит на 3-м тесте

Ответы (1 шт):