Задача по программированию можете помочь пожалуйста
Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли a1
участников, второе место — a2 участников, ..., заключительное n ‑е место заняли an
участников.
Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в P
денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:
1)
Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;
2)
Всем участникам, занявшим заключительное n
‑е место, достанутся призы стоимостью в 1
денежную единицу;
3) Разница d
между призом участника на i ‑м месте и призом участника на i+1 ‑м месте должна быть одинакова для всех i от 1 до n−1 , в том числе может быть и так, что d=0 , то есть все участники могут получить одинаковые призы независимо от занятого ими места.
Необходимо определить, какую максимальную разницу d
жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы P .
Формат входных данных
В первой строке входных данных содержится одно натуральное число n
—
количество различных мест, которые заняли участники олимпиады (2≤n≤105 ). В следующих n
строках, по одному в строке, находятся натуральные числа ai — количество участников, занявших i ‑е место (i от 1 до n ). Общее количество участников a1+a2+...+an не превосходит 1018 , любое ai не менее 1 . В последней строке находится натуральное число P — сумма, заложенная в смете на призы (P≤1018 ). Гарантируется, что P>a1+a2+...+an , то есть для каждого участника можно купить приз стоимостью как минимум в одну денежную единицу.
Формат выходных данных
Выведите одно неотрицательное целое число — максимальную разницу d , которую можно запланировать, не выходя за пределы суммы P
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64 ‑битный тип данных
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
long long ford(long long M){
long long res = 0, psum = 1, t = 1;
for(int i = n; i >= 1; i--){
res += psum * (v[i] - v[i - 1]);
t += M;
psum += t;
}
return res;
}
int main(){
cin >> n;
v.resize(n + 1);
v[0] = 0;
for(int i = 1; i <= n; i++){
cin >> v[i];
}
long long P;
cin >> P;
long long L = 0, R = 1;
while(ford(R) <= P){
R *= 2;
}
while(R - L > 1){
long long M = (R + L) / 2;
if(ford(M) <= P){
L = M;
}
else{
R = M;
}
}
cout << L;
}
n = int(input())
a = [0] * n
one = 0
two = 0
for i in range(n):
a[i] = int(input())
one +=(n-i-1) * a[i]
two += a[i]
p = int(input())
p -= two
print(p//one)
тг @succuberry - скину все ответы)