Петя любит плавать в реке. Место, доступное для плавания, ограничено буйками. Плавать левее первого буйка и правее последнего буйка запрещено. Линия, вдоль которой расположены N буйков, проходит параллельно берегу.

Question

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

Будем считать, что буйки пронумерованы числами от 1 до N слева направо. Известны расстояния S1, S2, … SN-1, где Sj — расстояние от буйка j до буйка (j + 1).

В хорошую погоду Петя входит в воду напротив первого буйка, очень быстро доплывает до него, а затем несколько раз плавает до последнего буйка и обратно. После этого он возвращается от первого буйка к берегу. Но сегодня так не получится: по прогнозу погоды через Т единиц времени начнётся сильный дождь.

Петя хотел бы войти в воду напротив одного из буйков, проплыть вдоль буйков вправо и вернуться обратно — то есть выйти из воды там, где он заходил — до начала дождя. При этом мальчик хотел бы проплыть вдоль как можно большего количества различных буйков.

Петя полагает, что он проплыл вдоль некоторого буйка, если оказался в воде строго напротив этого буйка.

Считайте, что Петя проплывает за одну единицу времени одну единицу расстояния между буйками в любом направлении. Буйки расположены близко к берегу, поэтому считайте, что расстояние от берега до буйка и обратно Петя преодолевает мгновенно.

Ваша задача — определить номер буйка, напротив которого Петя войдёт в воду, и номер самого правого буйка, вдоль которого проплывёт Петя.

Ответ

Answer 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 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)