Задание 26. Информатика. ЕГЭ. Шастин. 3.6.2025

(Л. Шастин) Исследователь отправляется в экспедицию через пустыню, чтобы добраться до древнего храма, расположенного на расстоянии \(R\) километров от стартовой точки (которая определена первым километром). В начале пути его верблюд полностью отдохнувший и может пройти \(V\) километров без остановки. По пути расположены оазисы, в которых можно напоить верблюда и позволить ему восстановить силы, чтобы снова пройти до \(V\) километров. Известны координаты \(N\) оазисов — километры от начала пути, на которых они расположены, а также запас воды в каждом из них (в у. е). Каждая \(1\) у.е. воды эквивалентна \(1\) километру пути, который может преодолеть верблюд. Определите, какое минимальное количество оазисов придется посетить, чтобы достигнуть древнего храма, а также минимально возможный номер километра расположения оазиса, который получится посетить последний раз.

Входные данные

В первой строке входного файла находится три натуральных числа: \(N\) \((N < 100~000)\) — количество оазисов на пути, \(R\) \((R < 10~000~000)\) — расстояние от стартовой точки до храма, и \(V\) \((V < R)\) — максимальное количество километров, которые может пройти полностью отдохнувший верблюд. В следующих \(N\) строках находятся по два числа: расстояние (в километрах) между стартовой точкой и очередным оазисом, и запас воды в каждом из них (в у. е.). Каждое из чисел целое, не превосходящее \(10~000~000.\)

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

Типовой пример организации данных во входном файле

\(7 \,\, 50 \,\, 20\)
\(10 \,\, 20\)
\(19 \,\, 9\)
\(15 \,\, 11\)
\(40 \,\, 20\)
\(31 \,\, 5\)
\(41 \,\, 10\)
\(30 \,\, 10\)

При таких исходных данных можно сделать \(3\) остановки: \(\{15, \, 30, \, 41\}\) или \(\{15, \, 30, \, 40 \}\) или \(\{10, \, 30, \, 40 \}.\) Ответ: \(3 \,\, 40.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

fd = open('26.txt')
N, R, V = map(int, fd.readline().split())

oasis = [tuple(map(int, line.split())) for line in fd]
oasis.sort()
p = 0
curr = 0
water = V
visited = 0
last_km = 0

while curr + water < R:
    tmp = []
    while p < N and oasis[p][0] - curr <= water:
        next_pos = min(water - (oasis[p][0] - curr) + oasis[p][1], V)
        tmp.append((next_pos, p))
        if oasis[p][0] + next_pos >= R and not last_km:
            last_km = oasis[p][0]
        p += 1
    best = max(tmp)
    p = best[1]
    water = min(water - (oasis[p][0] - curr) + oasis[p][1], V)
    curr = oasis[p][0]
    visited += 1
print(visited, last_km)