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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@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