27. Программирование – оптимизация по времени и по памяти —Каталог задач по ЕГЭ - Информатика

Главная
Каталог задач
Каталог заданий по ЕГЭ - Информатика
Программирование – оптимизация по времени и по памяти

Тема 27. Программирование – оптимизация по времени и по памяти

27.01 Программирование – оптимизация по времени и по памяти

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела программирование – оптимизация по времени и по памяти

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#61579

Задание выполняется с использованием прилагаемых файлов.

Метеорологическая станция ведёт наблюдение за количеством выпавших осадков. Показания записываются каждую минуту в течении $N$ минут. Определеяется пара измерений, между которыми прошло не менее $K$ минут. Найдите максимальную сумму показаний среди таких пар.

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

Даны два входных файла(A и B), каждый из которых в первой строке содержит число $N$ - количество измерений, а также через пробел число $K$ - минимальное количество минут между искомыми измерениями. В каждой из следующих $N$ строк находится число: количество выпавших осадков.

Пример входных данных:

$6 2$

$10$

$1$

$15$

$30$

$1515$

$3$

Для указанных входных данных ответом будет $1530$ .

В ответе укажите одно число: значение искомой величины для файла А. Файл Б для тех кто хочет проверить свои знания, ответ: 174980.

Вложения к задаче

Zadanie_27a.txt

Zadanie_27B.txt

Показать ответ и решение

def neeff(a, k): # Неэффективный алгоритм
    m = -10**9
    n = len(a)
    for i in range(n):
        for j in range(i + k, n):
            m = max(m, a[i] + a[j])
    return m


def eff(a, k): # Эффективный
    m = -10**9
    n = len(a)
    maxim = -10**20
    for i in range(k - 1, n):
        m = max(m, a[i] + maxim)
        # a[i - (k - 1)] --> свалку
        maxim = max(maxim, a[i - (k - 1)])
    return m

def eff_stat(a, k): # Эффективный статический
    b = []
    m = -10**9
    n = len(a)
    for i in range(n):
        b.append((a[i], i))
    b.sort()
    if len(b) >= 100:
        c = b[-100:]
    else:
        c = b.copy()
    for x in range(len(c)):
        for y in range(x + 1, len(c)):
            if abs(c[x][1] - c[y][1]) >= k:
                m = max(m, c[x][0] + c[y][0])
    return m

f = open(’Задача_27.txt’)
n, k = [int(s) for s in f.readline().split()]
a = [int(s) for s in f]
                                                                                                     
                                                                                                     
print(eff(a, k))

Ответ: 179

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#58618

Дано натуральное число $N$ , затем дана последовательность $N$ натуральных чисел. Найдите непрерывную последовательность с максимальной суммой, в которой количество нечетных элементов кратно $10$ . В качестве ответа выведите сумму данной последовательности.

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно целое число $N (1 ≤ N ≤ 1000000)$ — количество чисел. Каждая из следующих $N$ строк содержит натуральное число, меньшее 10000.

В ответе укажите два числа: сначала значение для файла $A$ , затем для файла $B$ .

Вложения к задаче

27A_2.txt

27B_2.txt

Показать ответ и решение

f = open(’test.txt’)
n = int(f.readline())

s = 0 # Сумма всех чисел
count_nch = 0

min_s = [10000000]*10
min_s[0] = 0

s_max = 0

for i in range(n):
    x = int(f.readline())
    s += x
    count_nch += 1*(x % 2 != 0)

    if s - min_s[count_nch % 10] > s_max:
        s_max = s - min_s[count_nch % 10]

    if s < min_s[count_nch % 10]:
        min_s[count_nch % 10] = s

print(s_max)

Ответ: 103546 5493881388

Ошибка.
Попробуйте повторить позже

Задача 3#58617

Дано натуральное число $N$ , затем дана последовательность $N$ натуральных чисел. Найдите непрерывную последовательность, внутри которой сумма элементов на нечетных позициях равна сумме элементов на четных позициях. В качестве ответа выведите сумму данной последовательности. Если их несколько, то в качестве ответа укажите наибольшую из сумм.

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

В ответе укажите два числа: сначала значение для файла $A$ , затем для файла $B$ .

Вложения к задаче

27A_2.txt

27B_2.txt

Показать ответ и решение

f = open(’27A_2.txt’)
n = int(f.readline())
s_chet = 0
s_nechet = 0
min_ps = [10e20] * 100000000
ans = 0

for i in range(n):
    x = int(f.readline())
    s_chet += x * (i % 2 == 0)
    s_nechet += x * (i % 2 != 0)

    s = s_chet + s_nechet
    l = s_nechet - s_chet

    ans = max(ans, s - min_ps[l])
    min_ps[l] = min(min_ps[l], s)

print(ans)

Ответ: 27716 4569350940

Ошибка.
Попробуйте повторить позже

Задача 4#56890

Дано число $N$ затем $N$ натуральных чисел. Найти количество троек чисел, где элементы будут представлять собой строго возрастающую геометрическую прогрессию. Знаменатель геометрической прогрессии – натуральное число большее $1$ .

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

В первой строке подается натуральное число $1 < N < 100000$ . В каждой строке после записано одно натуральное число, не превышающее $10000$ .

В ответе укажите одно число: значение для файла А.

Файл Б для тех, кто уверен в своих силах. Ответ для него: 75392942

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

n = int(input())

mask = [0] * 10001

for i in range(n):
    mask[int(input())] += 1

ans = 0
for i in range(2, 101):
    for j in range(1, 10000 + 1):
        if j * i * i > 10000:
            break

        if mask[j] * mask[j * i] * mask[j * i * i] > 0:
            ans += mask[j] * mask[j * i] * mask[j * i * i]

print(ans)

Ответ: 1

Ошибка.
Попробуйте повторить позже

Задача 5#56889

Дано число $N$ затем $N$ натуральных чисел. Найдите количество пар чисел, где произведение чисел будет кратно $8$ , но некратно $16$ , а сумма будет иметь остаток $4$ при делении на $10$ .

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

n = int(input())

sv = [[0]*10 for i in range(8+1)]
ans = 0

for i in range(n):
    x = int(input())

    if x % 16 != 0:
        for j in [8, 4, 2, 1]:
            if j * x % 8 == 0 and j * x % 16 != 0:
                for k in range(10):
                    if (k + x) % 10 == 4:
                        ans += sv[j][k]

        for j in [8, 4, 2, 1]:
            if x % j == 0:
                sv[j][x % 10] += 1
                break

print(ans)

Ответ: 1 15769843

Ошибка.
Попробуйте повторить позже

Задача 6#56888

Дано число $N$ , затем $N$ натуральных чисел. Найдите количество пар элементов, где оба элемента будут являться различными числами, при этом хотя бы одно число является полным квадратом.

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

n = int(input())

# Количество полных квадратов
# mask[i] -- количество чисел i
mask = [0]*10001
count = 0 # Общее количество квадратов на данной итерации
ans = 0

for i in range(n):
    x = int(input())
    if x ** 0.5 == int(x ** 0.5):
        # Пары, где оба числа квадраты
        # и пары, где x - квадрат, а другое нет
        ans += count - mask[x] + (i - count)

        mask[x] += 1
        count += 1
    else:
        ans += count

print(ans)

Ответ: 54 78484522

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#56887

Дано число $N$ , затем $N$ натуральных чисел. Найдите количество пар элементов, где оба элемента будут являться различными числами, при этом оба числа являются полными квадратами.

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

n = int(input())

# Количество полных квадратов
# mask[i] -- количество чисел i
mask = [0]*10001
count = 0 # Общее количество квадратов на данной итерации

ans = 0

for i in range(n):
    x = int(input())
    if x**0.5 == int(x**0.5):
        ans += count - mask[x]

        mask[x] += 1
        count += 1

print(ans)

Ответ: 3 1231738

Ошибка.
Попробуйте повторить позже

Задача 8#56484

Крабодел составил список точек плоскости с целочисленными координатами, среди которых имеется хотя бы одна, не лежащая на осях координат. Крабоеду необходимо найти количество отрезков, удовлетворяющих следующим условиям:

1) оба конца отрезка принадлежат заданному множеству;

2) ни один конец отрезка не лежит на осях координат;

3) отрезок пересекается с обеими осями координат.

Описание входных данных

В первой строке задаётся $N$ — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа $x$ и $y$ — координаты очередной точки. Гарантируется, что $1 ≤ N ≤ 10000$ , $− 1000 ≤ x ≤ y ≤ 1000$ .

Описание выходных данных

Необходимо вывести количество удовлетворяющих требованиям отрезков.

Пример входных данных:

$4$

$6$ $6$

- $8$ $8$

- $9$ - $9$

$7$ - $5$

Пример выходных данных для приведённого выше примера входных данных:

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

Для того, чтобы отрезок, концы которого не лежат на осях координат пересекался и с $Oy$ , и с $Ox$ , необходимо, чтобы его концы лежали в противоположных четвертях. Тогда подсчитаем количество точек в каждой четверти, а затем перемножим их и сложим $k ∗k + k ∗ k 1 3 2 4$ , где индексы при $k$ — номера четвертей.

f = open(’27A.txt’)
k1, k2, k3, k4 = 0, 0, 0, 0
n = int(f.readline())

for i in range(n):
    x, y = map(int, f.readline().split())
    if x > 0 and y > 0:
        k1 += 1
    if x < 0 and y > 0:
        k2 += 1
    if x < 0 and y < 0:
        k3 += 1
    if x > 0 and y < 0:
        k4 += 1

print(k1*k3 + k2*k4)

Ответ: 42 1247171763

Ошибка.
Попробуйте повторить позже

Задача 9#56328

Задание выполняется с использованием прилагаемых файлов

Последовательность натуральных чисел характеризуется числом X, равным длине цепочки, сумма чисел которой максимальна и делится на $21$ . Найдите разность суммы и X. Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если существует несколько подпоследовательностей с равной максимальной суммой, нужно выбрать последовательность, которая заканчивается раньше, т.е. последний элемент имеет меньший индекс.

Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

В ответ укажите числа для файла A и для файла B через пробел.

Вложения к задаче

27a.txt

27b.txt

Показать ответ и решение

f = open(’27a.txt’)
n = int(f.readline())
mins = [0] + [1000000000] * 20
ind = [-1] + [-100] * 20
maxim, summ = 0, 0
for i in range(n):
    x = int(f.readline())
    summ += x
    ost = summ % 21
    if summ - mins[ost] > maxim:
        maxim = summ - mins[ost]
        dlina = i - ind[ost]
    if summ < mins[ost]:
        mins[ost] = summ
        ind[ost] = i
print(maxim - dlina)

Ответ: 4779 562665721

Ошибка.
Попробуйте повторить позже

Задача 10#55508

Дано число $N,$ затем $N$ натуральных чисел. Рассматриваются все пары элементов последовательности, разность которых четна, и в этих парах, по крайней мере, одно из чисел делится на $17$ .

Среди всех таких пар найдите пару с максимальной суммой элементов и выведите элементы пары в порядке возрастания их числовых значений.

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

Вложения к задаче

27B.txt

27A.txt

Показать ответ и решение

# первый элемент массивов -- чет
# второй -- нечет
kr17 = [0, 0]
nekr = [0, 0]

n = int(input())
ans = [0]

for i in range(n):
    x = int(input())
    if x % 17 == 0:
        if x + kr17[x % 2] > sum(ans):
            ans = [x, kr17[x % 2]]
        if x + nekr[x % 2] > sum(ans):
            ans = [x, nekr[x % 2]]

        kr17[x % 2] = max(kr17[x % 2], x)
    else:
        if x + kr17[x % 2] > sum(ans):
            ans = [x, kr17[x % 2]]
        nekr[x % 2] = max(nekr[x % 2], x)

print(ans)

Ответ: 3077 8759 9996 10000

Ошибка.
Попробуйте повторить позже

Задача 11#55473

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

Входные данные: В первой строке входного файла вводится одно число $N$ (натуральное число, не превышающее $100$ ) — количество ступенек. В следующей строке вводятся $N$ натуральных чисел, не превосходящих $100$ — стоимость каждой ступеньки (снизу вверх).

Выходные данные: Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Выведите ответ для следующих чисел:

$4$

$1$ $2$ $10$ $2$

Показать ответ и решение

Жадный алгоритм на каждом шагу принимает локальное оптимальное решение, не заботясь о том, что будет дальше. Разберём, почему в данной задаче жадный алгоритм не сработает. Изначально у него есть два варианта: сходить на ступеньку с числом $1$ или с числом $2$ — и пойдет на ступеньку с числом $1$ , т.к. это дешевле. Но правильное решение здесь — пойти на ступеньку с числом $2$ , потом мы сможем перепрыгнуть ступеньку с числом $10$ .

Решим задачку ручками: $2$ + $2$ = $4$ , а ступеньки с числами $1$ и $10$ мы перепрыгнули.

Ответ: 4

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#55469

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.

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

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

В первой строке входного файла находятся два числа: $S$ — размер свободного места на диске (натуральное число, не превышающее $100$ ) и $N$ — количество пользователей (натуральное число, не превышающее $100$ ). В следующих $N$ строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие $10$ ), каждое в отдельной строке.

Запишите в ответе максимальное количество файлов, которые удастся сохранить в архив.

Запишите ответ для следующих входных данных:

$10 5$

$1$

$2$

$3$

$8$

Показать ответ и решение

Обычный жадный алгоритм здесь не сработает, поскольку нам необходимо заполнить весь архив. Решим задачу ручками: число $10$ получится набрать, только если взять файлы размером $2$ и $8$ . Значит, всего удастся сохранить $2$ пользовательских файла.

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 13#54787

Андрей едет из пункта $A$ в пункт $B$ на автомобиле. Расстояние между этими пунктами равно $N$ километров. Известно, что с полным баком автомобиль способен проехать $k$ километров. Дана карта, на которой отмечены координаты бензоколонок, относительно пункта $A$ . Определите минимальное число заправок, которые придется сделать Андрею чтобы успешно достичь пункта $B$ . Известно, что при выезде из пункта $A$ бак был полон.

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

В первой строке вводятся числа $N$ и $k$ (натуральные, не превосходят $1000$ ). В следующей строке вводится количество бензоколонок $S$ , потом следует $S$ натуральных чисел, не превосходящих $N$ — расстояния от пункта $A$ до каждой заправки. Заправки упорядочены по удаленности от пункта $A$ .

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

Если при данных условиях пункта $B$ достичь невозможно, то вывести число $− 1$ . Если решение существует, то вывести минимальное количество остановок на дозаправку, которое нужно, чтобы достичь пункта $B$ .

Вложения к задаче

input.txt

Показать ответ и решение

f = open("input.txt")

n, k = [int(i) for i in f.readline().split()]
s = int(f.readline())

# список координат каждой заправки
d = [int(i) for i in f.readlines()]

# добавляем в список координат координату точки B
# это нужно для того, чтобы мы могли проверить,
# можно ли доехать с последней заправки до точки B без дозаправки или нет
d.append(n)

current_fuel = k  # текущая наполненность бака
current_dist = 0  # пройденное расстояние
ans = 0  # ответ
possible = True  # флаг, указывающий то, смогли ли мы доехать до пункта B
coords = []
for i in range(s+1):
    # проверка того, что мы не сможем проехать до следующей
    # заправки и нам нужно заправиться
    if d[i] - current_dist > current_fuel:
        # проверка того, что мы можем заправиться (в пункте A заправок нет)
        # и проверка того, что мы после заправки сможем доехать до следующей заправки
        if current_dist != 0 and k >= d[i] - current_dist:
            current_fuel = k - (d[i] - current_dist)
            ans += 1
            coords.append(current_dist)
        else:
            possible = False
            break
    # если мы смогли доехать до следующей заправки без дозаправки,
    # то необходимо уменьшить кол-во топлива в баке
    else:
        current_fuel -= (d[i] - current_dist)
    current_dist = d[i]

if possible:
    print(ans)
                                                                                                     
                                                                                                     
else:
    print(-1)

Ответ: 31

Ошибка.
Попробуйте повторить позже

Задача 14#54786

В этой задаче Вася готовится к олимпиаде. Учитель дал ему $N$ ( $1 ≤ N ≤ 100$ ) задач для тренировки. Для каждой из этих задач известно, каким умением $ai$ нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения $i$ -й задачи умение Васи увеличивается на число $bi$ .

Исходное умение Васи равно $A$ . Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

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

Сначала вводятся два целых числа $N$ , $A$ ( $1 ≤ N ≤ 100,0 ≤ A ≤ 100$ ) — количество задач и исходное умение. Далее идут N пар целых чисел $ai$ , $bi$ ( $1 ≤ ai ≤ 100,0 ≤ bi ≤ 3$ ) — соответственно сколько умения нужно для решения $i$ -й задачи и сколько умения прибавится после её решения.

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

Выведите одно число — максимальное количество задач, которое Вася может решить.

Вложения к задаче

test.txt

Показать ответ и решение


f = open("test.txt")

n, a = [int(i) for i in f.readline().split()]

tasks = []
for _ in range(n):
    x, y = [int(i) for i in f.readline().split()]
    tasks.append([x, -y])
tasks.sort()


ans = 0
for i in range(n):
    x, y = tasks[i][0], -tasks[i][1]
    if x <= a:
        ans += 1
        a += y

print(ans)

Ответ: 29

Ошибка.
Попробуйте повторить позже

Задача 15#54783

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

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

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

Сначала вводится число $S$ — размер свободного места на диске (натуральное, не превышает $10000$ ), затем следует число $N$ — количество пользователей (натуральное, не превышает $100$ ), после этого идет $N$ чисел — объем данных каждого пользователя (натуральное, не превышает $1000$ ).

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

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

Вложения к задаче

task_1__t54z.txt

Показать ответ и решение


f = open("task_1.txt")

s, n = [int(x) for x in f.readline().split()]

data = [int(x) for x in f.readlines()]
data.sort()

ans = 0
for i in range(len(data)):
    if s - data[i] >= 0:
        ans += 1
        s -= data[i]
    else:
        break

print(ans)

Ответ: 2610

Ошибка.
Попробуйте повторить позже

Задача 16#54406

Вам известны координаты начал и концов $n$ отрезков, расположенных на числовой прямой. Сколько существует непересекающихся промежутков, покрытых ровно одним отрезком из данных Вам?

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

В первой строке входных данных содержится единственное число $n$ $5 (1 ≤ n ≤ 10 )$ .

Далее в $n$ строках записано по два числа $a$ и $b$ , описывающие отрезки: начало и конец отрезка $(1 ≤ a ≤ b ≤ 109)$ .

Выведите единственное число — количество непересекающихся промежутков, покрытых ровно одним отрезком.

Пример входных данных:

$3$

$1$ $9$

$3$ $4$

$7$ $8$

Пояснение к примеру:

Промежутки $[1,3)$ , $(4,7)$ и $(8,9]$ покрыты ровно одним отрезком. Ответ на данный пример — $3$ .

Вложения к задаче

file.txt

Показать ответ и решение

f = open("file.txt")
n = int(f.readline())
segments = []
for i in range(n):
    a, b = map(int, f.readline().split())
    segments.append((a, 0))
    segments.append((b, 1))

segments.sort()
ans = 0
cur = 0
for i in range(2 * n):
    a, b = segments[i]
    if (b == 0):
        cur += 1
    else:
        cur -= 1
    if (cur == 1):
        ans += 1
print(ans)

Ответ: 3

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#54386

Вам известны времена прихода и ухода каждого из $n$ посетителей ресторана. Какое максимальное количество человек посетило ресторан в какой-либо момент времени?

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

Первая строка входных данных содержит единственное число $n$ $5 (1 ≤ n ≤ 10 )$ .

Далее следуют $n$ строк, описывающие клиентов. Каждая строка содержит два числа $a$ и $b$ : времена прихода и ухода каждого клиента $(1 ≤ a ≤ b ≤ 109)$ .

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

Выведите одно число — максимальное число клиентов в какой-либо момент времени.

Пример входных данных:

$3$

$5$ $8$

$2$ $4$

$3$ $9$

Пояснение к примеру:

Например, в момент времени $7$ в ресторане присутствовали первый и третий клиент. Ответ на данный пример — $2$ .

Вложения к задаче

file.txt

Показать ответ и решение

f = open("file.txt")
n = int(f.readline())
customer = []
for i in range(n):
    a, b = map(int, f.readline().split())
    customer.append((a, 0))
    customer.append((b, 1))

customer.sort()
ans = 0
cur = 0
for i in range(2 * n):
    a, b = customer[i]
    if (b == 0):
        cur += 1
    else:
        cur -= 1
    ans = max(ans, cur)
print(ans)

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 18#54384

На фестивале фильмов будет показано $n$ фильмов. Вам известно время начала и конца каждого фильма. Какое максимальное количество фильмов Вы можете посмотреть полностью?

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

В первой строке входных данных записано число $n$ $5 (1 ≤ n ≤ 10 )$ .

Далее заданы $n$ строк, описывающие фильмы. Каждая строка содержит два числа $a$ и $b$ : времена начала и конца фильма $(1 ≤ a ≤ b ≤ 109)$ .

Выведите одно число: максимальное число фильмов, которые сможете посмотреть полностью.

Пример входных данных:

$3$

$3$ $5$

$4$ $9$

$5$ $8$

Пояснение к примеру:

Вы можете посмотреть первый и третий фильмы полностью. Ответ на данный тестовый пример — $2$ .

Вложения к задаче

file.txt

Показать ответ и решение

f = open("file.txt")
n = int(f.readline())
movie = []
for i in range(n):
    a, b = map(int, f.readline().split())
    movie.append((b, a))

movie.sort()
ans, cur = 1, movie[0][0]

for i in range(1, n):
    if (movie[i][1] >= cur):
        cur = movie[i][0]
        ans += 1
print(ans)

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 19#48261

На вход подается натуральное число $N,$ затем $N$ натуральных чисел в порядке неубывания. Определите, сколько раз встречается число $722$ . В качестве ответа укажите количество чисел $722$ в последовательности.

Вложения к задаче

test.txt

Показать ответ и решение

def binary_search_recursive(arr, elem, start=0, end=None):
    if end is None:
        end = len(arr) - 1
    if start > end:
        return False

    mid = (start + end) // 2
    if elem == arr[mid]:
        return mid
    if elem < arr[mid]:
        return binary_search_recursive(arr, elem, start, mid-1)

    return binary_search_recursive(arr, elem, mid+1, end)

def count_nums(arr, x):
    ind = binary_search_recursive(arr, x)

    if ind == -1:
        return 0

    count = 1
    left = ind - 1
    while left >= 0 and arr[left] == x:
        count += 1
        left -= 1

    right = ind + 1
    while right < len(arr) and arr[right] == x:
        count += 1
        right += 1

    return count

f = open(’test.txt’)
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]

print(count_nums(a, 722))

Ответ: 128

Ошибка.
Попробуйте повторить позже

Задача 20#48260

На вход подается натуральное число $N,$ затем $N$ натуральных чисел в порядке неубывания. Определите, на каком месте впервые встречается число $34$ . В качестве ответа укажите индекс данного числа в массиве, индексация начинается с $0$ .

Вложения к задаче

test.txt

Показать ответ и решение

def binary_search_recursive(arr, elem, start=0, end=None):
    if end is None:
        end = len(arr) - 1
    if start > end:
        return False

    mid = (start + end) // 2
    if elem <= arr[mid]:
        return binary_search_recursive(arr, elem, start, mid-1)

    if elem == arr[mid + 1]:
        return mid + 1


    return binary_search_recursive(arr, elem, mid+1, end)

f = open(’test.txt’)
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]

print(binary_search_recursive(a, 34))

Ответ: 25

Предыдущий раздел

Следующий раздел