Решайте задания в удобном темпе. Ответы сохраняются в браузере, а результат появится после отправки теста.
Верный ответ: 20
Сначала сопоставим вершины по количеству дорог, выходящих из каждой из них. На графе пункт К соединён со всеми шестью остальными пунктами. В таблице единственный пункт с шестью связями — П5, значит, К соответствует П5.
Если мысленно убрать К и П5, оставшиеся пункты образуют одну цепочку. На графе это А—Б—В—Г—Д—Е, а в таблице — П3—П4—П7—П6—П2—П1. Цепочку можно читать и в обратном направлении, но нужные дороги в обоих случаях соответствуют тем же двум рёбрам:
Б—В ↔ П4—П7, длина 7;
Г—Д ↔ П6—П2, длина 13.
Требуется сумма протяжённостей, поэтому складываем 7 и 13.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18843.
(¬x∧y∧z)∨(¬x∧y∧¬z)∨(¬x∧¬y∧¬z)
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
Верный ответ: yxz
Каждое слагаемое дизъюнкции задаёт один истинный набор:
• ¬x ∧ y ∧ z — набор (x, y, z) = 011;
• ¬x ∧ y ∧ ¬z — набор 010;
• ¬x ∧ ¬y ∧ ¬z — набор 000.
Во всех трёх наборах x = 0, поэтому столбец, состоящий только из нулей, — второй — соответствует x.
Значения y в перечисленных наборах равны 1, 1, 0, а в таблице первый столбец содержит те же значения в обратном порядке строк: 0, 1, 1. Значения z равны 1, 0, 0; им соответствует третий столбец 0, 0, 1.
Порядок строк в таблице не важен: важно, что наборы столбцов полностью совпадают с тремя наборами, описанными формулой.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19141.
Верный ответ: 2
Для каждого мужчины из таблицы «Люди» считаем количество строк, в которых его ID указан в поле ID_родителя. Так получаем распределение мужчин-родителей по числу детей:
27 мужчин имеют одного ребёнка;
72 мужчины — двух детей;
1 мужчина — троих детей;
14 мужчин — четверых детей.
По условию требуется группа, состоящая ровно из 72 мужчин. Этой группе соответствует значение 2.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19088.
Верный ответ: 01
Для обратного условия Фано разворачиваем все слова и строим обычное префиксное дерево. Известные коды превращаются в 00, 010, 110 и 011.
Одноразрядный код невозможен: обе начальные ветви уже содержат известные слова. Среди слов длины 2 ветвь 00 занята, 01 является началом кодов 010 и 011, а 11 — началом кода 110. Свободна только ветвь 10.
Если назначить её букве Д, для трёх остальных букв остаётся ветвь 111, которую можно дополнительно разделить, например, на 1110, 11110 и 11111. После обратного разворота свободная ветвь 10 соответствует исходному коду 01.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19143.
1. Строится двоичная запись числа N. 2. В конец двоичной записи добавляются две первые цифры этой записи в обратном порядке. 3. Результат переводится в десятичную систему и выводится на экран.Пример. Дано число N = 11. Алгоритм работает следующим образом:
Верный ответ: 23
После дописывания двух цифр двоичная запись N сдвигается влево на два разряда. Поэтому результат равен 4N плюс число, образованное дописанными битами.
Для N, способного дать результат больше 90, двоичная запись имеет не менее двух разрядов и начинается либо с 10, либо с 11. После перестановки первые две цифры превращаются соответственно в 01 или 11, то есть к 4N добавляется 1 или 3.
Для N < 22 получаем R ≤ 4 · 21 + 3 = 87, поэтому результат больше 90 невозможен.
N = 22 = 101102: дописываем 01, получаем 10110012 = 89 — не подходит.
N = 23 = 101112: дописываем 01, получаем 10111012 = 93.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18928.
Верный ответ: 750
За два повторения блока Черепаха строит четыре стороны и возвращается в начальную точку. Получается ромб со стороной 30 и острым углом 60°; остальные повторения только обводят ту же границу.
Его можно задать вершинами (0; 0), (15; 15√3), (45; 15√3), (30; 0). Целые уровни y внутри фигуры — от 1 до 25, поскольку 15√3 ≈ 25,98. На каждом таком уровне левая граница имеет абсциссу y/√3, а правая — 30 + y/√3.
Между этими двумя нецелыми числами находится ровно 30 целых значений x. Поэтому внутренних точек 25 · 30 = 750.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 21204.
Верный ответ: 17
Подсказка: 2048 цветов = 211, значит глубина цвета 11 бит на пиксель.
Объём одного снимка: 128·2048·11 бит.
За 600 секунд можно передать 81920·600 бит.
Количество снимков: ⌊81920·600 / (128·2048·11)⌋ = 17.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 25508.
Верный ответ: 144
Среди данных букв три гласные — Е, У, А — и четыре согласные — Л, Р, С, М. Чтобы две буквы одного типа не оказались рядом, типы букв должны чередоваться.
Согласных на одну больше, поэтому возможна только схема СГСГСГС. Начать с гласной нельзя: тогда для чередования потребовалось бы четыре гласные.
Четыре согласные можно переставить на их местах 4! способами, а три гласные — 3! способами. Число кодов равно 4! · 3! = 24 · 6 = 144.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19174.
Верный ответ: 10
Вечерний промежуток 19:00–22:00 находится в столбцах U:X, а утренний промежуток 05:00–08:00 — в G:J.
Во вспомогательной ячейке Z2 используйте:
=ЕСЛИ(И(МЕСЯЦ(A2)=6;СРЗНАЧ(U2:X2)-СРЗНАЧ(G2:J2)>=5);1;0)
Сначала отдельно вычисляются два средних значения, затем из вечернего среднего вычитается утреннее. Проверка «не менее чем на 5 градусов» означает разность, большую или равную 5, поэтому знак строгого сравнения > использовать нельзя.
После протягивания до Z92 сумма столбца равна 10. Проверка месяца гарантирует, что учитываются только июньские дни.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18986.
Верный ответ: 11
Нужно посчитать две конкретные словоформы, поэтому выполняем два поиска с отключённым учётом регистра и с параметром «только слово целиком».
Отдельное слово «долг» встречается 5 раз, а отдельное слово «долгу» — 6 раз. Складываем результаты: 5 + 6 = 11.
Поиск по части слова «долг» дал бы лишние совпадения: «долго», «долгом», «долга», «долговременное» и другие слова. Именно поэтому важно искать каждую требуемую форму как целое слово.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18852.
Верный ответ: 29
Две части кода используют разные алфавиты, поэтому их размеры считаются отдельно.
Для 26 букв требуется 5 бит на символ. Первая часть из 12 букв занимает:
12 · 5 = 60 бит.
Для 10 цифр требуется 4 бита на символ. Вторая часть из 7 цифр занимает:
7 · 4 = 28 бит.
Весь код содержит 60 + 28 = 88 бит, то есть ровно 11 байт.
На одну запись приходится 2560 : 64 = 40 байт. После вычитания 11 байт персонального кода на дополнительные сведения остаётся 40 − 11 = 29 байт.
Складывать 26 и 10 и кодировать все позиции шестью битами нельзя: по условию буквенная и цифровая части кодируются раздельно.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19177.
| a0 | a1 | ... | am−1 | |
| q0 | команда | команда | ... | команда |
| q1 | команда | команда | ... | команда |
| ... | ... | ... | ... | ... |
| qn−1 | команда | команда | ... | команда |
| λ | Z | |
| q0 | λ, L, q0 | X, L, q1 |
| q1 | λ, S, q1 | X, L, q1 |
| ... | λ | λ | Z | Z | Z | Z | λ | λ | ... |
| ▲q0 |
| ... | λ | λ | X | X | X | X | λ | λ | ... |
| ▲q1 |
| λ | 1 | 0 | |
| q0 | λ, L, q1 | ||
| q1 | λ, R, q2 | 0, R, q2 | 1, L, q1 |
| q2 | λ, S, q2 | 1, R, q2 | 1, R, q2 |
Верный ответ: 254
В состоянии q1 головка идёт справа налево. Все нули на правом конце она заменяет единицами. При встрече с первой единицей программа записывает вместо неё 0, разворачивает головку вправо и переходит в q2. Далее все ячейки справа заполняются единицами до пустой ячейки.
Итак, конечные нули исходной строки исчезают, а ближайшая к ним единица превращается в один новый ноль. Чтобы исходных нулей было максимально много, оставим в строке только одну единицу. Расположим её на 50-й позиции слева: 49 нулей слева сохранятся, сама единица станет нулём, а 205 нулей справа превратятся в единицы.
После работы останется ровно 49 + 1 = 50 нулей. При этом изначально нулями были все 255 символов, кроме одной обязательной единицы.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 25524.
Верный ответ: 252
Байт маски не может принимать любое значение. Из-за правила «сначала единицы, затем нули» допустимы только 0, 128, 192, 224, 240, 248, 252, 254, 255. Так как требуется минимальное A, проверяем их по возрастанию.
Первые два байта во всех адресах сети фиксированы. В них суммарно 12 единиц. Значит, условие нарушится, если в правых двух байтах найдётся хотя бы 13 единиц.
При A = 248 получается сеть 252.63.192.0/21. В ней есть адрес 252.63.199.255: в его правых двух байтах 13 единиц, что больше 12, поэтому это значение A не подходит. При A = 252 сеть сужается до 252.63.192.0/22; даже у адреса 252.63.195.255, дающего максимальное количество единиц справа, их только 12. Следовательно, условие выполняется для каждого адреса этой сети.
from ipaddress import ip_network
for A in (0, 128, 192, 224, 240, 248, 252, 254, 255):
net = ip_network(f"252.63.194.3/255.255.{A}.0", strict=False)
ok = True
for address in net:
bits = f"{int(address):032b}"
if bits[:16].count("1") < bits[16:].count("1"):
ok = False
break
if ok:
print(A)
break
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 21659.
Верный ответ: 490
Умножение на 4 добавляет справа два нуля: все единицы лишь переходят в разряды на две позиции старше, поэтому их количество внутри скобок и во всём числе одинаково.
Преобразуем степени: 8200 = 2600, 4250 = 2500. После вычитания 2500 из 2600 единицы стоят в разрядах 500–599. Вычитание 2180 занимает из разряда 500: в разрядах 501–599 остаются 99 единиц, а разряды 180–499 дают ещё 320 единиц.
Младшая часть 275 − 31 = 275 − 25 + 1 содержит единицы в разрядах 5–74 и в разряде 0, то есть ещё 70 + 1. Блоки не пересекаются, поэтому считаем 99 + 320 + 70 + 1.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19180.
Верный ответ: 62
Чтобы второй и третий дизъюнкты были ложны, должны выполняться условия x < y и y ≤ 8. Именно среди таких пар нужно найти наибольшее значение 3x + 5y.
Выражение возрастает при увеличении x и y. Поэтому берём максимально возможное y = 8. Из условия x < y для целых неотрицательных чисел получаем максимальное x = 7.
Тогда 3x + 5y достигает значения 3 · 7 + 5 · 8 = 61. Первый дизъюнкт содержит строгое неравенство, поэтому параметр должен быть больше 61.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18938.
Верный ответ: 3133
Для n > 32 аргумент в рекурсивном вызове уменьшается на 5. Поэтому F(100) зависит от F(95), затем от F(90) и так далее, пока цепочка не дойдёт до F(30), для которого уже действует вторая формула.
Ключевые значения цепочки:
F(30) = 40 → F(35) = 49 → F(40) = 60 → F(45) = 75 → F(50) = 96 → F(55) = 126 → F(60) = 169 → F(65) = 232 → F(70) = 325 → F(75) = 462 → F(80) = 667 → F(85) = 972 → F(90) = 1428 → F(95) = 2111.
На последнем шаге:
F(100) = (3 · F(95)) // 2 − 100 // 3 = 6333 // 2 − 33 = 3166 − 33 = 3133.
Скобки существенны: сначала вычисляется произведение 3 · F(n−5), затем оно делится нацело на 2. Операция // отбрасывает дробную часть, а не округляет число до ближайшего целого.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18993.
Верный ответ: 156 507
Число подходит, если в его десятичной записи присутствуют все три цифры: 0, 5 и 7. Порядок цифр и наличие других цифр не имеют значения. Каждая из трёх обязательных цифр должна встретиться хотя бы один раз.
Удобно преобразовать число в строку и проверить вхождение каждой цифры:
with open("zadanie_11_17.txt") as f:
a = [int(x) for x in f]
good = []
for x in a:
text = str(x)
if all(digit in text for digit in "057"):
good.append(x)
print(len(good), min(good))
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19156.
Верный ответ: 2024 1541
Обязательное посещение G5 позволяет разделить маршрут на два независимых участка: A1 → G5 и G5 → J10. На каждом участке применяем обычное динамическое программирование для ходов вправо и вниз: к значению клетки прибавляем максимум или минимум из результатов сверху и слева.
Для участка A1 → G5 получаются максимум 1620 и минимум 1324. Для участка G5 → J10 — максимум 1278 и минимум 1091.
В G5 записано 874. При сложении результатов двух участков это значение учитывается дважды, поэтому вычитаем его один раз:
максимум вычисляется как 1620 + 1278 − 874;
минимум — как 1324 + 1091 − 874. Вычитание обязательно, потому что G5 входит в оба участка.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19211.
Для ответа на задания 19-21 изучите предложенный ниже текст.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня, добавить в кучу три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или больше камней.
Верный ответ: 13
С чего начать. Здесь число S нельзя угадывать проверкой готового ответа. Решаем задачу с конца: сначала определяем, какая позиция позволит Ване закончить игру одним ходом, затем выясняем, каким первым ходом Петя мог оставить такую позицию. Петя получает S + 2, S + 3 или 2S. Чтобы Петя не выиграл сразу, необходимо 2S < 30, значит S ≤ 14. Хуже всего для Вани самый маленький результат Пети — S + 2. Из него Ваня должен суметь выиграть удвоением: 2(S + 2) ≥ 30, откуда S ≥ 13. Первое подходящее целое значение — 13; затем отдельно проверяются остальные два хода Пети.
Проверка и доказательство.
За первый ход Петя может получить S + 2, S + 3 или 2S камней. Требуется, чтобы ни один из этих ходов не завершал игру, но после каждого из них Ваня мог сразу получить не менее 30 камней.
При S = 13 возможны позиции 15, 16 и 26. Они ещё не являются выигрышными для Пети, а Ваня в каждом случае может удвоить число камней и получить соответственно 30, 32 или 52.
При S ≤ 12 Петя может добавить два камня и оставить в куче не более 14. Даже самый сильный ответ Вани — удвоение — даст не более 28 камней. Поэтому гарантированной победы Вани после любого хода Пети ещё нет. Значение 13 является первым, для которого выполняются все требования.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18888.
Верный ответ: 4
С чего начать. Это задание 20, поэтому решаем его обратным ходом.
1. Сначала отмечаем позиции, из которых игрок выигрывает за один ход.
2. Затем ищем опорную проигрышную позицию: игрок, которому досталась такая позиция, сам сразу не выигрывает, но любой его ход приводит к поражению: соперник либо выигрывает следующим ходом, либо особое правило игры сразу засчитывает поражение ходящему.
3. Начальная позиция подходит Пете, если он не может выиграть сразу, но одним ходом переводит Ваню в такую опорную позицию.
Откуда берутся проверяемые S. Из начальной позиции выписываем все формы первого хода, а затем смотрим, какие из них совпадают с опорными позициями. Для этой игры получаются:
• 13: S = 10 ходом +3 или S = 11 ходом +2;
• 14: S = 7 ходом ×2, S = 11 ходом +3 или S = 12 ходом +2;
Именно обратный переход от этих позиций, а не случайный перебор, даёт числа в ответе.
Проверка и доказательство.
Сначала найдём позиции, которые невыгодны игроку, делающему ход. Это 13 и 14 камней: после любого хода из них соперник сразу достигает 30 или больше.
Петя выигрывает вторым ходом, если первым ходом может попасть в 13 или 14, не закончив игру сразу:
S = 7: 7 × 2 = 14;
S = 10: 10 + 3 = 13;
S = 11: 11 + 2 = 13 или 11 + 3 = 14;
S = 12: 12 + 2 = 14.
Из 13 после ходов Вани получаются 15, 16 или 26; Петя удваивает и выигрывает. Из 14 получаются 16, 17 или 28; Петя удваивает 16/17 либо добавляет 2 к 28.
При S = 13 и 14 Петя уже может выиграть первым ходом, поэтому они условию не удовлетворяют. Всего остаются четыре значения.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18889.
Верный ответ: 8 9
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 8, 9. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 8
• Петя: +2 → 10. Ваня не выигрывает сразу, но ходом +3 переводит игру в опорную позицию 13 и гарантирует победу своим следующим ходом.
• Петя: +3 → 11. Ваня не выигрывает сразу, но ходом +2 переводит игру в опорную позицию 13 и гарантирует победу своим следующим ходом.
• Петя: ×2 → 16. Ваня выигрывает сразу: ×2 → 32.
S = 9
• Петя: +2 → 11. Ваня не выигрывает сразу, но ходом +2 переводит игру в опорную позицию 13 и гарантирует победу своим следующим ходом.
• Петя: +3 → 12. Ваня не выигрывает сразу, но ходом +2 переводит игру в опорную позицию 14 и гарантирует победу своим следующим ходом.
• Петя: ×2 → 18. Ваня выигрывает сразу: ×2 → 36.
Проверка и доказательство.
Проверим все первые ходы Пети.
S = 8: Петя может получить 10, 11 или 16. Из 16 Ваня выигрывает сразу удвоением. Позиции 10 и 11 являются выигрышными для Вани за два хода: Ваня переводит их соответственно в 13 или 14, после чего любой ответ Пети оставляет немедленную победу.
S = 9: после ходов Пети получаются 11, 12 или 18. Из 18 Ваня выигрывает сразу, а из 11 и 12 использует стратегию второго хода через позиции 13 или 14.
Ваня не может гарантировать победу первым ходом: например, после перехода 8 → 10 или 9 → 11 сумма ещё слишком мала. Значения 8 и 9 — единственные позиции этого уровня, поэтому они же являются двумя наибольшими.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18890.
Верный ответ: 16
С чего начать. Обозначим через Ti самый ранний момент завершения процесса с ID i. Если процесс независимый, он запускается в момент 0, поэтому Ti равно его собственному времени выполнения. Если процесс зависит от нескольких предшественников, они могут работать параллельно, но новый процесс обязан дождаться самого позднего из них. Поэтому используется правило:
Ti = время процесса i + max(времена завершения всех его предшественников).
Берём максимум, а не сумму: предшественники выполняются одновременно, а не один за другим.
Независимые процессы: T1 = 7, T4 = 3, T7 = 4, T11 = 7.
Вычисляем зависимые процессы:
T2 = T1 + 3 = 10
T3 = T2 + 2 = 12
T5 = T4 + 3 = 6
T6 = T5 + 9 = 15
T8 = T7 + 4 = 8
T9 = T8 + 3 = 11
T10 = max(T5, T8) + 8 = max(6, 8) + 8 = 16
T12 = max(T9, T11) + 3 = max(11, 7) + 3 = 14.
Время завершения всей совокупности — наибольшее из найденных времён:
max(7, 10, 12, 3, 6, 15, 4, 8, 11, 16, 7, 14) = 16.
Критическая цепочка: 7 → 8 → 10. Процесс 10 ждёт процессы 5 и 8; более поздним является процесс 8. Складывать длительности всех процессов нельзя: такой способ ошибочно предполагает, что параллельного выполнения нет.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 21205.
1. Возводит в квадрат
2. Прибавить 2
3. Умножить на 2Сколько существует программ, для которых при исходном числе 2 результатом является число 64 и
при этом траектория вычислений не содержит число 8?
Верный ответ: 99
Обозначим F(n) — число программ, которые переводят 2 в n и не проходят через 8. Число n могло получиться:
• из n − 2 командой «Прибавить 2»;
• из n / 2 командой «Умножить на 2», если n чётно;
• из √n командой «Возвести в квадрат», если n — полный квадрат.
Эти варианты нужно складывать. Даже если две разные команды переводят одно и то же исходное число в один результат, они образуют разные программы. Например, из 2 в 4 можно попасть и умножением на 2, и возведением в квадрат; вместе с путём 2→4 через «+2» это даёт F(4)=3.
Задаём F(2)=1 и F(8)=0, чтобы исключить все траектории через 8. Нечётные числа недостижимы. Последовательно получаем:
F(4)=3, F(6)=3, F(8)=0, F(12)=3, F(16)=6, F(24)=9, F(32)=18, F(36)=27, F(48)=48, F(56)=69, F(60)=81.
Для 64 складываются три возможных последнего шага: из 62 командой «+2» — 81 программа, из 32 командой «×2» — 18 программ, из 8 возведением в квадрат — 0 программ из-за запрета. Поэтому F(64)=81+18+0=99.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18946.
Верный ответ: L 5
Последний символ 0 является признаком конца данных, а не элементом искомой последовательности, поэтому его нужно удалить или прекратить обработку при его появлении.
Во время прохода по строке храним длину текущей серии одинаковых символов. Если новый символ совпадает с предыдущим, серия продолжается и её длина увеличивается. Если символ изменился, начинается новая серия длины 1.
Кроме длины максимальной серии нужно запомнить её символ. Важная деталь: обновлять максимум следует только при строгом условии cur > best. Если использовать >=, более поздняя серия той же длины заменит первую, что противоречит условию.
Пример программы на Python:s = open("zadanie_4_24.txt").read().strip()
s = s[:-1] # удаляем завершающий 0
prev = s[0]
cur = 1
best = 1
best_char = s[0]
for ch in s[1:]:
if ch == prev:
cur += 1
else:
cur = 1
if cur > best:
best = cur
best_char = ch
prev = ch
print(best_char, best)
Строгое сравнение с текущим максимумом не меняет сохранённую серию при равенстве длин, поэтому выбирается именно первое подходящее вхождение.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18974.
Верный ответ:
190062 137280 190066 99294 190075 235724
odd_part совпадают со всеми нечётными делителями исходного числа.get_divisors находит делители попарно до квадратного корня. Если длина полученного списка равна шести, исходное число подходит. Команда sum(odd_divisors) складывает именно эти шесть нечётных делителей.n, а во второй — рассчитанная сумма.from math import isqrt
def get_divisors(n):
divisors = []
for d in range(1, isqrt(n) + 1):
if n % d == 0:
divisors.append(d)
if d * d != n:
divisors.append(n // d)
return divisors
for n in range(190061, 190081):
odd_part = n
while odd_part % 2 == 0:
odd_part //= 2
odd_divisors = get_divisors(odd_part)
if len(odd_divisors) == 6:
print(n, sum(odd_divisors))
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18894.
100 4 80 30 50 40При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
2 50
Верный ответ: 1132 70
1. Максимизируем количество файлов.
Если требуется сохранить как можно больше файлов, сначала нужно рассматривать самые маленькие: замена меньшего файла на больший не может освободить место и увеличить количество. Поэтому размеры сортируем по возрастанию и последовательно складываем.
Сумма 1132 наименьших файлов равна 13 801. Следующий файл имеет размер 51, и 13 801 + 51 = 13 852, что превышает объём диска 13 820. Значит, 1133 файла не помещаются, а 1132 файла поместить можно.
2. Максимизируем размер одного файла при найденном количестве.
Нельзя просто вывести размер 1132-го файла после сортировки: это даст лишь один из возможных наборов, но не наибольший допустимый файл. Оставим 1131 самый маленький файл. Их сумма равна 13 750, поэтому для ещё одного файла остаётся 70 единиц. В исходном наборе есть файл размера 70; любой файл большего размера уже превысит свободный остаток.
Удобная схема программы:
a.sort()
s = 0
k = 0
while k < N and s + a[k] <= S:
s += a[k]
k += 1
base = sum(a[:k - 1])
max_file = max(x for x in a[k - 1:] if base + x <= S)Сортировка по возрастанию отвечает за максимальное количество, а замена последнего файла — за выполнение второго критерия задачи.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18895.
Верный ответ:
Первая строка: 74829, 109831
Вторая строка: 166537, 86699
Что требуется сделать и зачем нужна программа.
Это файловое задание. В поле ответа вводятся только четыре числа, но получить их вручную по сотням строк практически невозможно, поэтому координаты обрабатываются программой. Текст программы в ответ не переносится: он служит инструментом для получения чисел.
Шаг 1. Прочитать координаты.
В каждой непустой строке записаны два вещественных числа. В файле используется десятичная запятая, тогда как функция float в Python ожидает точку. Поэтому строка сначала преобразуется командой replace(",", "."), затем разбивается на две части. Каждая точка хранится как кортеж (x, y).
Шаг 2. Разделить точки на кластеры и аномалии.
График в условии является только иллюстрацией и не показывает данные этого варианта. Сначала полезно построить точечную диаграмму по фактическому файлу в электронной таблице. На ней видны плотные группы и отдельные далёкие точки. После этого выбираются границы в пустых промежутках между группами. Эти границы не вычисляются из H и W и не являются единственно возможными: подходят любые условия, которые дают то же разбиение. Аномалию нельзя присоединять к ближайшему кластеру, потому что по условию она не относится ни к одному из них.
Разбиение именно для этих файлов.
В файле A верхний кластер задаётся условиями x > 0, y > 16, нижний — x > 0, 9 < y < 16. Нижняя граница 9 выбрана так, чтобы не потерять четыре крайние точки второго кластера. В файле B используются три разнесённые прямоугольные области.
В файле A получаются размеры кластеров 105 и 140; две отброшенные точки: (5,4753459; −1,6318432); (−3,8852938; 20,8820432).
В файле B получаются размеры кластеров 101, 96 и 445; три отброшенные точки: (−8,042437762; 26,41164858); (37,92318549; 31,48164858); (2,330782238; −25,24265146).
В программе после разбиения стоят проверки assert. Если граница выбрана неверно и количество точек не совпадёт, программа остановится, а не продолжит вычисления с неправильными кластерами.
Шаг 3. Найти центры кластеров.
Центр из условия — это медоид, то есть одна из исходных точек кластера. Он не равен среднему арифметическому координат. Для каждой точки-кандидата программа складывает расстояния до всех точек того же кластера и выбирает кандидата с минимальной суммой. Расстояние до самой себя равно нулю и на выбор не влияет.
Результаты перебора для файла A:
A1: центр (3,5265948; 20,7685119), минимальная сумма расстояний 138,042311175
A2: центр (6,1700362; 12,3647544), минимальная сумма расстояний 134,893091395.
Результаты перебора для файла B:
B1: центр (12,21724979; 10,31689525), минимальная сумма расстояний 96,002197273
B2: центр (18,21600372; 14,36225718), минимальная сумма расстояний 87,4241707861
B3: центр (19,52793365; 1,3306858), минимальная сумма расстояний 399,310278016.
Шаг 4. Вычислить величины из условия.
В файле A объединяются расстояния A1-центр → точки A2 и A2-центр → точки A1. Минимум 7,48295483501 связан с точкой (6,1614422; 19,8477043), максимум 10,9831514783 — с точкой (7,8249142; 10,6613824).
В файле B средние координаты центров равны Qx = 16,6537290533, Qy = 8,66994607667. Усредняются три центра, а не все 642 рабочих точек.
Как формируется запись ответа.
Функция scale сначала берёт модуль, затем умножает число на 10 000 и применяет int. Это именно взятие целой части, а не математическое округление: использовать round нельзя.
Типичные ошибки.
1) использовать иллюстративный график вместо данных файла; 2) включить аномалию в ближайший кластер; 3) принять средние координаты за центр; 4) сравнить точку с центром чужого кластера при поиске внутреннего радиуса; 5) округлить результат; 6) забыть модуль у координатной величины.
Полная проверенная программа на Python.
Файлы A и B нужно положить в ту же папку, что и программа. Условия разбиения относятся именно к этому варианту.
from math import hypot
def read_points(filename):
points = []
with open(filename, encoding="utf-8-sig") as file:
for line in file:
if line.strip():
x, y = map(float, line.replace(",", ".").split())
points.append((x, y))
return points
def distance(a, b):
return hypot(a[0] - b[0], a[1] - b[1])
def cluster_center(cluster):
# По определению из условия центр обязан быть одной из точек кластера.
best_point = None
best_sum = float("inf")
for candidate in cluster:
current_sum = sum(distance(candidate, p) for p in cluster)
if current_sum < best_sum:
best_sum = current_sum
best_point = candidate
return best_point
def scale(value):
# int после модуля отбрасывает дробную часть, а не округляет.
return int(abs(value) * 10000)
def split_a(points):
clusters = [[], []]
anomalies = []
for p in points:
x, y = p
if x > 0 and y > 16:
clusters[0].append(p)
elif x > 0 and 9 < y < 16:
clusters[1].append(p)
else:
anomalies.append(p)
return clusters, anomalies
def split_b(points):
clusters = [[], [], []]
anomalies = []
for p in points:
x, y = p
if 8 < x < 15 and 5 < y < 13:
clusters[0].append(p)
elif 15 < x < 22 and y > 8:
clusters[1].append(p)
elif 15 < x < 25 and y < 5:
clusters[2].append(p)
else:
anomalies.append(p)
return clusters, anomalies
points_a = read_points("27var09A.txt")
points_b = read_points("27var09B.txt")
clusters_a, anomalies_a = split_a(points_a)
clusters_b, anomalies_b = split_b(points_b)
# Эти проверки сразу обнаружат ошибку в границах разбиения.
assert [len(c) for c in clusters_a] == [105, 140]
assert [len(c) for c in clusters_b] == [101, 96, 445]
assert len(anomalies_a) == 2
assert len(anomalies_b) == 3
centers_a = [cluster_center(cluster) for cluster in clusters_a]
centers_b = [cluster_center(cluster) for cluster in clusters_b]
cross_distances = (
[distance(centers_a[0], p) for p in clusters_a[1]] +
[distance(centers_a[1], p) for p in clusters_a[0]]
)
p1 = min(cross_distances)
p2 = max(cross_distances)
qx = sum(center[0] for center in centers_b) / 3
qy = sum(center[1] for center in centers_b) / 3
print(scale(p1), scale(p2))
print(scale(qx), scale(qy))
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 25538.