1 Ответ
1. Даны пять коробок, пронумерованных от 1 до 5. В каждой из них лежит карточка с одной буквой из пяти: А, Б, В, Г, Д.
За один ход можно поменять местами содержимое двух любых коробок. Например, запись 13 означает: «взять листок из 1-й коробки и поменять его с листком из 3-й». Составьте последовательность таких операций, чтобы в итоге буквы в коробках располагались в алфавитном порядке: в первой коробке — А, во второй — Б, в третьей — В, в четвёртой — Г, а в пятой — Д. Чем меньше операций вам потребуется, тем больше баллов вы получите. Рассмотрим пример. Пусть у нас всего три коробки, и буквы в них лежат в таком порядке: В, А, Б. Чтобы расставить их по алфавиту (А, Б, В), можно сделать два действия:
Сначала меняем местами 1-ю и 2-ю коробки (12). Получится А, В, Б.
Затем меняем местами 2-ю и 3-ю коробки (23). Получится А, Б, В.
Ответ для этого примера: 12 23
Ответ: 14 25 34
2. Аня, Боря, Вера, Глеб, Даша и Егор встали в один ряд для школьной фотографии. Фотограф сделал первый снимок. Затем один из школьников, который стоял не первым слева, вышел из ряда и встал на левый край, перед всеми остальными. Остальные сохранили свой взаимный порядок. Фотограф сделал второй снимок. Снимки потерялись, но помощник фотографа запомнил несколько подробностей. На первом снимке:
между Аней и Глебом стоял ровно один человек;
Аня стояла левее Глеба;
Даша стояла с краю.
На втором снимке:
Боря и Егор стояли рядом;
Боря и Даша стояли рядом;
Даша стояла левее Егора;
Вера и Егор стояли рядом.
Все воспоминания помощника верны. Слово «рядом» означает, что между ребятами никто не стоял; «с краю» — на первом или последнем месте. Лево и право определяются с точки зрения фотографа.
В каком порядке слева направо стояли ребята на первом снимке?
В каком порядке слева направо стояли ребята на втором снимке?
Кто перешёл на левый край?
Аня
Боря
Вера
Глеб
Даша
Егор
Ответ: первый снимок — Даша, Боря, Егор, Аня, Вера, Глеб; второй снимок — Аня, Даша, Боря, Егор, Вера, Глеб; на левый край перешла Аня
3. Глеб придумал способ короче записывать строки из букв. Если один и тот же фрагмент повторяется несколько раз подряд, его можно записать один раз в скобках, а перед скобками указать количество повторений. Например, запись 4(аб) означает абабабаб, а запись 6(а)б — ааааааб. В одной записи можно использовать несколько таких блоков и обычные буквы. Запись читается слева направо: обычные буквы переписываются без изменений, а каждый блок заменяется указанным количеством копий фрагмента. В результате должна получиться в точности исходная строка. Внутри скобок записывается одна или несколько букв. Скобки внутри скобок использовать нельзя. Количество повторений не может быть меньше 2. Длина записи — количество всех её символов без пробелов. Каждая буква, каждая цифра и каждая скобка считаются за один символ. Например, длина записи 6(а)б равна 5. Запишите каждую из следующих строк как можно короче.
аааааааа
абабабабаб
абабабвабабабв
аааааааабааааааааб
абабабабабвабвабвабв
Ответ: 1) 8(а); 2) 5(аб); 3) 2(абабабв); 4) 8(а)б8(а)б; 5) 4(аб)4(абв)
4. У фотографа на карте памяти осталось место для n снимков. Он хочет использовать всю оставшуюся память, чтобы сфотографировать участок стены длиной d сантиметров и объединить снимки в панораму. Каждый снимок охватывает участок стены длиной k сантиметров. Фотограф делает ровно n снимков слева направо: каждый следующий снимок смещён вправо относительно предыдущего. Все соседние снимки должны перекрываться на одинаковую ширину. Первый снимок начинается у левого края участка, а последний заканчивается у правого края. Снимки не должны выходить за границы участка. Запишите формулу, которая по значениям n, k и d вычисляет ширину пересечения соседних снимков в сантиметрах.
Приведённая формула показывает только допустимую форму записи и не является правильным ответом на задачу.
Ответ: (n * k — d)/(n — 1)
5. На панели расположены 8 ламп, пронумерованных слева направо от 1 до 8. Для каждого сигнала от A до G в таблице указано состояние исправной панели. Оно записывается строкой из восьми нулей и единиц: i-й символ слева соответствует лампе с номером i; 1 означает, что она горит, а 0 — что не горит. После ремонта провода двух ламп перепутали местами: каждая получает команду, предназначенную для другой. Ещё одна лампа работает наоборот: горит, когда должна быть выключена, и не горит, когда должна быть включена. Эти три лампы различны, остальные исправны. Характер поломок не меняется при переключении сигналов.
Сигнал Состояние
A 01110100
B 10100101
С 11010001
D 10110100
E 11100010
F 00011011
G 11001001
При сигнале A панель показала 00111110. Сколькими способами можно выбрать пару ламп с перепутанными проводами и третью лампу, работающую наоборот, чтобы получилось это состояние? Порядок ламп в паре не учитывается.
Какие сигналы не позволят различить варианты из предыдущего вопроса?
При том же расположении неисправностей дополнительно проверили сигнал E. Панель показала 11101010. Определите номера двух ламп с перепутанными проводами: _____ и _____. Определите номер лампы, работающей наоборот: _____.
Ответ: количество способов — 2; не позволяют различить варианты сигналы C и F; перепутаны провода ламп 2 и 7; наоборот работает лампа 5
6. Астрономы получили набор радиосигналов из одного участка неба. Для каждого сигнала удалось определить его частоту. Для подсчёта различных источников сигналы располагают в порядке возрастания частоты. Соседние в этом ряду сигналы считают принадлежащими одному источнику, если разность их частот не превосходит k. Если разность больше k, то между этими сигналами проходит граница между двумя источниками. При этом разность между наименьшей и наибольшей частотами одного источника может быть больше k. Например, при k = 5 сигналы с частотами 101, 103, 108, 120, 122, 125 относятся к двум источникам: первому принадлежат сигналы 101, 103, 108, а второму — 120, 122, 125.
Чему равна разность между наибольшей и наименьшей частотами зарегистрированных сигналов?
Чему равна наибольшая разность частот двух соседних сигналов после расположения всех сигналов в порядке возрастания частоты?
Сколько различных источников было обнаружено при k = 5?
Предположим, что значение k изменяется. Какое наименьшее целое значение k нужно выбрать, чтобы все зарегистрированные сигналы относились не более чем к десяти различным источникам?
Пусть k = 10. Какое наибольшее количество сигналов было получено от одного источника?
Ответ: 1) 3739; 2) 61; 3) 56; 4) 30; 5) 71
7. Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В древнем Китае для измерения времени использовали водяные часы — лоуху. В нижнем сосуде часов изначально находится v миллилитров воды. Каждые a секунд, то есть в моменты времени a, 2a, 3a, …, в сосуд поступает 1 миллилитр воды. Каждые b секунд, то есть в моменты времени b, 2b, 3b, …, из сосуда вытекает 1 миллилитр воды. Если поступление и вытекание происходят одновременно, объём воды в этот момент не изменяется. Определите, сколько миллилитров воды будет в сосуде через n секунд. События, происходящие ровно в момент n, также должны быть учтены. Гарантируется, что воды в сосуде достаточно для всех вытеканий до момента n, даже если не учитывать поступления новой воды.
Ответ:
import sys
v, a, b, n = map(int, sys.stdin.read().split())
print(v + n // a — n // b)
8. Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Склад службы доставки находится в точке 0 на прямой дороге. Два посёлка находятся в точках x и y. Положительные и отрицательные координаты соответствуют разным направлениям от склада. Все координаты измеряются в километрах, расстояние между точками с координатами u и v равно |u − v|. В посёлок с координатой x нужно доставить контейнер массой a, а в посёлок с координатой y — контейнер массой b. Для доставки используется дрон. За один рейс он может перевезти груз суммарной массой не более m килограммов и пролететь не более d километров. Каждый рейс начинается и заканчивается на складе. Все контейнеры, доставляемые за один рейс, загружаются в дрон перед вылетом. Во время рейса дрон не может брать на складе дополнительные контейнеры или заряжаться, даже если его маршрут снова проходит через склад. Перед новым рейсом дрон полностью заряжается. За один рейс дрон может доставить один контейнер или оба контейнера, посетив посёлки в любом порядке. Определите минимальное количество рейсов, необходимое для доставки обоих контейнеров. Если выполнить доставку невозможно, выведите −1.
Ответ:
import sys
x, y, a, b, m, d = map(int, sys.stdin.read().split())
if a > m or b > m or 2 * abs(x) > d or 2 * abs(y) > d:
print(-1)
elif a + b <= m and abs(x) + abs(x — y) + abs(y) <= d:
print(1)
else:
print(2)
9. Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Садовник хочет разбить прямоугольную клумбу и огородить её по периметру. Для клумбы он может выделить не более s квадратных метров земли и использовать не более p метров ограждения. Длины сторон клумбы a и b, измеренные в метрах, должны быть натуральными числами. Поэтому выбранный размер клумбы подходит, если одновременно выполняются условия ab ⩽ s, 2(a + b) ⩽ p. Два размера считаются одинаковыми, если соответствующие клумбы совпадают после поворота. В частности, размеры a × b и b × a считаются одинаковыми. Сколько существует различных размеров подходящей клумбы?
Ответ:
from math import isqrt
s = int(input())
p = int(input())
h = p // 2
top = min(isqrt(s), h // 2)
lo, hi = 0, top
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * (h — mid) <= s:
lo = mid
else:
hi = mid — 1
k = lo
count = k * (h + 1) — k * (k + 1)
count += sum(s // a for a in range(k + 1, top + 1))
count -= (top — 1) * top // 2 — (k — 1) * k // 2
print(count)
