Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли а1 участников, второе место — a2 участников, …, заключительное n-е место заняли аn участников.
Согласно регламенту соревнования, требуется каждого участника наградить призом.
Суммарно на все призы в смете олимпиады заложена сумма в Р денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:
1) Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;
2) Всем участникам, занявшим заключительное п-е место, достанутся призы стоимостью в 1 денежную единицу;
3) Разница d между призом участника на і-м месте и призом участника на і + 1-м месте должна быть одинакова для всех i от 1 до n — 1, в том числе может быть и так, что d = 0, то есть все участники могут получить одинаковые призы независимо от занятого ими места.
Необходимо определить, какую максимальную разницу d жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы Р.
1 Ответ
Ответ: определить, какую максимальную разницу d жюри может запланировать
C++:
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
int main()
{
ll n; cin >> n;
vector<ll> 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)