Нужно понять как задачу на два указателя

@Hochmuch · Регистрация: 05.07.2019

Студворк — интернет-сервис помощи студентам

В 2029 году три финала Всероссийской олимпиады — по химии, информатике и физкультуре — проводятся в Самаре. Из Саратова прошло много участников по каждому из этих предметов, и все они планируют ехать в Самару на поезде. Руководитель сборной по химии уже купил билеты для своих подопечных. Руководитель сборной по информатике как раз сейчас планирует этим заняться. Но программисты — странные люди, у которых есть много запросов к купленным местам. Например, они категорически не хотят ехать в одном вагоне со спортсменами (участниками сборной по физкультуре), а также со всеми другими людьми, не прошедшими на всерос (то есть, из всех возможных людей, они готовы терпеть только всероссников по химии).

К счастью, пока кроме химиков ещё никто не успел купить билеты на поезд, так что всё, что нужно обеспечить руководителю, это чтобы после покупки билетов, в вагонах, в которых поедут участники сборной по информатике не осталось свободных мест (тогда там точно не поедут посторонние).

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

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

Входные данные
В первой строке дано два целых числа n и k (1≤n≤105,1≤k≤109) — число вагонов и участников сборной соответственно.

Во второй строке даны n целых чисел ai (0≤ai≤109) — количество свободных мест в вагонах.

Гарантируется, что суммарное число свободных мест в поезде не превосходит 109.

Выходные данные
Выведите два целых числа — номера первого и последнего вагона, в которых поедут участники сборной.

Если же купить билеты, соблюдя все требования, невозможно, выведите -1.
Вот мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
n, k = map(int, input().split())
train = [int(q) for q in input().split()]
res = []
i = 0
j = 0
s = train[0]
go = True
while go:
    if train[i] == 0:
        if i + 1 < n:
            i += 1
        else:
            go = False
    if s == k:
        res.append([i + 1, j + 1])
        if j + 1 < n:
            j += 1
            s += train[j]
        else:
            go = False
    elif s < k:
        if j + 1 < n:
            j += 1
            s += train[j]
        else:
            go = False
    else:
        s -= train[i]
        i += 1
minimum = 99999999999999999999999999999999999999999999999999999999999999999999
r1, r2 = -1, -1
for g in res:
    if g[1] - g[0] < minimum:
        r1, r2 = g[0], g[1]
        minimum = r2 - r1
if r1 == -1:
    print(-1)
else:
    print(r1, r2)

@eaa · 24.07.2020, 14:42

в чем вопрос?

@Hochmuch · 24.07.2020, 14:58 **[ТС]**

Вопрос в том, как решить эту задачу, так как этот код проходит не все тесты. Ссылка на задачу - https://codeforces.com/gym/102330/problem/B

@Skybi · 02.09.2020, 19:04

Вы смогли решить? Если да, в чем была ваша проблема? А то у меня тоже падает решение на последнем тесте...

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.07.2020, 14:42
	в чем вопрос? 0

@Hochmuch 0 / 0 / 0 Регистрация: 05.07.2019 Сообщений: 14
	24.07.2020, 14:58 [ТС]
	Вопрос в том, как решить эту задачу, так как этот код проходит не все тесты. Ссылка на задачу - https://codeforces.com/gym/102330/problem/B 0

@Skybi 2 / 2 / 0 Регистрация: 28.09.2018 Сообщений: 18
	02.09.2020, 19:04
	Вы смогли решить? Если да, в чем была ваша проблема? А то у меня тоже падает решение на последнем тесте... 0