Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли а1 участников, второе место — a2 участников, …, заключительное n-е место заняли аn участников.

Question

Вопрос. Полная версия

Согласно регламенту соревнования, требуется каждого участника наградить призом.

Суммарно на все призы в смете олимпиады заложена сумма в Р денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:

1) Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;

2) Всем участникам, занявшим заключительное п-е место, достанутся призы стоимостью в 1 денежную единицу;

3) Разница d между призом участника на і-м месте и призом участника на і + 1-м месте должна быть одинакова для всех i от 1 до n — 1, в том числе может быть и так, что d = 0, то есть все участники могут получить одинаковые призы независимо от занятого ими места.

Необходимо определить, какую максимальную разницу d жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы Р.

Ответ

Answer 1

C++:

#include

using namespace std;

#define ll long long

int main()

{

ll n; cin >> n;

vector a(n);

ll sum1 = 0;

ll sum2 = 0;

for (ll i = 0; i < n; ++i) { cin >> a[i];

sum1 += (n — i — 1) * a[i];

sum2 += a[i];

}

ll p; cin >> p;

p -= sum2;

cout << p / sum1 << «\n»;

return 0;

}

Python:

n = int(input())

a = [0] * n

sum1 = 0

sum2 = 0

for i in range(n):

a[i] = int(input())

sum1 += (n — i — 1) * a[i]

sum2 += a[i]

p = int(input())

p -= sum2

print(p // sum1)