Олимпиадная информатика ПОМОГИТЕ, ПОЖАЛУЙСТА
Награждение участников олимпиады
Ограничение по времени: 1
секунда
Ограничение по памяти: 256
мегабайт
—
Мы все третье место заняли: и я,
и Мишка, и Толька, и Кимка, все‑все.
Вовка —
первое, рыжий лягушонок —
второе, а мы, остальные восемнадцать
человек, мы заняли третье.
Так инструктор сказал!
Виктор Драгунский, «Третье место
в стиле баттерфляй».
Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли 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
‑битный тип данных, например, long long в C++, int64
в Free Pascal, long в Java.
Система оценки
Решения, правильно работающие для случаев, в которых P/n
не превосходит 106
, получат не менее 60
баллов.
Замечание
В примере участники распределились следующим образом:
1
место —
2
участника,
2
место —
1
участник,
3
место —
3
участника,
4
место —
4
участника,
5
место —
2
участника.
Если заложить разницу между призами в 4
денежных единицы, то распределение стоимостей призов будет следующим:
5
место —
2
приза по 1
денежной единице,
4
место —
4
приза по 5
денежных единиц,
3
место —
3
приза по 9
денежных единиц,
2
место —
1
приз по 13
денежных единиц,
1
место —
2
приза по 17
денежных единиц.
Суммарно на призы будет потрачено 2⋅1+4⋅5+3⋅9+1⋅13+2⋅17=96
денежных единиц, что укладывается в смету в 100
денежных единиц.
Если же заложить разницу между призами в 5
денежных единиц, то потребуется 2⋅1+4⋅6+3⋅11+1⋅16+2⋅21=117
денежных единиц, что превышает сумму, указанную в смете.
Ввод
Вывод
5
2
1
3
4
2
100
#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 *= 3;
}
while(R - L > 1){
long long M = (R + L) / 2;
if(ford(M) <= P){
L = M;
}
else{
R = M;
}
}
cout << L;
}
это на 100 баллов
#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;
}
Ответ удалён тг @succuberry - скину все ответы)