Петя любит плавать в реке. Место, доступное для плавания, ограничено буйками. Плавать левее первого буйка и правее последнего буйка запрещено. Линия, вдоль которой расположены N буйков, проходит параллельно берегу.
Будем считать, что буйки пронумерованы числами от 1 до N слева направо. Известны расстояния S1, S2, … SN-1, где Sj — расстояние от буйка j до буйка (j + 1).
В хорошую погоду Петя входит в воду напротив первого буйка, очень быстро доплывает до него, а затем несколько раз плавает до последнего буйка и обратно. После этого он возвращается от первого буйка к берегу. Но сегодня так не получится: по прогнозу погоды через Т единиц времени начнётся сильный дождь.
Петя хотел бы войти в воду напротив одного из буйков, проплыть вдоль буйков вправо и вернуться обратно — то есть выйти из воды там, где он заходил — до начала дождя. При этом мальчик хотел бы проплыть вдоль как можно большего количества различных буйков.
Петя полагает, что он проплыл вдоль некоторого буйка, если оказался в воде строго напротив этого буйка.
Считайте, что Петя проплывает за одну единицу времени одну единицу расстояния между буйками в любом направлении. Буйки расположены близко к берегу, поэтому считайте, что расстояние от берега до буйка и обратно Петя преодолевает мгновенно.
Ваша задача — определить номер буйка, напротив которого Петя войдёт в воду, и номер самого правого буйка, вдоль которого проплывёт Петя.
1 Ответ
Чтобы определить номер буйка, против которого Петя войдет в воду, надо сделать следующие решение:
C++:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n; cin >> n;
—n;
ll t; cin >> t;
ll sum = 0;
int ans = 0;
int bl = 0, br = 0;
vector<int> a(n);
int l = 0, r = 0;
while (r < n) {
cin >> a[r];
a[r] *= 2;
sum += a[r];
++r;
while (sum > t) {
sum -= a[l];
++l;
}
if (ans < r — l) {
ans = r — l;
bl = l;
br = r;
}
}
cout << bl + 1 << » » << br + 1 << «\n»;
}
Python:
n = int(input())
n -= 1
t = int(input())
sum = 0
ans = 0
bl = 0
br = 0
a = [0] * n
l = 0
r = 0
while r < n:
a[r] = int(input())
a[r] *= 2
sum += a[r]
r += 1
while sum > t:
sum -= a[l]
l += 1
if ans < r — l:
ans = r — l
bl = l
br = r
print(bl + 1)
print(br + 1)