Решайте задания в удобном темпе. Ответы сохраняются в браузере, а результат появится после отправки теста.
Верный ответ: 7
На графе Е — единственная вершина степени 2. В таблице единственный пункт, соединённый ровно с двумя другими, — П6. Значит, Е = П6.
У Е два соседа: Д степени 1 и Г степени 3. Пункт П6 соединён с П1 степени 1 и П2 степени 3, поэтому Д = П1, Г = П2.
У пункта Г есть ещё один тупиковый сосед Ж. Среди соседей П2 таким пунктом является П3: он соединён только с П2. Следовательно, Ж = П3. Дороге Г—Ж соответствует ребро П2—П3, в таблице для него указана длина 7.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18951.
(x≡¬y)→(z≡(y∨w))
Верный ответ: zwyx
Во всех строках значение импликации (x ≡ ¬y) → (z ≡ (y ∨ w)) равно 0. Импликация ложна только при истинном основании и ложном следствии.
Поэтому x ≡ ¬y = 1, то есть x и y противоположны. Одновременно z ≡ (y ∨ w) = 0, значит, z отличается от значения y ∨ w.
Столбцы x и y нельзя выбирать среди пар, где в одной строке уже записаны два нуля. Пары 1–2, 1–3, 1–4 и 2–4 сразу исключаются. Остаются варианты 2–3 и 3–4.
Если x и y располагались бы во втором и третьем столбцах, то при одной ориентации вторая строка нарушила бы условие z ≠ (y ∨ w), а при другой вторая и третья строки после заполнения совпали бы.
Следовательно, третий и четвёртый столбцы — это y и x. В первой строке y = 0, поэтому x = 1; во второй и третьей x = 0, поэтому y = 1. Чтобы следствие было ложным, первый столбец оказывается z = 0, а второй — w. Пропуск в третьей строке заполняется единицей, иначе она совпала бы со второй.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19114.
Верный ответ: 25520
В таблице «Товар» находим товар «Сливки 35% для взбивания»: его артикул — 8. В таблице «Магазин» выбираем магазины Заречного района: M3, M9, M11 и M14.
В таблице «Движение товаров» нужны только строки с типом операции «Продажа», артикулом 8 и датами с 1 по 5 июня включительно. Поступления учитывать нельзя, поскольку они не образуют выручку.
Для каждого из четырёх магазинов 2 июня продано по 29 упаковок по цене 220 руб. Выручка одного магазина: 29 × 220 = 6380 руб. Суммарная выручка: 6380 × 4 = 25520 руб.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18926.
Верный ответ: 20
Известные слова имеют длины 3 и 2, их сумма равна 5. Нужно разместить ещё пять букв.
Коды 011 и 10 оставляют свободными пять трёхразрядных слов: 000, 001, 010, 110 и 111. Все они можно использовать одновременно, и вместе с известными словами условие Фано выполняется.
Сделать добавочную сумму меньше нельзя. На уровне длины 3 имеются ровно пять свободных листьев. Если заменить пару листьев 000 и 001 их более коротким родителем 00 либо пару 110 и 111 их родителем 11, число доступных кодовых слов уменьшится на одно. Чтобы снова получить пять слов, другую ветвь придётся разделить на два слова длины 4, и общая длина не уменьшится.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19116.
Верный ответ: 33
Рассмотрим два случая.
В исходной записи чётное число единиц. Сначала дописывается 1. После этого единиц становится нечётное число, поэтому остаток от деления их количества на 2 равен 1. В конце появляются биты 11, и R = 4N + 3.
В исходной записи нечётное число единиц. Сначала дописывается 0, количество единиц остаётся нечётным, затем дописывается 1. В конце появляются биты 01, и R = 4N + 1.
Для N ≤ 7 результат не превышает 4 · 7 + 3 = 31. Следующее число N = 8 имеет запись 10002 с одной единицей, поэтому дописываются 01:
1000 → 1000012 = 33.
Вопрос требует минимальное возможное R, а не исходное N.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19144.
Верный ответ: 625
До команды Опусти хвост поднят, поэтому первые перемещения только переносят Черепаху в точку A(100; 100) и задают направление под углом −30° к оси Ox. После опускания хвоста каждая команда цикла строит одну сторону длиной 25 и поворачивает на 90°. Через 4 повторения квадрат замыкается; остальные повторения лишь повторно проходят по уже построенным сторонам.
Для проверки целочисленных точек удобно перейти к координатам вдоль сторон квадрата:
u = (√3/2)(x − 100) − (1/2)(y − 100),
v = −(1/2)(x − 100) − (√3/2)(y − 100).
Точка находится строго внутри тогда и только тогда, когда 0 < u < 25 и 0 < v < 25. Перебор целых x и y в ограничивающем прямоугольнике даёт 625 точек; равенства u = 0, u = 25, v = 0 или v = 25 соответствуют границе и не учитываются.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 21188.
Верный ответ: 203125
Подсказка: палитра 225 означает 25 бит на пиксель.
Исходный объём одной фотографии: 2000·1000·25 бит.
Новый объём: 800·700·15 бит.
Экономия для 40 фотографий: (2000·1000·25 − 800·700·15)·40 / 8 / 1024 = 203125 Кбайт.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 25502.
Верный ответ: 1626
Алфавитный порядок букв: А, К, Л, О, Ш. Сначала идут все слова, начинающиеся с А, затем с К, и только после них — слова на Л.
Для каждой фиксированной первой буквы оставшиеся четыре позиции имеют 54 = 625 вариантов. Значит, перед словами на Л расположено 2 · 625 = 1250 слов.
Внутри блока Л**** перед сочетанием ЛО идут блоки ЛА***, ЛК*** и ЛЛ***. В каждом из них три свободные позиции дают 53 = 125 слов, всего 3 · 125 = 375.
Перед первым словом ЛОААА находится 1250 + 375 = 1625 слов, поэтому оно имеет номер 1626.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19201.
Верный ответ: 9
В таблице B соответствует 00:00, поэтому температура в 21:00 находится в столбце W. Среднее за день вычисляется по диапазону B:Y.
Введите во вспомогательный столбец формулу:
=ЕСЛИ(И(МЕСЯЦ(A2)=6;W2>СРЗНАЧ(B2:Y2));1;0)
Единица появляется только в июньской строке, где значение в 21:00 строго выше среднего за сутки. Равенство не подходит, потому что в условии сказано «выше».
Протяните формулу по всем строкам и сложите полученные единицы. Их количество равно 9.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18959.
Верный ответ: 1
Файл содержит первую главу романа. В строку поиска вводим «долг», отключаем учёт регистра и включаем параметр «только слово целиком».
В тексте находится одно вхождение требуемой формы. Другие формы существительного, например «долга», «долгу», «долгами», а также слова вроде «долго» не должны учитываться.
Поэтому искать нужно не часть слова «долг», а именно отдельное слово: иначе редактор может показать лишние совпадения.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19203.
Верный ответ: 1300
Пароль строится из 7 возможных символов. Двух бит недостаточно, так как они дают только 2² = 4 комбинации; трёх бит достаточно, так как 2³ = 8. Значит, один символ занимает 3 бита.
Шесть символов пароля занимают:
6 · 3 = 18 бит.
Два байта содержат только 16 бит, поэтому пароль требует минимально 3 байта.
На одного пользователя хранится 3 байта пароля и 10 байт дополнительных сведений:
3 + 10 = 13 байт.
Для 100 пользователей потребуется 13 · 100 = 1300 байт.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18961.
| 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 | λ, S, q1 | 0, S, q1 | 1, L, q1 |
Верный ответ: 519
В состоянии q1 исполнитель идёт справа налево. Каждый встретившийся справа ноль он заменяет единицей и продолжает движение. При встрече с первой единицей исполнитель записывает вместо неё 0 и останавливается.
Чтобы исходных нулей было как можно больше, единиц должно быть как можно меньше. Полностью нулевая строка не подходит: исполнитель заменил бы все 520 нулей единицами, и после работы нулей не осталось бы. Поэтому оставляем ровно одну единицу, а остальные 519 символов делаем нулями.
Эту единственную единицу можно поставить на 125-ю позицию слева. Тогда 124 нуля слева от неё не будут затронуты, сама единица превратится в ноль, а 395 нулей справа превратятся в единицы. В результате останется ровно 124 + 1 = 125 нулей. Значит, вариант с 519 исходными нулями достижим, а больше быть не может, поскольку хотя бы одна единица необходима.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 25516.
Верный ответ: 26
Маска задаёт сеть 116.29.170.64–116.29.170.95; в ней 32 IP-адреса. В условии сказано именно об IP-адресах сети, поэтому перебираются все адреса, включая адрес сети и широковещательный адрес.
Каждый адрес переводим в 32-битную запись. Срез первых 16 бит соответствует левым двум байтам, последних 16 бит — правым двум. Далее считаем единицы и проверяем условие: left ≥ right.
from ipaddress import ip_network
net = ip_network("116.29.170.89/255.255.255.224", strict=False)
count = 0
for address in net:
bits = f"{int(address):032b}"
left = bits[:16].count("1")
right = bits[16:].count("1")
if left >= right:
count += 1
print(count)
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 21651.
Верный ответ: 13
Преобразуем степени: 97 = 314, а 19 = 2013 = 2 · 32 + 1. Выражение принимает вид 321 + 314 − 2 · 32 − 1.
Для вычитания 2 · 32 занимаем единицу из 14-го разряда: разряды 3–13 становятся равны 2, а во 2-м разряде остаётся 1. Затем при вычитании единицы происходит новое заимствование из 2-го разряда: он становится нулём, а в разрядах 1 и 0 появляются цифры 2.
Получаются 11 двоек в разрядах 3–13 и ещё две в младших разрядах 1 и 0.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18937.
Верный ответ: 8
Формула требует проверки только для пар, у которых первый дизъюнкт ложен, то есть 2x + 7y ≤ 14. Среди этих пар ищем максимум x + y.
Если y = 0, то x ≤ 7 и максимальная сумма равна 7.
Если y = 1, то 2x ≤ 7, поэтому x ≤ 3 и x + y ≤ 4.
Если y = 2, то x = 0 и сумма равна 2. Большие y невозможны.
Следовательно, x + y может достигать 7. Так как требуется строгое неравенство x + y < A, параметр должен быть больше максимума.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19073.
Верный ответ: 839
Условия для чётной и нечётной ветвей применяются только при n ≥ 0. Как только аргумент станет отрицательным, используется первая формула — это базовый случай, останавливающий рекурсию.
Начнём с конца цепочки. Для n = −3:
F(−3) = −(−3) − 5 = −2.
Далее аргумент 1 нечётный:
F(1) = 4 · 1 + F(−3) = 2.
После этого последовательно получаем:
F(5) = 20 + F(1) = 22;
F(9) = 36 + F(5) = 58;
F(13) = 52 + F(9) = 110;
F(17) = 178;
F(21) = 262;
F(25) = 362;
F(29) = 478;
F(33) = 610;
F(37) = 758.
Число 40 чётное, поэтому F(40) = 2 · 40 + 1 + F(37) = 81 + 758 = 839. Отрицательное значение F(−3) не является ошибкой: функция по условию может принимать отрицательные значения.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19128.
Верный ответ: 843 9996
Здесь необходимо проверить все условия, в том числе два разных ограничения на окончание числа.
• x % 10 != 4 — последняя цифра не равна 4;
• x % 100 != 28 — две последние цифры не образуют число 28.
Второе ограничение не заменяет первое: например, число 54 не оканчивается на 28, но должно быть исключено из-за последней цифры 4.
with open("zadanie_10_17.txt") as f:
a = [int(x) for x in f]
good = []
for x in a:
if (x % 6 == 0
and x % 24 != 0
and x % 11 != 0
and x % 10 != 4
and x % 100 != 28):
good.append(x)
print(len(good), max(good))
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19129.
Верный ответ: 472 1208
Конечная клетка J10 пуста, поэтому при входе в неё к сумме прибавляется 0. Для остальных клеток используем динамическое программирование.
Так как разрешены ходы вправо и вниз, в каждую клетку можно прийти сверху или слева. Для минимального результата к значению клетки прибавляем меньший из доступных результатов, для максимального — больший. В первой строке путь идёт только слева, в первом столбце — только сверху.
Из J10 считываем сначала минимальный, затем максимальный результат, как требует условие.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19076.
Для ответа на задания 19-21 изучите предложенный ниже текст.
За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 81. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 81 или больше камней. В начальный момент в первой куче было 13 камней, во второй куче – S камней; 1 ≤ S ≤ 67.
Верный ответ: 17
С чего начать. Здесь число S нельзя угадывать проверкой готового ответа. Решаем задачу с конца: сначала определяем, какая позиция позволит Ване закончить игру одним ходом, затем выясняем, каким первым ходом Петя мог оставить такую позицию. Для минимального S в первую очередь проверяем два последовательных увеличения второй кучи в 2 раза, потому что именно в ней находится неизвестное S. За два хода эта куча станет равна 4·S, поэтому получаем неравенство 13 + 4·S ≥ 81. Отсюда S ≥ (81 − 13)/4, и первое целое значение равно 17. Это и есть источник первого проверяемого числа. Для S = 16 даже такая самая сильная последовательность даёт 13 + 4·16 = 77, что меньше 81. После нахождения границы остаётся проверить, что первый ход Пети ещё не завершает игру.
Проверка и доказательство.
Фраза «после неудачного первого хода Пети» означает, что достаточно найти хотя бы один ход Пети, который ещё не заканчивает игру, но после которого Ваня сразу достигает суммы 81.
При S = 17 Петя может удвоить вторую кучу: (13, 17) → (13, 34). Сумма равна 47, поэтому ход Пети не является победным. Затем Ваня ещё раз удваивает вторую кучу и получает (13, 68), где 13 + 68 = 81.
При S = 16 даже максимально сильная последовательность из двух ходов с удвоением второй кучи даёт 13 + 4 · 16 = 77, что меньше 81. Двойное увеличение первой кучи или сочетание ходов дают ещё меньшую сумму, поэтому при меньшем S такая ситуация невозможна.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18915.
Верный ответ: 27 33
С чего начать. Это задание 20, поэтому решаем его обратным ходом.
1. Сначала отмечаем позиции, из которых игрок выигрывает за один ход.
2. Затем ищем опорную проигрышную позицию: игрок, которому досталась такая позиция, сам сразу не выигрывает, но любой его ход приводит к поражению: соперник либо выигрывает следующим ходом, либо особое правило игры сразу засчитывает поражение ходящему.
3. Начальная позиция подходит Пете, если он не может выиграть сразу, но одним ходом переводит Ваню в такую опорную позицию.
Откуда берутся проверяемые S. Из начальной позиции выписываем все формы первого хода, а затем смотрим, какие из них совпадают с опорными позициями. Для этой игры получаются:
• (26, 27): S = 27, Петя удваивает первую кучу;
• (14, 33): S = 33, Петя прибавляет 1 к первой куче;
Именно обратный переход от этих позиций, а не случайный перебор, даёт числа в ответе.
Проверка и доказательство.
Ищем первый ход Пети в позицию, где Ваня не может избежать победы Пети на следующем ходу.
S = 27. Петя удваивает первую кучу: (13, 27) → (26, 27). Если Ваня прибавит камень, Петя удвоит подходящую кучу; если Ваня удвоит одну из куч, Петя либо ещё раз удвоит первую, либо добавит недостающий камень. Во всех четырёх ответах сумма на следующем ходу Пети достигает 81.
S = 33. Петя добавляет камень в первую кучу: (13, 33) → (14, 33). После прибавлений Вани Петя удваивает вторую кучу; после удвоения первой — удваивает первую; после удвоения второй достаточно прибавить один камень.
Обратный просмотр позиций, из которых любой ход ведёт к немедленной победе соперника, даёт только эти два исходных S. Для них начальная сумма и все ходы Пети ещё меньше 81, поэтому условие запрета победы первым ходом выполнено.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18916.
Верный ответ: 32
С чего начать. В задании 21 первым ходит Петя, а стратегию проверяем для Вани. Используем два типа позиций из предыдущих шагов:
• выигрыш за один ход — Ваня сразу достигает победной границы;
• выигрыш за два хода — Ваня переводит Петю в опорную проигрышную позицию и выигрывает после любого ответа.
Подходящее S должно удовлетворять двум условиям: после каждого первого хода Пети Ваня находится на одном из этих двух уровней, но хотя бы после одного хода Пети Ваня не может выиграть немедленно. Последняя оговорка как раз исключает стратегию гарантированной победы первым ходом.
Полный обратный просмотр даёт набор S: 32. Ни одно число здесь не появляется из готового ответа: мы последовательно проверяем все разрешённые первые ходы Пети.
S = 32
• Петя: +1 к первой куче → (14, 32). Ваня не выигрывает сразу, но ходом +1 ко второй куче переводит игру в опорную позицию (14, 33) и гарантирует победу своим следующим ходом.
• Петя: +1 ко второй куче → (13, 33). Ваня не выигрывает сразу, но ходом +1 к первой куче переводит игру в опорную позицию (14, 33) и гарантирует победу своим следующим ходом.
• Петя: ×2 первую кучу → (26, 32). Ваня выигрывает сразу: ×2 первую кучу → (52, 32).
• Петя: ×2 вторую кучу → (13, 64). Ваня выигрывает сразу: ×2 первую кучу → (26, 64).
Проверка и доказательство.
При S = 32 у Пети четыре возможных хода:
(13, 32) → (14, 32), (13, 33), (26, 32) или (13, 64).
Из двух последних позиций Ваня выигрывает сразу: удваивает подходящую кучу или добавляет недостающий камень. Позиции (14, 32) и (13, 33) являются выигрышными для Вани за два хода: Ваня переводит игру в позицию, где любой ответ Пети открывает немедленную победу.
Значит, при любой игре Пети Ваня выигрывает первым или вторым ходом. Однако после хода Пети в (14, 32) Ваня ещё не может сразу получить 81, поэтому гарантии победы именно первым ходом у него нет.
Обратная классификация позиций даёт единственное подходящее значение S = 32.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18917.
Верный ответ: 18
С чего начать. Обозначим через Ti самый ранний момент завершения процесса с ID i. Если процесс независимый, он запускается в момент 0, поэтому Ti равно его собственному времени выполнения. Если процесс зависит от нескольких предшественников, они могут работать параллельно, но новый процесс обязан дождаться самого позднего из них. Поэтому используется правило:
Ti = время процесса i + max(времена завершения всех его предшественников).
Берём максимум, а не сумму: предшественники выполняются одновременно, а не один за другим.
Независимые процессы: T1 = 3, T2 = 5, T3 = 6, T6 = 2, T9 = 6.
Вычисляем зависимые процессы:
T4 = max(T1, T2, T3) + 4 = max(3, 5, 6) + 4 = 10
T5 = T4 + 8 = 18
T7 = T6 + 3 = 5
T8 = max(T4, T7) + 5 = max(10, 5) + 5 = 15
T10 = max(T8, T9) + 2 = max(15, 6) + 2 = 17
T11 = T9 + 2 = 8
T12 = T11 + 4 = 12.
Время завершения всей совокупности — наибольшее из найденных времён:
max(3, 5, 6, 10, 18, 2, 5, 15, 6, 17, 8, 12) = 18.
Критическая цепочка: 3 → 4 → 5: процесс 3 заканчивается к 6 мс, затем процесс 4 — к 10 мс, а процесс 5 — к 18 мс. Складывать длительности всех процессов нельзя: такой способ ошибочно предполагает, что параллельного выполнения нет.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 21189.
Верный ответ: 13
Разложим числа на простые множители: 8 = 23, 2048 = 211. В конечном числе нет множителя 3. Если хотя бы один раз выполнить команду «Умножить на 3», множитель 3 появится и уже не исчезнет, поскольку все команды только умножают. Поэтому вторую команду использовать нельзя.
Нужно увеличить показатель степени двойки с 3 до 11, то есть набрать ещё 8 единиц показателя.
Команда «×2» увеличивает показатель на 1, а команда «×8» = «×23» увеличивает его на 3. Значит, задача сводится к подсчёту последовательностей шагов 1 и 3 с суммой 8.
Обозначим F(k) количество таких последовательностей с суммой k. Последний шаг равен либо 1, либо 3, поэтому F(k)=F(k−1)+F(k−3), F(0)=1, а для отрицательных индексов значение равно 0.
Получаем F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=4, F(6)=6, F(7)=9, F(8)=13.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19162.
Верный ответ: 6
Считается количество пар AB в одной непрерывной цепочке ABAB...AB. После найденной пары следующая пара такой цепочки должна начинаться ровно через два символа, поэтому при совпадении удобно сразу переходить на две позиции вперёд.
Если в текущей позиции начинается AB, увеличиваем число пар в текущей цепочке. Если пары нет, прежняя цепочка прервана: обнуляем счётчик и сдвигаемся на один символ, чтобы не пропустить возможное начало AB со следующей позиции.
Пример программы на Python:s = open("zadanie_11_24.txt").read().strip()
i = 0
cur = 0
best = 0
while i + 1 < len(s):
if s[i:i + 2] == "AB":
cur += 1
best = max(best, cur)
i += 2
else:
cur = 0
i += 1
print(best)
Например, цепочка ABABAB имеет длину 6 символов, но содержит три требуемые пары, поэтому счётчик увеличивается три раза.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19163.
Верный ответ: 14511924531934621944661954681964691974711984741994781910481191148619124901913499191450119
С чего начать:
Перебираем все числа от 45006 до 50221. В Python правая граница функции range не включается, поэтому в программе указано 50222.
1. Проверяем окончание числа.
Остаток n % 100 равен числу, образованному двумя последними цифрами. Следовательно, условие n % 100 == 19 оставляет только числа, оканчивающиеся цифрами 19.
2. Проверяем простоту.
Функция is_prime ищет делитель от 2 до квадратного корня из числа. Если делитель найден, число составное. Если делителей нет, число простое. Дальше квадратного корня идти не нужно: у делителя больше корня обязательно есть парный делитель меньше корня.
3. Формируем ответ без пробелов.
Счётчик k увеличивается только после нахождения подходящего числа. Выражение str(k) + str(n) склеивает номер и число, а "".join(answer) склеивает все полученные фрагменты без пробелов. Поэтому номер 10 и число 48119 дают фрагмент 1048119.
Пример программы на Python 3:
from math import isqrt
def is_prime(n):
if n < 2:
return False
for d in range(2, isqrt(n) + 1):
if n % d == 0:
return False
return True
answer = []
k = 0
for n in range(45006, 50222):
if n % 100 == 19 and is_prime(n):
k += 1
answer.append(str(k) + str(n))
print("".join(answer))
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19191.
100 4 80 30 50 40Для примера ответ: 2 50.
Верный ответ: 561 50
Сначала ищем максимальное количество.
Чтобы взять как можно больше подарков, коробки сортируют по возрастанию объёма. Если набор из самых маленьких коробок уже не помещается, никакой другой набор того же, большего количества поместиться не сможет: замена маленькой коробки на большую только увеличивает сумму.
Сумма 561 наименьшей коробки равна 7973. Следующая коробка имеет объём 29, и 7973 + 29 = 8002, что больше объёма мешка 8000. Поэтому 562 подарка взять невозможно.
Затем увеличиваем одну коробку, сохраняя количество.
Оставим 560 самых маленьких коробок. Они занимают 7944 единицы, поэтому на последнюю коробку остаётся 56. Среди коробок, которые ещё можно выбрать, максимальный объём, не превышающий 56, равен 50. Именно поэтому нельзя просто вывести объём 561-й коробки после сортировки: требуется найти наибольшую допустимую замену.
Схема программы:
boxes.sort()
s = 0
k = 0
while k < N and s + boxes[k] <= S:
s += boxes[k]
k += 1
base = sum(boxes[:k - 1])
large = max(x for x in boxes[k - 1:] if base + x <= S)Первый цикл отвечает за число подарков, а поиск по оставшимся коробкам — за максимально возможный объём одной из них.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19084.
Верный ответ:
Первая строка: 83354, 110525
Вторая строка: 8580, 9126
Что требуется сделать и зачем нужна программа.
Это файловое задание. В поле ответа вводятся только четыре числа, но получить их вручную по сотням строк практически невозможно, поэтому координаты обрабатываются программой. Текст программы в ответ не переносится: он служит инструментом для получения чисел.
Шаг 1. Прочитать координаты.
В каждой непустой строке записаны два вещественных числа. В файле используется десятичная запятая, тогда как функция float в Python ожидает точку. Поэтому строка сначала преобразуется командой replace(",", "."), затем разбивается на две части. Каждая точка хранится как кортеж (x, y).
Шаг 2. Разделить точки на кластеры и аномалии.
График в условии является только иллюстрацией и не показывает данные этого варианта. Сначала полезно построить точечную диаграмму по фактическому файлу в электронной таблице. На ней видны плотные группы и отдельные далёкие точки. После этого выбираются границы в пустых промежутках между группами. Эти границы не вычисляются из H и W и не являются единственно возможными: подходят любые условия, которые дают то же разбиение. Аномалию нельзя присоединять к ближайшему кластеру, потому что по условию она не относится ни к одному из них.
Разбиение именно для этих файлов.
Для файла A удобно взять пустой промежуток по ординате: при x > 0 точки с y > 16 образуют первый кластер, а точки с 8 < y < 16 — второй. Для файла B две левые группы разделяются горизонталью y = 13, а правая группа отделяется условием x > 20.
В файле A получаются размеры кластеров 105 и 137; две отброшенные точки: (5,4752859; −1,6318562); (−3,8852938; 20,8820432).
В файле B получаются размеры кластеров 90, 131 и 413; три отброшенные точки: (5,750393691; −19,87762839); (−4,581906309; 27,63585695); (43,79354536; 32,68585695).
В программе после разбиения стоят проверки assert. Если граница выбрана неверно и количество точек не совпадёт, программа остановится, а не продолжит вычисления с неправильными кластерами.
Шаг 3. Найти центры кластеров.
Центр из условия — это медоид, то есть одна из исходных точек кластера. Он не равен среднему арифметическому координат. Для каждой точки-кандидата программа складывает расстояния до всех точек того же кластера и выбирает кандидата с минимальной суммой. Расстояние до самой себя равно нулю и на выбор не влияет.
Результаты перебора для файла A:
A1: центр (3,5503069; 20,8538382), минимальная сумма расстояний 96,6817145607
A2: центр (5,3739419; 11,5495491), минимальная сумма расстояний 135,04416666.
Результаты перебора для файла B:
B1: центр (15,30318943; 16,33599059), минимальная сумма расстояний 76,3669284304
B2: центр (15,68022687; 9,183039895), минимальная сумма расстояний 108,2422899
B3: центр (25,80675038; 6,369569856), минимальная сумма расстояний 376,02095337.
Шаг 4. Вычислить величины из условия.
Для P1 и P2 рассматриваются оба направления: расстояния от центра A1 до всех точек A2 и от центра A2 до всех точек A1. Иначе часть допустимых расстояний будет потеряна.
Минимум 8,33543858749 получается для центра A2 и точки (6,1614422; 19,8477043) из A1. Максимум 11,052530154 получается для центра A1 и точки (7,8249142; 10,6613824) из A2.
В файле B минимальный кластер — B1 (90 точек), максимальный — B3 (413 точек). Для первого сумма расстояний равна 76,3669284304, поэтому Q1 = 76,3669284304 / 89 = 0,858055375622. Для второго Q2 = 376,02095337 / 412 = 0,912672216917. Делитель уменьшается на единицу, потому что нулевое расстояние от центра до себя не учитывается.
Как формируется запись ответа.
Функция 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 8 < 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 10 < x < 20 and y > 13:
clusters[0].append(p)
elif 10 < x < 20 and y < 13:
clusters[1].append(p)
elif x > 20 and y < 12:
clusters[2].append(p)
else:
anomalies.append(p)
return clusters, anomalies
points_a = read_points("27var01A.txt")
points_b = read_points("27var01B.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, 137]
assert [len(c) for c in clusters_b] == [90, 131, 413]
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]
# Файл A: расстояния от центра одного кластера до точек другого.
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)
# Файл B: средние для наименьшего и наибольшего кластеров.
sizes_b = [len(cluster) for cluster in clusters_b]
i_min = min(range(3), key=lambda i: sizes_b[i])
i_max = max(range(3), key=lambda i: sizes_b[i])
def average_distance_without_center(center, cluster):
total = sum(distance(center, p) for p in cluster)
return total / (len(cluster) - 1)
q1 = average_distance_without_center(centers_b[i_min], clusters_b[i_min])
q2 = average_distance_without_center(centers_b[i_max], clusters_b[i_max])
print(scale(p1), scale(p2))
print(scale(q1), scale(q2))
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 25530.