Прочие прототипы —Каталог задач по ЕГЭ - Информатика

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

Задача 1#56484

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

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

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

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

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

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

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

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

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

$4$

$6$ $6$

- $8$ $8$

- $9$ - $9$

$7$ - $5$

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

2

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

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

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

Задача 2#55473

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

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

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

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

$4$

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

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

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

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

Ответ: 4

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

Задача 3#55469

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

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

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

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

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

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

$10 5$

$1$

$2$

$3$

$8$

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

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

Ответ: 2

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

Задача 4#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

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

Задача 5#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

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

Задача 6#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

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

Задача 7#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

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

Задача 8#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

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

Задача 9#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

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

Задача 10#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

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

Задача 11#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

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

Задача 12#48233

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

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

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)

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

print(binary_search_recursive(a, 8305))

Ответ: YES

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

Задача 13#47009

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

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

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $20$ .

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

27A.txt

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

f = open(’27A.txt’)

n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
k = 1000
ans = 0

for i in range(1, 2**n):
    t = i
    s = 0
    for j in range(n):
        if t % 2 == 1:
            s += a[j]
        t //= 2

    if s % k == 0:
        ans += 1

print(ans)

Ответ: 1125

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

Задача 14#47008

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

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

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $20$ .

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

27A.txt

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

f = open(’27A.txt’)

n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
k = 128
ans = 0

for i in range(1, 2**n):
    t = i
    s = 0
    for j in range(n):
        if t % 2 == 1:
            s += a[j]
        t //= 2

    if s % k == 0:
        ans += 1

print(ans)

Ответ: 8195

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

Задача 15#47007

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

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

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $20$ .

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

27a.txt

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

f = open(’27A.txt’)

n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
k = 100
ans = 0

for i in range(1, 2**n):
    t = i
    s = 0
    for j in range(n):
        if t % 2 == 1:
            s += a[j]
        t //= 2

    if s % k == 0:
        ans += 1

print(ans)

Ответ: 10476

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

Задача 16#47006

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

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

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $20$ .

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

27A.txt

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

f = open(’27A.txt’)

n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
k = 30
ans = 0

for i in range(1, 2**n):
    t = i
    s = 0
    for j in range(n):
        if t % 2 == 1:
            s += a[j]
        t //= 2

    if s % k == 0:
        ans += 1

print(ans)

Ответ: 35275

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

Задача 17#47005

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

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

Первая строка входного файла содержит число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит натуральное число, не превышающее $10000$ .

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

27A.txt

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

f = open(’27A.txt’)

n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
k = 10
ans = 0

for i in range(1, 2**n):
    t = i
    s = 0
    for j in range(n):
        if t % 2 == 1:
            s += a[j]
        t //= 2

    if s % k == 0:
        ans += 1

print(ans)

Ответ: 104863

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

Задача 18#47004

Найдите максимальное значение функции с точностью до $10− 3$ при следующих условиях $f(x) = 6x2 − 240x + 3600 → x∈m[a0x,30]$

В качестве ответа укажите найденное число, округлив до большего.

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

def fun(x):
    return 6*x**2-240*x+3600

def bin_search():
    eps = 0.001
    left = 0
    right = 30
    while abs(right - left) > eps:
        middle = (left + right) / 2

        if fun(middle) < 0:
            left = middle
        else:
            right = middle

    return int(fun(right) + 1)

print(bin_search())

Ответ: 3600

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

Задача 19#47003

Найдите решение следующего уравнения с точностью до $10−4$ :

x2 = 9999800001

В качестве ответа укажите положительный корень уравнения с точностью до $10−4$ , дробную часть укажите через точку (т.е. так: $10.2563$ ).

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

def fun(x):
    return x**2

def bin_search(c):
    eps = 0.001
    left = 0
    right = 10**15
    while abs(right - left) > eps:
        middle = (left + right) / 2

        if fun(middle) - c < 0:
            left = middle
        else:
            right = middle

    return right

print(bin_search(99999**2))

Ответ: 99999.0004

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

Задача 20#47002

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

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

test.txt

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

def bin_search(a, x):
    n = len(a)
    left = -1
    right = n
    while right - left > 1:
        middle = (left + right) // 2

        if x == a[middle]:
            left = middle

        elif a[middle] >= x:
            right = middle

        else:
            left = middle

    if left != n and a[left] == x:
        return left
    else:
        return -1

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

print(bin_search(a, 82))

Ответ: 196