Информатика: банк заданий
139 тренировочных задач. Фильтруй по линии КИМ прямо в списке — номер линии указан на карточке.
Кратчайший путь по дорогам
Между пунктами A, B, C, D, E и F проложены двусторонние дороги. Длины дорог (в километрах): A–B: 4, A–C: 2, B–C: 1, B–D: 5, C–D: 8, C–E: 10, D–E: 2, D–F: 6, E–F: 3. Определите длину кратчайшего пути из пункта A в пункт F (по заданным дорогам).
Количество единиц в таблице истинности
Логическая функция $F$ задана выражением $F = (x \wedge \neg y) \vee (y \equiv z)$. Сколько среди всех возможных наборов значений переменных $x, y, z$ таких, при которых $F = 1$?
Восстановление порядка столбцов таблицы истинности
Логическая функция $F$ задаётся выражением $F = (x \wedge y) \vee (\neg x \wedge z)$. Дан фрагмент таблицы истинности, в котором столбцы с переменными $x, y, z$ расположены в неизвестном порядке и обозначены как «Пер. 1», «Пер. 2», «Пер. 3»: | Пер. 1 | Пер. 2 | Пер. 3 | $F$ | |---|---|---|---| | 0 | 1 | 0 | 0 | | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 1 | | 1 | 1 | 0 | 0 | Определите, какому столбцу соответствует каждая из переменных. В ответе запишите буквы переменных (строчные латинские) в порядке столбцов «Пер. 1», «Пер. 2», «Пер. 3» без пробелов (например, xyz).
Условие Фано
Для кодирования букв А, Б, В, Г и Д используется неравномерный двоичный код, удовлетворяющий условию Фано (ни одно кодовое слово не является началом другого). Известно, что А — 0, Б — 100, В — 101. Какова наименьшая возможная суммарная длина кодовых слов для букв Г и Д?
Автомат с битом чётности
Автомат получает на вход натуральное число $N$ и строит новое число $R$ по следующим правилам. 1. Строится двоичная запись числа $N$. 2. Справа дописывается бит чётности: 0, если в записи чётное число единиц, и 1, если нечётное. 3. Над полученной записью повторяется действие пункта 2. Полученная запись — двоичная запись числа $R$. Укажите наименьшее число $N$, для которого результат $R$ больше 150.
Цикл со знакопеременной суммой
Определите, что будет напечатано в результате выполнения программы. ```python s = 0 for i in range(1, 8): if i % 2 == 0: s += i * i else: s -= i print(s) ```
Цикл while и целочисленное деление
Определите, что будет напечатано в результате выполнения программы. ```python n = 1000 k = 0 while n > 10: n = n // 3 k += 1 print(n + k) ```
Размер растрового изображения
Несжатое растровое изображение имеет размер $1024 \times 768$ пикселей. Для кодирования цвета каждого пикселя используется палитра из 65 536 цветов. Сколько Кбайт (1 Кбайт = 1024 байт) занимает это изображение в памяти?
Размер звукового файла
Производится двухканальная (стерео) звукозапись с частотой дискретизации 16 000 Гц и глубиной кодирования 16 бит. Запись длится 1 минуту, сжатие не используется. Сколько Кбайт занимает полученный файл (1 Кбайт = 1024 байт)?
Слова с одной определённой буквой
Сколько существует различных четырёхбуквенных слов (не обязательно осмысленных), составленных из букв А, Б, В, Г, в которых буква Б встречается ровно один раз?
Хранение паролей
Пароль состоит из 10 символов. В качестве символов используются 26 заглавных латинских букв и 10 цифр. В базе данных каждый пароль кодируется минимально возможным одинаковым целым числом бит на символ, а весь пароль занимает минимально возможное целое число байт. Кроме пароля, для каждого пользователя хранится ещё 3 байта дополнительных сведений. Сколько байт нужно для хранения данных о 40 пользователях?
Редактор с заменой подстрок
Исполнитель Редактор получает на вход строку цифр и выполняет программу. Команда `заменить (v, w)` заменяет в строке первое (слева) вхождение цепочки `v` на цепочку `w`. ``` НАЧАЛО ПОКА нашлось (12) ИЛИ нашлось (222) ЕСЛИ нашлось (12) ТО заменить (12, 2) ИНАЧЕ заменить (222, 1) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ ``` На вход подана строка 1112222 (три единицы и четыре двойки). Чему равна сумма цифр строки, полученной после выполнения программы?
Адрес сети по маске
Узел с IP-адресом 192.168.77.130 принадлежит сети с маской 255.255.255.192. Чему равно число, стоящее в последнем (четвёртом) байте адреса этой сети?
Число узлов в сети
Сеть задана маской 255.255.240.0. Сколько различных IP-адресов в этой сети можно назначить узлам, если два адреса — адрес сети и широковещательный адрес — использовать нельзя?
Единицы в двоичной записи значения выражения
Значение арифметического выражения $4^9 + 2^{12} - 8$ записали в двоичной системе счисления. Сколько цифр «1» содержит эта запись?
Определение основания системы счисления
Запись числа 83 в системе счисления с основанием $x$ равна $123_x$. Найдите $x$.
Отрезки и тождественная истинность
На числовой прямой заданы отрезки $P = [10;\,30]$ и $Q = [20;\,50]$. Выберите такой отрезок $A$ наименьшей возможной длины, чтобы формула $(x \in P) \rightarrow ((x \in Q) \vee (x \in A))$ была тождественно истинна (то есть принимала значение 1 при любом $x$). Чему равна длина отрезка $A$?
Поразрядная конъюнкция и параметр A
Через $x \,\&\, y$ обозначается поразрядная конъюнкция неотрицательных целых чисел. Для какого наименьшего натурального числа $A$ выражение $(x \,\&\, 14 \neq 0) \rightarrow \big((x \,\&\, 56 = 0) \rightarrow (x \,\&\, A \neq 0)\big)$ тождественно истинно (то есть принимает значение 1 при любом неотрицательном целом $x$)?
Рекурсивная функция
Алгоритм вычисления значения функции $F(n)$ задан следующими соотношениями: ```python def F(n): if n <= 2: return 1 return F(n - 1) + 2 * F(n - 2) ``` Чему равно значение $F(9)$?
Пары соседних элементов
Дана последовательность из 12 натуральных чисел: 14, 27, 33, 8, 41, 19, 25, 36, 7, 50, 22, 31. Найдите количество пар соседних элементов последовательности, в которых сумма элементов кратна 3 и хотя бы один из элементов пары чётный.
Игра с кучей камней: выигрыш Вани первым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может либо добавить в кучу 3 камня, либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 50 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 49$. Укажите наибольшее значение $S$, при котором Петя не может выиграть первым ходом, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Числа с шестью делителями
Сколько существует натуральных чисел от 1 до 100 включительно, имеющих ровно 6 натуральных делителей (включая 1 и само число)?
Погрузка коробок в грузовик
На складе лежат 8 коробок массой 7, 12, 5, 9, 14, 3, 11 и 6 кг. В грузовик можно погрузить коробки общей массой не более 32 кг. Сначала определите, какое наибольшее количество коробок можно погрузить. Затем из всех вариантов погрузки такого количества коробок выберите тот, в котором суммарная масса максимальна (но не превышает 32 кг). Чему равна эта суммарная масса (в килограммах)?
Соответствие таблицы и схемы дорог
Между шестью населёнными пунктами построены дороги. Схема дорог (без указания длин) задана перечнем рёбер: A–B, D–F, D–E, A–F, B–D, B–F, A–C, B–C. В таблице указаны длины дорог между пунктами П1–П6 (в километрах); знак «–» означает, что прямой дороги между пунктами нет. Нумерация пунктов в таблице никак не связана с буквенными обозначениями на схеме. | П1 | П2 | П3 | П4 | П5 | П6 П1 | – | 4 | 9 | 6 | 11 | – П2 | 4 | – | 12 | – | – | 10 П3 | 9 | 12 | – | – | 2 | – П4 | 6 | – | – | – | 7 | – П5 | 11 | – | 2 | 7 | – | – П6 | – | 10 | – | – | – | – Определите длину дороги между пунктами A и F. В ответе запишите целое число — длину дороги в километрах.
Кратчайший путь по таблице дорог
Между пунктами A, B, C, D, E, F и G построены двусторонние дороги. Длины дорог (в километрах) заданы перечнем: D–F: 3, D–E: 8, C–E: 11, B–C: 7, A–E: 10, C–F: 10, A–B: 12, C–G: 4, B–F: 13, B–D: 9, A–F: 11, A–D: 10. Других дорог нет. Найдите длину кратчайшего пути из пункта A в пункт G.
Соответствие схемы и таблицы дорог: длина дороги
Между семью населёнными пунктами построены дороги. Схема дорог (без указания длин) задана списком: A–B, A–C, B–D, B–E, C–F, B–G, C–G, B–C, A–F, D–F. В таблице указаны длины дорог в километрах между пунктами, пронумерованными числами от 1 до 7 (прочерк означает, что прямой дороги нет). Нумерация в таблице никак не связана с буквенными обозначениями на схеме. | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | --- | --- | --- | --- | --- | --- | --- | | 1 | – | – | – | – | – | – | 4 | | 2 | – | – | 8 | – | – | – | 3 | | 3 | – | 8 | – | 8 | 8 | – | 13 | | 4 | – | – | 8 | – | 12 | – | 14 | | 5 | – | – | 8 | 12 | – | 12 | – | | 6 | – | – | – | – | 12 | – | 8 | | 7 | 4 | 3 | 13 | 14 | – | 8 | – | Определите длину дороги между пунктами B и E. В ответе запишите целое число.
Кратчайший путь через обязательный пункт
Между пунктами A, B, C, D, E, F, G и H проложены двусторонние дороги. Длины дорог (в километрах): A–B: 3, A–C: 5, B–C: 2, B–D: 6, C–D: 7, C–E: 4, D–E: 3, D–F: 5, E–F: 8, E–G: 6, F–G: 2, F–H: 7, G–H: 3. Определите длину кратчайшего пути из пункта A в пункт H, который проходит через пункт D.
Таблица истинности с четырьмя переменными
Логическая функция F задаётся выражением (x → y) ∧ (y → z) ∧ (z → w). Ниже приведён фрагмент таблицы истинности функции F; столбцы с переменными x, y, z, w расположены в неизвестном порядке и обозначены «Пер. 1» – «Пер. 4». Пер. 1 | Пер. 2 | Пер. 3 | Пер. 4 | F 0 | 1 | 0 | 0 | 1 1 | 1 | 0 | 0 | 0 1 | 1 | 1 | 0 | 1 0 | 1 | 0 | 1 | 0 Определите, какому столбцу соответствует каждая переменная. В ответе запишите буквы переменных в порядке столбцов «Пер. 1», «Пер. 2», «Пер. 3», «Пер. 4» без пробелов (например, xyzw).
Таблица истинности: четыре переменные и неизвестный порядок
Логическая функция $F$ задаётся выражением $F = ((x \to y) \wedge (z \equiv w)) \vee (\neg y \wedge w)$. Дан фрагмент таблицы истинности, в котором столбцы с переменными $x, y, z, w$ расположены в неизвестном порядке и обозначены «Пер. 1» … «Пер. 4»: | Пер. 1 | Пер. 2 | Пер. 3 | Пер. 4 | $F$ | | --- | --- | --- | --- | --- | | 0 | 1 | 1 | 0 | 0 | | 1 | 1 | 0 | 1 | 1 | | 0 | 0 | 1 | 0 | 1 | | 1 | 0 | 0 | 0 | 1 | Определите, какому столбцу соответствует каждая из переменных. В ответе запишите буквы переменных (строчные латинские) в порядке столбцов «Пер. 1» … «Пер. 4» без пробелов (например, xyzw).
Количество наборов, на которых функция истинна
Логическая функция $F$ задана выражением $F = ((x \to y) \wedge (y \to z)) \vee (w \wedge \neg z)$. Сколько существует наборов значений переменных $x, y, z, w$, на которых $F = 1$?
Сколько килограммов сахара продано
В магазинной сети ведутся три связанные таблицы. Таблица «Товар» (в упаковке — количество единиц товара в одной упаковке): Артикул | Отдел | Наименование | Ед. | В упаковке | Поставщик 101 | Бакалея | Сахар-песок | кг | 5 | Сладкая жизнь 102 | Бакалея | Сахар тростниковый | кг | 2 | Колониал 103 | Бакалея | Мука пшеничная | кг | 10 | Зерно 104 | Молочные продукты | Молоко 3,2% | л | 6 | Нива 105 | Бакалея | Сахар-рафинад | кг | 1 | Сладкая жизнь 106 | Бакалея | Гречка | кг | 3 | Зерно Таблица «Магазин»: ID | Район | Адрес М1 | Центральный | ул. Ленина, 10 М2 | Заречный | ул. Мира, 5 М3 | Центральный | ул. Гагарина, 22 М4 | Северный | ул. Парковая, 3 Таблица «Движение товаров» (дата в формате ГГГГ-ММ-ДД, количество — в упаковках): ID оп. | Дата | Магазин | Артикул | Тип операции | Упаковок 1 | 2026-06-03 | М1 | 102 | Продажа | 7 2 | 2026-06-03 | М2 | 101 | Поступление | 10 3 | 2026-06-03 | М2 | 104 | Продажа | 2 4 | 2026-06-03 | М1 | 105 | Продажа | 11 5 | 2026-06-03 | М1 | 103 | Продажа | 9 6 | 2026-06-03 | М4 | 101 | Продажа | 4 7 | 2026-06-04 | М4 | 105 | Поступление | 8 8 | 2026-06-04 | М2 | 105 | Продажа | 8 9 | 2026-06-04 | М3 | 102 | Поступление | 11 10 | 2026-06-04 | М3 | 101 | Продажа | 4 11 | 2026-06-05 | М1 | 103 | Поступление | 11 12 | 2026-06-06 | М1 | 103 | Продажа | 12 13 | 2026-06-07 | М4 | 106 | Продажа | 2 14 | 2026-06-08 | М3 | 105 | Продажа | 9 15 | 2026-06-08 | М1 | 101 | Поступление | 8 16 | 2026-06-08 | М3 | 103 | Поступление | 3 17 | 2026-06-09 | М1 | 101 | Поступление | 11 18 | 2026-06-09 | М3 | 104 | Продажа | 10 Сколько килограммов сахара (все товары, наименование которых начинается со слова «Сахар») было продано в магазинах Центрального района с 2 по 8 июня 2026 года включительно? Поступления товара в расчёт не принимаются.
Премии сотрудников отделов
Заданы три таблицы. «Отдел» (ID отдела | Название | Город): ID | Название | Город 1 | Разработка | Казань 2 | Продажи | Москва 3 | Поддержка | Казань 4 | Аналитика | Самара «Сотрудник» (ID | Фамилия | ID отдела | Оклад, тыс. руб.): ID | Фамилия | Отдел | Оклад 1 | Агеев | 1 | 120 2 | Белова | 1 | 135 3 | Власов | 2 | 95 4 | Громова | 2 | 105 5 | Дмитриев | 3 | 70 6 | Ершова | 3 | 75 7 | Жуков | 4 | 110 8 | Зайцева | 1 | 150 9 | Исаев | 3 | 68 10 | Крылов | 2 | 99 «Премия» (ID сотрудника | Месяц | Сумма, руб.): Сотрудник | Месяц | Сумма 1 | февраль | 6000 1 | февраль | 11000 1 | апрель | 18000 2 | апрель | 20000 2 | февраль | 10000 3 | март | 12000 4 | март | 5000 4 | февраль | 21000 5 | февраль | 23000 5 | февраль | 26000 5 | апрель | 15000 5 | март | 30000 5 | март | 12000 5 | апрель | 13000 6 | март | 8000 8 | март | 21000 9 | апрель | 6000 10 | февраль | 28000 Найдите суммарную сумму премий (в рублях), начисленных в марте сотрудникам отделов, расположенных в городе Казань.
Потомки в таблице родственных связей
Две таблицы описывают семью. «Люди» (ID | Фамилия И. О. | Пол | Год рождения): ID | Фамилия И. О. | Пол | Год 1 | Ковалёв А.Н. | М | 1948 2 | Ковалёва Т.П. | Ж | 1950 3 | Ковалёв И.А. | М | 1972 4 | Громова О.А. | Ж | 1975 5 | Громов С.В. | М | 1970 6 | Ковалёва М.И. | Ж | 1996 7 | Ковалёва Н.Р. | Ж | 1974 8 | Ковалёв Д.И. | М | 1999 9 | Громова А.С. | Ж | 1998 10 | Громов П.С. | М | 2001 11 | Петров Е.Д. | М | 1995 12 | Петров К.Е. | М | 2022 13 | Петрова Л.Е. | Ж | 2024 14 | Белова Е.Ю. | Ж | 2023 15 | Белов Ю.К. | М | 1997 «Родство» (ID родителя | ID ребёнка): 1 → 3; 2 → 3; 1 → 4; 2 → 4; 3 → 6; 7 → 6; 3 → 8; 7 → 8; 4 → 9; 5 → 9; 4 → 10; 5 → 10; 6 → 12; 11 → 12; 6 → 13; 11 → 13; 9 → 14; 15 → 14 Сколько всего потомков (дети, внуки и правнуки) у супругов Ковалёва А. Н. и Ковалёвой Т. П. вместе? Каждый человек учитывается один раз.
Остаток товаров отдела по району (три таблицы)
База данных магазинной сети состоит из трёх таблиц. «Товар» (Артикул | Отдел | Наименование | Масса единицы, кг): | Артикул | Отдел | Наименование | Масса единицы, кг | | --- | --- | --- | --- | | 101 | Бакалея | Мука пшеничная | 2 | | 102 | Бакалея | Рис круглозёрный | 1 | | 103 | Бакалея | Сахар-песок | 1 | | 104 | Молочные продукты | Молоко 3,2% | 1 | | 105 | Молочные продукты | Сметана 20% | 1 | | 106 | Консервы | Горошек зелёный | 1 | «Магазин» (ID | Район | Адрес): | ID | Район | Адрес | | --- | --- | --- | | 1 | Центральный | пр. Мира, 12 | | 2 | Центральный | ул. Садовая, 5 | | 3 | Северный | ул. Лесная, 40 | | 4 | Южный | ул. Речная, 8 | «Движение» (ID операции | Дата | ID магазина | Артикул | Тип операции | Количество единиц): | ID операции | Дата | ID магазина | Артикул | Тип операции | Количество | | --- | --- | --- | --- | --- | --- | | 1 | 03.06 | 1 | 101 | Поступление | 120 | | 2 | 03.06 | 2 | 101 | Поступление | 80 | | 3 | 03.06 | 3 | 102 | Поступление | 150 | | 4 | 04.06 | 1 | 101 | Продажа | 45 | | 5 | 04.06 | 2 | 101 | Продажа | 30 | | 6 | 04.06 | 1 | 102 | Поступление | 60 | | 7 | 05.06 | 1 | 103 | Поступление | 200 | | 8 | 05.06 | 3 | 102 | Продажа | 70 | | 9 | 05.06 | 2 | 103 | Поступление | 90 | | 10 | 06.06 | 1 | 102 | Продажа | 25 | | 11 | 06.06 | 2 | 103 | Продажа | 35 | | 12 | 06.06 | 2 | 102 | Поступление | 40 | | 13 | 07.06 | 1 | 103 | Продажа | 110 | | 14 | 07.06 | 4 | 101 | Поступление | 50 | | 15 | 07.06 | 2 | 102 | Продажа | 15 | | 16 | 07.06 | 1 | 104 | Поступление | 90 | | 17 | 07.06 | 1 | 104 | Продажа | 40 | На сколько килограммов изменилась суммарная масса товаров отдела «Бакалея» в магазинах района «Центральный» за период 03.06–07.06 (поступления увеличивают, продажи уменьшают)? Все операции, приведённые в таблице, относятся к этому периоду.
Двоюродные братья и сёстры по таблице родства
Две таблицы описывают родственные связи. «Люди» (ID | Фамилия И. О.): | ID | Фамилия И. О. | | --- | --- | | 1 | Орлов А.И. | | 2 | Орлова М.П. | | 3 | Орлов К.А. | | 4 | Орлова Н.А. | | 5 | Лебедев С.В. | | 6 | Орлов Д.К. | | 7 | Орлова Е.К. | | 8 | Лебедев П.С. | | 9 | Лебедева О.С. | | 10 | Орлова В.Д. | | 11 | Лебедев И.П. | | 12 | Лебедев Т.О. | | 13 | Лебедева Ю.П. | | 14 | Орлов Р.Д. | | 15 | Лебедев А.П. | | 16 | Лебедев Г.С. | | 17 | Лебедева К.О. | | 18 | Лебедев Н.Г. | «Родство» (ID родителя → ID ребёнка): 1 → 3; 2 → 3; 1 → 4; 2 → 4; 3 → 6; 3 → 7; 4 → 8; 5 → 8; 4 → 9; 5 → 9; 4 → 16; 5 → 16; 6 → 10; 6 → 14; 8 → 11; 8 → 13; 8 → 15; 9 → 12; 9 → 17; 16 → 18. Сколько двоюродных братьев и сестёр у Лебедева Т.О. (ID 12)? Двоюродными считаются дети родных брата или сестры одного из родителей (то есть людей, у которых с этим родителем общие оба родителя).
Три буквы в оставшейся ветке кодового дерева
Для кодирования шести букв А, Б, В, Г, Д, Е используется неравномерный двоичный код, удовлетворяющий условию Фано. Известны коды трёх букв: А — 0, Б — 10, В — 110. Остальные три буквы нужно закодировать так, чтобы суммарная длина кодовых слов букв Г, Д и Е была наименьшей. Чему равна эта суммарная длина?
Число способов декодирования
Для кодирования букв используются слова: А — 0, Б — 01, В — 11, Г — 101. Условие Фано не выполняется, поэтому одну и ту же двоичную последовательность можно расшифровать по-разному. Сколько существует различных сообщений (последовательностей букв), которым соответствует двоичная строка 0101110?
Сколько слов длины 4 можно добавить
Три буквы закодированы словами 00, 01 и 100 (условие Фано выполняется). Сколько существует двоичных слов длины 4, каждое из которых можно использовать как код ещё одной буквы, не нарушая условия Фано?
Оптимальный префиксный код для сообщения
Сообщение «КАРАКАТИЦАКАРАКУЛИ» требуется закодировать неравномерным двоичным кодом, удовлетворяющим условию Фано. Каждой букве сопоставляется своё кодовое слово. Какое наименьшее количество бит необходимо для кодирования всего сообщения при наилучшем выборе кода?
Автомат с чётностью и дописыванием
Автомат получает на вход натуральное число N и строит новое число R по следующим правилам. 1. Строится двоичная запись числа N. 2. Если N чётное, то слева к записи дописывается 1, а справа 0. Если N нечётное, то слева дописывается 11, а справа 1. 3. Полученная запись является двоичной записью числа R. Укажите наименьшее число N, для которого R больше 400.
Троичный автомат
Автомат получает на вход натуральное число N и строит число R так. 1. Строится троичная запись числа N. 2. Складываются все цифры этой записи; остаток от деления суммы на 3 записывается в конец троичной записи. 3. Над новой записью выполняется то же действие ещё раз. Полученная запись — троичная запись числа R. Найдите наименьшее N, при котором R > 500.
Автомат: дописывание в зависимости от чётности
Автомат получает на вход натуральное число $N$ и строит новое число $R$ по следующим правилам. 1. Строится двоичная запись числа $N$. 2. Если $N$ чётное, к записи справа дописывается «10»; если нечётное — слева дописывается «1», а справа «01». 3. Полученная запись — двоичная запись числа $R$. Укажите наименьшее число $N$, для которого результат $R$ больше 300.
Автомат: остаток числа единиц, дважды
Автомат получает на вход натуральное число $N$ и преобразует его по следующему алгоритму. 1. Строится двоичная запись числа $N$. 2. Подсчитывается число единиц в записи, находится остаток $k$ от деления этого числа на 3. 3. К записи справа дописывается двухразрядная двоичная запись числа $k$ (00, 01 или 10). 4. Пункты 2 и 3 повторяются для полученной записи ещё один раз. Полученная запись — двоичная запись числа $R$. Найдите наибольшее $N$, для которого $R < 500$.
Исполнитель Черепаха: два прямоугольника
Исполнитель Черепаха перемещается по плоскости. В начале — в точке (0, 0), голова направлена вверх (по оси Oy). Команды: Вперёд n (n шагов в направлении головы), Направо m и Налево m (поворот на m градусов), Поднять хвост (перестать рисовать), Опустить хвост. Записанная в скобках последовательность выполняется заданное число раз. Повтори 2 [Вперёд 10 Направо 90 Вперёд 6 Направо 90] Поднять хвост Вперёд 5 Направо 90 Вперёд 7 Налево 90 Опустить хвост Повтори 2 [Вперёд 6 Направо 90 Вперёд 4 Направо 90] Сколько точек с целочисленными координатами лежит строго внутри фигур, ограниченных нарисованными линиями (точки на самих линиях не считаются)?
Вложенные циклы и функция
Определите, что будет напечатано в результате выполнения программы. ```python def f(x): return x * x % 11 s = 0 for a in range(1, 6): for b in range(a, 6): if f(a) + f(b) > 10: s += a * b print(s) ```
Какое число нужно ввести
Ниже записана программа. Укажите наименьшее натуральное число x, при вводе которого программа выведет число, большее 200. ```python x = int(input()) a = 0 b = 1 while x > 0: if x % 2 == 1: a += b b *= 3 x //= 2 print(a) ```
Серия фотографий со сжатием
Фотоаппарат создаёт снимки размером 2048 × 1536 пикселей, каждый пиксель кодируется 24 битами. Перед сохранением снимок сжимается в среднем в 4 раза. Сколько мегабайт (1 Мбайт = 2²⁰ байт) занимает серия из 40 снимков?
Выгодно ли сжимать файл перед передачей
Файл передали по каналу со скоростью 2¹⁹ бит/с за 64 секунды. Теперь тот же файл нужно передать по каналу со скоростью 2¹⁵ бит/с. Можно передать его как есть, а можно предварительно сжать (сжатие уменьшает файл вдвое и занимает 8 секунд, при этом сжатый файл передаётся только после окончания сжатия). На сколько секунд быстрее второй способ?
Звук в моно и стерео
Одноканальная (моно) звукозапись длительностью 30 с сделана с частотой дискретизации 32 кГц и разрядностью 16 бит. Тот же звук записали заново: в стерео (2 канала), с частотой дискретизации 64 кГц и разрядностью 24 бита, а затем сжали файл в 3 раза. Во сколько раз размер нового файла больше размера исходного? Ответ — целое число.
Номер слова в алфавитном списке
Все пятибуквенные слова, составленные из букв А, К, Л, О (буквы могут повторяться), записаны в алфавитном порядке и пронумерованы, начиная с 1: ААААА, ААААК, ААААЛ, ААААО, АААКА, … Какой номер имеет слово ОКЛАК?
Слова без двух гласных подряд
Сколько существует пятибуквенных слов (не обязательно осмысленных), составленных из букв Е, К, О, П, С, в которых нет двух гласных букв подряд? Буквы в слове могут повторяться. (Гласные: Е, О; согласные: К, П, С.)
Номер слова в списке перестановок
Все слова, составленные из пяти букв А, К, О, Р, Т, в каждом из которых каждая буква используется ровно один раз, записаны в алфавитном порядке и пронумерованы, начиная с 1: АКОРТ, АКОТР, АКРОТ, … Какой номер имеет слово ОТКАР?
Слова с двумя одинаковыми буквами и без повторов подряд
Сколько существует шестибуквенных слов из букв А, Б, В, Г, в которых буква Б встречается ровно два раза и никакие две одинаковые буквы не стоят рядом?
Строки таблицы с одной парой повторов
В таблице 12 строк по 6 натуральных чисел. Определите, в скольких строках одновременно выполнены два условия: 1) в строке ровно одно число встречается дважды, а остальные четыре числа различны и отличаются от повторяющегося; 2) среднее арифметическое этих четырёх неповторяющихся чисел больше повторяющегося числа. № | A | B | C | D | E | F 1 | 9 | 4 | 2 | 7 | 3 | 2 2 | 9 | 5 | 8 | 9 | 7 | 1 3 | 1 | 8 | 2 | 5 | 5 | 1 4 | 7 | 8 | 8 | 5 | 4 | 9 5 | 3 | 5 | 8 | 6 | 6 | 5 6 | 6 | 9 | 1 | 6 | 8 | 5 7 | 6 | 6 | 9 | 7 | 9 | 8 8 | 4 | 3 | 9 | 2 | 3 | 5 9 | 6 | 6 | 3 | 5 | 3 | 5 10 | 3 | 2 | 1 | 2 | 7 | 4 11 | 6 | 1 | 5 | 1 | 2 | 2 12 | 2 | 2 | 9 | 5 | 8 | 7
Числа с возрастающими цифрами
Сколько существует четырёхзначных чисел, у которых цифры строго возрастают слева направо (каждая следующая цифра больше предыдущей) и сумма цифр кратна 3?
Перестановки букв слова без одинаковых соседей
Сколько различных слов (не обязательно осмысленных) можно получить, переставляя буквы слова ПРОГРАММА, так, чтобы никакие две одинаковые буквы не стояли рядом?
Строки таблицы с большой «верхней» тройкой
В файле электронной таблицы (приведён ниже полностью) в каждой строке записано шесть натуральных чисел. | № | A | B | C | D | E | F | | --- | --- | --- | --- | --- | --- | --- | | 1 | 25 | 8 | 43 | 76 | 53 | 50 | | 2 | 14 | 33 | 74 | 62 | 88 | 59 | | 3 | 72 | 37 | 8 | 71 | 9 | 56 | | 4 | 22 | 42 | 88 | 62 | 23 | 8 | | 5 | 83 | 70 | 82 | 70 | 31 | 59 | | 6 | 44 | 67 | 35 | 29 | 89 | 8 | | 7 | 11 | 33 | 64 | 73 | 11 | 39 | | 8 | 18 | 30 | 38 | 70 | 90 | 9 | | 9 | 21 | 60 | 17 | 53 | 33 | 10 | | 10 | 66 | 31 | 66 | 46 | 84 | 20 | | 11 | 18 | 28 | 77 | 31 | 78 | 75 | | 12 | 52 | 55 | 30 | 57 | 82 | 27 | | 13 | 37 | 58 | 40 | 15 | 45 | 81 | | 14 | 83 | 64 | 32 | 77 | 79 | 40 | Определите количество строк таблицы, для которых одновременно выполнены условия: — сумма трёх наибольших чисел строки больше суммы трёх остальных более чем на 110; — среднее арифметическое всех чисел строки меньше наибольшего числа строки больше чем на 30, и в строке есть хотя бы одно число, кратное 5.
Четырёхзначные числа с суммой цифр и порядком
Сколько существует четырёхзначных натуральных чисел, в записи которых все цифры различны, сумма цифр равна 14, а первая цифра больше последней?
Расчёт стоимости с условной скидкой
На складе хранятся товары (столбец A — название, B — категория, C — остаток на складе, шт., D — цена за штуку, руб.): Товар | Кат. | Остаток | Цена Тетрадь | A | 120 | 40 Ручка | A | 35 | 30 Линейка | B | 80 | 20 Маркер | A | 60 | 70 Папка | B | 45 | 90 Степлер | A | 90 | 150 Клей | A | 55 | 60 Скрепки | B | 200 | 10 В столбце E вычисляется цена со скидкой по формуле =ЕСЛИ(C2>50; D2*0,9; D2), в столбце F — стоимость остатка =C2*E2 (формулы протянуты на все строки 2–9). Чему равна сумма значений столбца F по товарам категории A?
Поиск слова в тексте
Дан фрагмент текста: «Информатика изучает способы получения, хранения и передачи информации. В школе ученик знакомится с алгоритмами и программами, а потом учится писать их сам. И если сначала задача кажется сложной, то после нескольких попыток она становится понятной. Программа состоит из команд, и каждая команда выполняется по порядку. Ошибка в одной строке и сбой во всей программе — это обычное дело, и нужно уметь находить ошибки. И тогда решение приходит само.» Сколько раз в этом тексте встречается слово «и» (как отдельное слово, строчная или заглавная буква — безразлично)? Слова, содержащие «и» внутри, не считаются.
Формула с накоплением по столбцу
В электронной таблице в диапазон A2:B7 записаны числа, в ячейке C1 записано число 10. В ячейку C2 ввели формулу =C1+ЕСЛИ(A2>B2; A2−B2; B2−A2) и скопировали её в диапазон C3:C7. A | B 8 | 2 3 | 7 12 | 15 5 | 5 9 | 6 4 | 10 (строки 2–7 соответственно) Чему равно значение в ячейке C7?
Поиск всех форм слова в тексте
Дан фрагмент текста: «Операционная система управляет процессами: каждый процесс получает свой квант времени процессора. Планировщик процессов решает, какой из процессов запускать следующим. Если процесс ждёт ввода, система переключается на другой процесс. Многие процессоры содержат несколько ядер, но и при этом число запущенных процессов обычно больше числа ядер. Диспетчер задач показывает, сколько ресурсов потребляет каждый процесс и сколько памяти занято процессами. Процессом также называют программу в момент выполнения; для процессов создаются отдельные адресные пространства, а процессорное время распределяется между ними. Завершение процесса освобождает память, а зависший процесс можно снять принудительно.» Сколько раз в этом тексте встречается слово «процесс» в любой падежной форме единственного и множественного числа (процесс, процесса, процессу, процессом, процессе, процессы, процессов, процессам, процессами, процессах), независимо от регистра букв? Слова «процессор», «процессоры», «процессорное» и т. п. не считаются.
Копирование формулы со смешанными ссылками
В электронной таблице заполнены ячейки: A1 = 2, B1 = 3, C1 = 5, D1 = 4; A2 = 1, A3 = 4, A4 = 3. В ячейку B2 ввели формулу =$A2*B$1+A$1 и скопировали её во все ячейки диапазона B2:D4. Чему равна сумма значений всех ячеек диапазона B2:D4?
База автомобильных номеров
Автомобильный номер состоит из 7 символов: первые 3 символа — буквы из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (12 букв), остальные 4 — десятичные цифры. Каждый символ номера кодируется одинаковым минимально возможным числом бит (алфавит — все 22 допустимых символа), номер хранится целым числом байт. Кроме номера, о каждой машине хранится ещё 11 байт сведений. Сколько Кбайт нужно для хранения данных о 4096 машинах?
Хранилище паролей и сведений
Пароль состоит из 9 символов, каждый из которых — заглавная или строчная латинская буква, цифра или один из 8 специальных знаков. Для хранения всех паролей используется одинаковое для каждого символа минимально возможное число бит, а пароль целиком занимает целое число байт. Для каждого пользователя дополнительно хранится 14 байт служебных сведений. Сколько Кбайт займут данные 2048 пользователей?
Идентификаторы и дополнительные сведения в базе
Идентификатор пользователя состоит из 14 символов и может содержать заглавные буквы русского алфавита (33 буквы) и десятичные цифры. Для кодирования каждого символа используют одинаковое наименьшее возможное число бит, а идентификатор целиком занимает наименьшее возможное целое число байт. В базе для каждого пользователя, помимо идентификатора, хранятся дополнительные сведения, занимающие одинаковое целое число байт. Для хранения сведений о 2000 пользователях потребовалось 38000 байт. Сколько байт занимают дополнительные сведения об одном пользователе?
Объём базы паролей в килобайтах
Пароль состоит из 12 символов, каждый из которых — заглавная латинская буква (26 букв), цифра (10 цифр) или один из 8 специальных символов. Для кодирования каждого символа используют одинаковое наименьшее возможное число бит; пароль целиком хранится в наименьшем возможном целом числе байт. Помимо пароля, для каждого пользователя хранятся ещё 7 байт служебных данных. Сколько килобайт (1 Кбайт = 1024 байт) займёт хранение сведений о 512 пользователях?
Редактор: двойки и пятёрки
Исполнитель Редактор получает на вход строку цифр и выполняет программу. Команда заменить (v, w) заменяет в строке первое слева вхождение цепочки v на цепочку w. НАЧАЛО ПОКА нашлось (222) ИЛИ нашлось (555) ЕСЛИ нашлось (222) ТО заменить (222, 5) ИНАЧЕ заменить (555, 22) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход подана строка, состоящая из 80 цифр 2. Чему равна сумма цифр строки, полученной в результате выполнения программы?
Редактор: движущийся маркер
Исполнитель Редактор выполняет программу, где команда заменить (v, w) заменяет первое слева вхождение v на w. НАЧАЛО ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0) ЕСЛИ нашлось (>1) ТО заменить (>1, 22>) ИНАЧЕ ЕСЛИ нашлось (>2) ТО заменить (>2, 2>) ИНАЧЕ заменить (>0, 1>) КОНЕЦ ЕСЛИ КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход подана строка >111112220000. Чему равна сумма цифр в строке, полученной после выполнения программы?
Редактор: свёртка двоек и троек
Исполнитель Редактор получает на вход строку цифр и выполняет программу. Команда «заменить (v, w)» заменяет в строке первое слева вхождение цепочки v на цепочку w. ``` НАЧАЛО ПОКА нашлось (22) ИЛИ нашлось (333) ЕСЛИ нашлось (22) ТО заменить (22, 3) ИНАЧЕ заменить (333, 2) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ ``` На вход подана строка, состоящая из 70 цифр 2. Чему равна сумма цифр строки, полученной в результате выполнения программы?
Редактор: движущаяся стрелка с тремя правилами
Исполнитель Редактор получает на вход строку, состоящую из символа «>» и цифр, и выполняет программу. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки v на w. Если подходят несколько правил, выполняется первое по списку. ``` НАЧАЛО ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0) ЕСЛИ нашлось (>1) ТО заменить (>1, 22>) ИНАЧЕ ЕСЛИ нашлось (>2) ТО заменить (>2, 2>1) ИНАЧЕ заменить (>0, 1>) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ ``` На вход подана строка >1202102212. Чему равна сумма цифр строки, полученной после выполнения программы? (Символ «>» в сумме не учитывается.)
Наибольшее число единиц в маске
Два узла, находящиеся в одной сети, имеют IP-адреса 117.191.37.84 и 117.191.51.132. Укажите наибольшее возможное количество единиц в двоичной записи маски этой сети.
Сколько масок подходит
Узел с IP-адресом 142.108.212.150 принадлежит сети с адресом 142.108.192.0. Маска сети — число, в двоичной записи которого сначала идут единицы, затем нули. Сколько существует различных масок, для которых это возможно?
Маска для заданного числа узлов
В подсети нужно разместить не менее 50 компьютеров. Адрес сети — 192.168.7.0, маска имеет вид 255.255.255.x. Найдите наибольшее возможное значение x (последнего байта маски), при котором в сети хватит адресов для 50 узлов. Адрес сети и широковещательный адрес узлам назначать нельзя.
Цифры в пятеричной записи значения
Значение выражения 5¹¹ + 5⁸ − 5⁴ − 2 записали в пятеричной системе счисления. Сколько цифр 4 содержит эта запись?
Неизвестная цифра и делимость
Число 2x31₉ записано в девятеричной системе счисления (x — неизвестная цифра от 0 до 8). Найдите сумму всех значений x, при которых это число делится на 4 без остатка.
Шестёрки в семеричной записи
Значение выражения 7⁴⁰ − 7²⁵ + 7¹⁰ − 1 записали в семеричной системе счисления. Сколько цифр 6 в этой записи?
Делимость и наибольшее A
Обозначим ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на m». Для какого наибольшего натурального числа A формула ¬ДЕЛ(x, A) → (ДЕЛ(x, 12) → ДЕЛ(x, 18)) тождественно истинна (то есть принимает значение 1 при любом натуральном x)?
Делимость и наименьшее A
Обозначим ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на m». Для какого наименьшего натурального числа A формула ДЕЛ(x, A) → (ДЕЛ(x, 12) ∨ ¬ДЕЛ(x, 18)) тождественно истинна (то есть принимает значение 1 при любом натуральном x)?
Поразрядная конъюнкция: наименьшее A
Обозначим через $x \,\&\, y$ поразрядную конъюнкцию неотрицательных целых чисел $x$ и $y$. Для какого наименьшего натурального числа $A$ формула $(x \,\&\, 25 \ne 0) \to ((x \,\&\, 41 = 0) \to (x \,\&\, A \ne 0))$ тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной $x$)?
Значение выражения с факториалоподобной функцией
Алгоритм вычисления функции F(n) задан соотношениями: F(1) = 1; F(n) = n · F(n − 1) при n > 1. Чему равно значение выражения F(2026) / F(2024)?
Взаимная рекурсия двух функций
Алгоритмы вычисления функций F(n) и G(n) заданы соотношениями: F(1) = 1, F(2) = 2; G(1) = 2, G(2) = 1; F(n) = F(n − 1) + 2 · G(n − 2) при n > 2; G(n) = G(n − 1) + F(n − 2) при n > 2. Чему равно значение F(9)?
Сколько раз вызывается функция
Функция F задана на Python: ```python def F(n): if n <= 2: return 1 return F(n - 1) + F(n - 2) ``` Сколько всего раз будет вызвана функция F (включая первый вызов), если выполнить F(7)?
Рекурсия с целой частью от деления пополам
Алгоритм вычисления функции $F(n)$ задан следующими соотношениями: $F(1) = 1$; $F(n) = F(n - 1) + F(\lfloor n / 2 \rfloor)$ при $n > 1$, где $\lfloor n / 2 \rfloor$ — целая часть от деления $n$ на 2. Чему равно значение $F(20)$?
Пары с элементом выше среднего
Дана последовательность из 16 натуральных чисел: 46, 28, 29, 25, 36, 74, 63, 11, 75, 24, 48, 39, 15, 47, 28, 65. Найдите количество пар соседних элементов, в которых хотя бы одно число больше среднего арифметического всех 16 чисел, а сумма пары кратна 3.
Тройки подряд идущих чисел
Дана последовательность из 15 натуральных чисел: 63, 53, 58, 68, 57, 24, 72, 85, 81, 39, 63, 83, 10, 13, 19. Найдите количество троек подряд идущих элементов, в которых ровно два числа кратны 3, а сумма трёх чисел нечётна.
Пары соседних: количество и наибольшая сумма
Дана последовательность из 24 натуральных двузначных чисел: 43, 28, 87, 83, 24, 26, 24, 88, 49, 11, 62, 60, 44, 93, 33, 12, 88, 89, 12, 46, 60, 47, 22, 12. Найдите все пары соседних элементов последовательности, в которых хотя бы один элемент оканчивается на цифру 3, а сумма элементов пары не превышает $M + 40$, где $M$ — наибольшее число последовательности, оканчивающееся на 3. Определите количество таких пар и наибольшую сумму элементов среди них. В ответе запишите сумму этих двух значений.
Пары чётных чисел с суммой, кратной 7
Дана последовательность из 18 натуральных чисел: 46, 54, 60, 15, 54, 8, 17, 11, 58, 22, 11, 34, 30, 28, 38, 27, 7, 25. Найдите количество пар элементов (не обязательно соседних, каждая пара учитывается один раз), в которых оба числа чётные, а сумма кратна 7.
Неравенства с параметром: линейная форма
Для какого наименьшего целого неотрицательного числа A выражение (x + 2y > 28) ∨ (x < A) ∨ (y < A) тождественно истинно (то есть принимает значение 1) при любых целых неотрицательных x и y?
Неравенства с параметром: произведение
Для какого наименьшего целого неотрицательного A выражение (x · y < 3A) ∨ (x ≥ 14) ∨ (y ≥ 9) тождественно истинно при любых целых неотрицательных x и y?
Робот собирает монеты: максимальная сумма
Квадрат 6 × 6 клеток заполнен числами (число — количество монет в клетке): 4 7 2 8 5 3 6 1 9 3 7 4 2 8 5 6 1 9 7 3 4 2 8 6 5 9 1 7 3 2 8 2 6 4 9 5 Робот стоит в левой верхней клетке и должен попасть в правую нижнюю, перемещаясь только вправо или вниз. Он собирает монеты во всех клетках пути, включая начальную и конечную. Какое наибольшее число монет он может собрать?
Робот: разность наибольшей и наименьшей сумм
Прямоугольная таблица 5 × 7 заполнена числами: 5 3 8 2 6 4 7 1 6 4 9 3 5 2 7 2 5 1 8 3 6 4 9 3 6 2 7 1 6 1 8 4 5 2 9 Робот стартует в левой верхней клетке и движется в правую нижнюю, перемещаясь только вправо или вниз; он суммирует числа во всех клетках пути, включая начальную и конечную. Найдите разность между наибольшей и наименьшей возможными суммами.
Робот с диагональным ходом
Прямоугольная таблица 5 × 6 заполнена числами: 4 6 2 2 7 9 1 6 6 4 3 7 6 2 8 6 9 3 4 2 5 4 3 4 7 1 3 5 1 5 Робот стартует в левой верхней клетке и движется в правую нижнюю. За один ход он может переместиться на одну клетку вправо, на одну клетку вниз или на одну клетку по диагонали вправо-вниз. Он суммирует числа во всех клетках пути, включая начальную и конечную. Найдите наибольшую возможную сумму.
Игра: Ваня выигрывает первым ходом (наименьшее S)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 3 камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 40 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 39. Укажите наименьшее значение S, при котором Петя не может выиграть первым ходом, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Игра с тремя ходами: единственное S
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 камень, добавить 4 камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 70. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 70 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 69. Укажите значение S, при котором Петя не может выиграть первым ходом, но при любом ходе Пети Ваня может выиграть своим первым ходом. (Такое S единственно.)
Игра: Ваня выигрывает первым ходом (наибольшее S)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня, добавить в кучу 3 камня либо увеличить количество камней в куче в четыре раза. Игра завершается, когда количество камней в куче становится не менее 90. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 90 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 89$. Укажите наибольшее значение $S$, при котором Петя не может выиграть первым ходом, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Игра с двумя кучами: Ваня выигрывает первым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней: в первой — $S$ камней, во второй — 5 камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить 3 камня в любую кучу либо увеличить количество камней в любой куче в два раза. Игра завершается, когда суммарное количество камней в двух кучах становится не менее 45. Победителем считается игрок, сделавший последний ход. Известно, что $1 \le S \le 39$. Найдите такое значение $S$, при котором Петя не может выиграть первым ходом, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Игра: Петя выигрывает вторым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 камень, добавить 4 камня либо увеличить количество камней в куче в три раза. Игра завершается, когда количество камней в куче становится не менее 60. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 60 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 59. Найдите два наименьших значения S, при которых Петя имеет выигрышную стратегию, причём одновременно выполняются условия: (1) Петя не может выиграть за один ход; (2) Петя может выиграть своим вторым ходом при любой игре Вани. В ответе запишите сумму этих двух значений.
Игра: три значения S и сумма
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня либо увеличить количество камней в куче в три раза. Игра завершается, когда количество камней в куче становится не менее 60. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 60 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 59. Найдите все значения S, при которых Петя не может выиграть первым ходом, но может выиграть своим вторым ходом при любой игре Вани. В ответе запишите сумму найденных значений.
Игра: Петя выигрывает вторым ходом (два наименьших S)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 60. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 60 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 59$. Найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются условия: (1) Петя не может выиграть за один ход; (2) Петя может выиграть своим вторым ходом при любой игре Вани. В ответе запишите сумму этих двух значений.
Игра: все значения S, выигрыш вторым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 камень, добавить в кучу 3 камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 50 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 49$. Найдите все значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно: (1) Петя не может выиграть за один ход; (2) Петя может выиграть своим вторым ходом при любой игре Вани. В ответе запишите сумму всех найденных значений $S$.
Игра с двумя кучами: Петя выигрывает вторым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней: в первой — $S$ камней, во второй — 12 камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить 2 камня в любую кучу либо увеличить количество камней в любой куче в два раза. Игра завершается, когда суммарное количество камней в двух кучах становится не менее 70. Победителем считается игрок, сделавший последний ход. Известно, что $1 \le S \le 57$. Найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно: (1) Петя не может выиграть за один ход; (2) Петя может выиграть своим вторым ходом при любой игре Вани. В ответе запишите сумму этих двух значений.
Игра: сколько значений S дают выигрыш вторым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 4 камня, добавить в кучу 7 камней либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 100 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 99$. Сколько существует значений $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются условия: (1) Петя не может выиграть за один ход; (2) Петя может выиграть своим вторым ходом при любой игре Вани?
Игра: Ваня выигрывает первым или вторым ходом
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 3 камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 40 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 39. Найдите наименьшее значение S, при котором одновременно выполняются два условия: (1) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; (2) у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
Игра: Ваня выигрывает за два хода (наибольшее S)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 2 камня, добавить 5 камней либо увеличить количество камней в куче в три раза. Игра завершается, когда количество камней в куче становится не менее 80. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 80 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 79. Найдите наибольшее значение S, при котором одновременно выполняются два условия: (1) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; (2) у Вани нет стратегии, позволяющей ему гарантированно выиграть первым ходом.
Игра: Ваня выигрывает за два хода (наименьшее S)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 камень, добавить в кучу 3 камня либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 50 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 49$. Найдите наименьшее значение $S$, при котором одновременно выполняются два условия: (1) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; (2) у Вани нет стратегии, позволяющей ему гарантированно выиграть первым ходом.
Игра: сумма всех S для выигрыша Вани за два хода
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 3 камня либо увеличить количество камней в куче в три раза. Игра завершается, когда количество камней в куче становится не менее 80. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 80 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 79$. Найдите все значения $S$, при которых одновременно выполняются условия: (1) у Вани есть стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети; (2) у Вани нет стратегии, позволяющей гарантированно выиграть первым ходом. В ответе запишите сумму найденных значений.
Игра: наибольшее S, при котором Ваня выигрывает за два хода
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 4 камня, добавить в кучу 7 камней либо увеличить количество камней в куче в два раза. Игра завершается, когда количество камней в куче становится не менее 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 100 или более камней. В начальный момент в куче было $S$ камней, $1 \le S \le 99$. Найдите наибольшее значение $S$, при котором одновременно выполняются два условия: (1) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; (2) у Вани нет стратегии, позволяющей ему гарантированно выиграть первым ходом.
Игра с двумя кучами: Ваня выигрывает за два хода
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней: в первой — $S$ камней, во второй — 6 камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить 2 камня в любую кучу либо увеличить количество камней в любой куче в два раза. Игра завершается, когда суммарное количество камней в двух кучах становится не менее 50. Победителем считается игрок, сделавший последний ход. Известно, что $1 \le S \le 43$. Найдите значение $S$, при котором одновременно выполняются два условия: (1) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; (2) у Вани нет стратегии, позволяющей ему гарантированно выиграть первым ходом.
Минимальное время выполнения процессов
Параллельно выполняются несколько независимых процессов. Каждый процесс может начаться, только когда завершились все процессы, от которых он зависит, и сразу же после их завершения (число процессоров неограниченно). Данные о процессах приведены в таблице. Процесс | Длительность, мс | Зависит от P1 | 4 | – P2 | 3 | – P3 | 5 | P1 P4 | 2 | P1, P2 P5 | 6 | P3 P6 | 4 | P4 P7 | 3 | P3, P4 P8 | 5 | P5, P6 P9 | 2 | P7 P10 | 4 | P8, P9 За какое минимальное время (в миллисекундах) могут быть выполнены все процессы?
Наибольшее число одновременных процессов
Используйте данные задачи о процессах (таблица ниже). Каждый процесс стартует в самый ранний возможный момент (сразу после завершения всех процессов, от которых зависит; независимые процессы стартуют в момент 0). Процесс | Длительность, мс | Зависит от P1 | 4 | – P2 | 3 | – P3 | 5 | P1 P4 | 2 | P1, P2 P5 | 6 | P3 P6 | 4 | P4 P7 | 3 | P3, P4 P8 | 5 | P5, P6 P9 | 2 | P7 P10 | 4 | P8, P9 Какое наибольшее число процессов выполняется одновременно в какой-то момент времени? (Процесс выполняется на промежутке от старта включительно до завершения не включительно.)
Минимальное время выполнения комплекса процессов
Параллельно выполняются несколько процессов. Процесс может начаться, только когда завершились все процессы, от которых он зависит, и стартует сразу после их завершения (число процессоров неограниченно). Данные о процессах: | Процесс | Длительность, мс | Зависит от | | --- | --- | --- | | P1 | 3 | – | | P2 | 5 | – | | P3 | 2 | – | | P4 | 4 | P1 | | P5 | 6 | P1, P2 | | P6 | 3 | P2, P3 | | P7 | 7 | P4 | | P8 | 2 | P4, P5 | | P9 | 5 | P5, P6 | | P10 | 4 | P7, P8 | | P11 | 3 | P8, P9, P10 | За какое минимальное время (в миллисекундах) после старта могут быть выполнены все процессы?
Запас времени процесса (допустимая задержка)
Параллельно выполняются несколько процессов. Каждый процесс стартует сразу после завершения всех процессов, от которых он зависит (число процессоров неограниченно); независимые процессы стартуют в момент 0. Данные о процессах: | Процесс | Длительность, мс | Зависит от | | --- | --- | --- | | P1 | 4 | – | | P2 | 2 | – | | P3 | 6 | P1 | | P4 | 3 | P1, P2 | | P5 | 5 | P3 | | P6 | 4 | P3, P4 | | P7 | 2 | P2 | | P8 | 3 | P5, P6 | | P9 | 5 | P6, P7 | | P10 | 4 | P8, P9 | На какое наибольшее время (в миллисекундах) можно задержать старт процесса P7 относительно самого раннего возможного, чтобы общее время выполнения комплекса процессов не увеличилось?
Два процессора: минимальное время выполнения независимых процессов
Имеется 9 независимых процессов, длительности которых (в миллисекундах): 13, 8, 11, 7, 9, 6, 12, 5, 10. Доступны два одинаковых процессора. Каждый процесс выполняется целиком на одном процессоре без прерываний, в любой момент процессор выполняет не более одного процесса; процессоры начинают работу в момент 0. Какое наименьшее время (в миллисекундах) требуется для завершения всех процессов?
Ускорение одного процесса вдвое
Параллельно выполняются несколько процессов; каждый стартует сразу после завершения всех процессов, от которых зависит (число процессоров неограниченно). Данные о процессах: | Процесс | Длительность, мс | Зависит от | | --- | --- | --- | | P1 | 6 | – | | P2 | 4 | – | | P3 | 8 | P1 | | P4 | 6 | P1, P2 | | P5 | 10 | P3 | | P6 | 4 | P3, P4 | | P7 | 6 | P4 | | P8 | 8 | P5, P6 | | P9 | 4 | P7, P6 | Один (любой) из процессов можно ускорить так, что его длительность сократится вдвое. Какое наименьшее общее время (в миллисекундах) выполнения всех процессов можно получить?
Программы исполнителя: обязательная точка и запрет
У исполнителя три команды, которым присвоены номера: 1. Прибавь 2 2. Прибавь 3 3. Умножь на 2 Первая команда увеличивает число на экране на 2, вторая — на 3, третья — умножает на 2. Программа для исполнителя — последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 30, при этом траектория вычислений содержит число 10 и не содержит число 17?
Количество программ с командами +1, +2, ×3
Исполнитель умеет выполнять три команды: Прибавь 1, Прибавь 2, Умножь на 3. Сколько существует программ, которые преобразуют число 1 в число 25 и содержат в траектории число 7, но не содержат число 11?
Программы исполнителя: обязательная точка 8 и запрет 12
У исполнителя три команды, которым присвоены номера: 1. Прибавь 1 2. Прибавь 3 3. Умножь на 2 Программа для исполнителя — последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 24, при этом траектория вычислений содержит число 8 и не содержит число 12? (Траектория включает начальное и конечное числа.)
Программы: две обязательные точки
Исполнитель умеет выполнять три команды: Прибавь 3, Прибавь 4, Умножь на 2. Программа — последовательность команд. Сколько существует программ, которые преобразуют число 1 в число 40, при этом траектория вычислений содержит и число 9, и число 20?
Программы с возведением в квадрат
Исполнитель умеет выполнять три команды: Прибавь 1, Прибавь 2, Возведи в квадрат. Программа — последовательность команд. Сколько существует программ, которые преобразуют число 2 в число 40, при этом траектория вычислений содержит число 5 и не содержит число 25?
Программы с ограничением на число команд умножения
Исполнитель умеет выполнять три команды: Прибавь 1, Прибавь 2, Умножь на 2. Программа — последовательность команд. Сколько существует программ, которые преобразуют число 1 в число 30 и содержат команду «Умножь на 2» ровно два раза?
Самая длинная цепочка без сочетания AB
Дана строка из 90 символов, состоящая из букв A, B и C: ACAABAABCBBAABBACCBABACBBAABCCAABCBBABCBBACBBBABACBACBBACBCBBACBCACBACACACBAABACBABABABABA Определите наибольшую длину непрерывной цепочки символов, в которой нет сочетания AB (буква A, сразу за которой следует буква B).
Подсчёт вхождений шаблонов
Дана строка из 100 символов (буквы A, B, C): BCBCAABBAAAABACAABBCCCCCAAABAABACBCBABCABBCCACBBCBACAACAAABCCAAABABAABACACBCABBACBBBAAACBABBACBABABA Сколько раз в ней встречаются подстроки ABA или CBC? Перекрывающиеся вхождения считаются отдельно (например, в строке ABABA подстрока ABA встречается 2 раза).
Самая длинная цепочка без одинаковых соседей
Дана строка из 80 символов, состоящая из букв A, B, C: BCBACBCCCCAACCCABBCABABCBACCBCABAABABCABBBCABCCCBAACCBACACBAACACABACCABBBBCCCCCB Найдите наибольшую длину цепочки подряд идущих символов, в которой никакие два соседних символа не совпадают.
Подстрока с ровно двумя буквами C и без сочетания BB
Дана строка из 110 символов, состоящая из букв A, B, C и D: BDAABCCBBBDADBBDCCCCBBCBBBDDADBBCACDBDCBBDDCCABDDCCABBDBBBDDDDCCAABDBACAACBDAADCBBCDADCDCCAABAADAACCBBACABABDA Определите наибольшую длину непрерывной цепочки символов, в которой буква C встречается ровно два раза и нет сочетания BB (двух букв B подряд).
Наибольшее число подряд идущих пар AB
Дана строка из 120 символов, состоящая из букв A, B, C и D: ABAABDACBBADCDACAABABABABACCAADBDBBDCDAADCBBBDACAABCDBACDBCAABABABBDDCAACDADBCDACDDBDDADDDBDCDBABABABABABAAABCCCBDBCBCCD Определите наибольшее количество подряд идущих пар символов AB (то есть наибольшее $k$, для которого в строке есть подстрока ABAB…AB, состоящая из $k$ пар AB).
Числа по маске и делимость
Маска числа — последовательность цифр, в которой могут встречаться символы «?» и «*». Символ «?» означает ровно одну произвольную цифру, символ «*» — любую последовательность цифр произвольной длины (в том числе пустую). Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 10 000 000, найдите все числа, соответствующие маске 1?2*5 и делящиеся на 123 без остатка. В ответе запишите количество таких чисел.
Число с тремя делителями
Найдите наибольшее натуральное число, не превышающее 1 000 000, у которого ровно 3 различных натуральных делителя (включая 1 и само число).
Числа ровно с пятью делителями на отрезке
Среди натуральных чисел, принадлежащих отрезку [100 000; 3 000 000], найдите все числа, имеющие ровно 5 различных натуральных делителей (включая 1 и само число). В ответе запишите сумму всех найденных чисел.
Маска числа и делимость на 29
Маской числа называется последовательность цифр, в которой могут встречаться символы «?» и «*». Символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность цифр произвольной длины, в том числе пустую. Найдите пять наименьших натуральных чисел, не превышающих $10^7$, которые соответствуют маске 1?3*8 и делятся на 29 без остатка. В ответе запишите сумму частных от деления этих чисел на 29.
Максимальный набор не пересекающихся заявок
В зале необходимо провести как можно больше мероприятий. Заявки заданы временными интервалами [начало; конец] (в часах): 1: [1; 4] 2: [3; 5] 3: [0; 6] 4: [5; 7] 5: [3; 9] 6: [5; 9] 7: [6; 10] 8: [8; 11] 9: [8; 12] 10: [2; 14] 11: [12; 16] 12: [13; 15] Два мероприятия можно провести в одном зале, если одно заканчивается не позже, чем начинается другое (совпадение конца и начала допустимо). Какое наибольшее количество мероприятий можно провести?
Диск и файлы: максимум файлов и размер последнего
На диск объёмом 100 Мбайт нужно записать как можно больше файлов. Размеры файлов (Мбайт): 18, 7, 25, 12, 9, 31, 14, 6, 22, 16, 11, 28, 5, 20. Найдите наибольшее количество файлов, которое можно записать, а затем — наибольший возможный размер самого большого файла среди записанных, если записано именно это наибольшее количество файлов. В ответе запишите второе число (наибольший возможный размер самого большого файла).
Парковка на два места: максимум принятых заявок
Автостоянка имеет 2 парковочных места. Поступили 12 заявок, каждая задана интервалом времени [начало; конец) в часах: 1: [15; 18) 2: [18; 29) 3: [24; 34) 4: [17; 29) 5: [19; 31) 6: [11; 21) 7: [27; 34) 8: [3; 12) 9: [25; 33) 10: [2; 8) 11: [16; 24) 12: [28; 38) Заявка занимает одно место на всё указанное время. Две заявки можно разместить на одном месте, если одна заканчивается не позже, чем начинается другая. Заявку нельзя выполнить частично. Какое наибольшее количество заявок можно принять?
Минимум контейнеров: не более двух предметов
На складе 16 предметов массой (в кг): 18, 55, 32, 70, 41, 25, 63, 12, 48, 36, 80, 29, 52, 21, 66, 44. Все предметы нужно упаковать в контейнеры. В каждый контейнер можно положить не более двух предметов, суммарная масса предметов в контейнере не должна превышать 100 кг. Какое наименьшее количество контейнеров потребуется?
Минимальная сумма пары с разрывом
Дана последовательность из 14 натуральных чисел (нумерация с 1): 53 32 17 11 80 44 38 55 23 89 56 13 20 45 Найдите минимальную сумму a[i] + a[j], где j − i ≥ 4, которая делится на 5. (В полной версии задачи последовательность содержит до 10⁷ чисел и хранится в файле, поэтому нужен алгоритм за один проход, а не перебор всех пар.)
Самый длинный фрагмент с суммой, кратной 7
Дана последовательность из 16 натуральных чисел: 19 3 5 4 6 1 13 9 18 8 5 13 3 13 15 16 Найдите наибольшую длину непрерывного фрагмента последовательности, сумма элементов которого делится на 7. (В реальной задаче чисел до 10⁷, нужен алгоритм за один проход.)
Количество фрагментов с суммой, кратной 5
Дана последовательность из 15 натуральных чисел: 17 29 16 9 26 30 3 10 7 13 5 5 6 20 29 Сколько существует непрерывных фрагментов (подряд идущих элементов; фрагмент из одного элемента тоже подходит), сумма элементов которых делится на 5? (В реальной задаче чисел до 10⁷, поэтому нужен линейный алгоритм.)
Наибольшая сумма фрагмента, кратная 11
Дана последовательность из 18 натуральных чисел: 43 42 30 58 46 51 52 27 28 6 42 26 29 5 5 30 50 17 Фрагментом называется непустая последовательность подряд идущих элементов. Найдите наибольшую сумму элементов фрагмента, состоящего не менее чем из двух элементов, которая делится на 11 без остатка. (В полной версии задачи последовательность содержит до $10^7$ чисел, поэтому нужен алгоритм за один проход.)
Наименьший фрагмент с суммой не меньше заданной
Дана последовательность из 20 натуральных чисел: 5 13 23 36 26 28 33 35 10 25 32 7 20 16 31 34 17 38 36 24 Найдите наименьшую возможную длину фрагмента (подряд идущих элементов), сумма элементов которого не меньше 150. (В полной версии задачи последовательность содержит до $10^7$ чисел.)