Задача 3. Чаепитие
ответСлон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай.
Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч». Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при расстановке предметов «ВЧХВ» на подготовку стола потребуются три секунды. Предметы, которые переставляются местами каждую секунду, подчёркнуты.
- ВХЧВ
- ХВЧВ
- ХВВЧ
Слон торопится, и поэтому хочет знать, при какой первоначальной расстановке предметов у него уйдёт наибольшее время на подготовку стола.
Вам нужно дать ответ для четырёх случаев: когда на столе у Семёна стоит 3, 6, 7 и 8 предметов. Для каждого из этих случаев вы должны записать в ответе строку, состоящую из необходимого количества букв, каждая буква должна быть одной из букв «Х», «В», «Ч». Количество предметов каждого вида вы можете выбрать самостоятельно, но общее число букв в ответе должно быть равно 3, 6, 7 и 8. Вы должны найти такую расстановку предметов, при которой подготовка стола займёт наибольшее время для данного числа предметов.
В ответе напишите четыре строки: в первой строке ответ для 3 предметов, во второй строке — для 6 предметов, в третьей строке — для 7 предметов, в четвёртой строке — для 8 предметов. Вы должны записать в ответе 4 строки, если вы не можете найти ответ для какого-то случая, напишите любую строку из букв «Х», «В», «Ч» нужной длины.
Ответ на Задачу 3.
Для чаепития необходима такая расстановка предметов: Х, ..., Х, В, ..., В, Ч, ... Ч. Нам необходимо получить перестановку предметов, для которой получение такой последовательности потребовало бы как можно больше операций. Поэтому в ответе не могут идти буквы Х и В подряд, иначе, переставив их местами, мы получим большее число операций. Также подряд не могут идти буквы В и Ч. То есть ответ всегда имеет вид Ч, ..., Ч, В, ..., В, Х, ..., Х. Осталось только понять, сколько нужно взять чая, варенья и хлеба в ответе.
Пусть в ответе чай встречается x раз, варенье встречается y раз, хлеб встречается z раз, x + y + z = n. Посчитаем количество секунд, необходимых для приведения такой перестановки в порядок. Нам придётся поменять местами каждую порцию чая и варенья, это займёт xy секунд. Аналогично понадобится yz секунд, чтобы поменять варенье и хлеб и xz секунд, чтобы поменять чай и хлеб. Нужно подобрать такие значения x, y, z, чтобы сумма xy + yz + xz была максимальной.
Интуитивно понятно, что числа должны быть равны или близки (отличаться на 1). Докажем это. Пусть, например, числа x и y отличаются на 2 и более, то есть x ≥ y + 2. Рассмотрим новую последовательность, в которой x будет на 1 меньше, а y увеличим на 1. Тогда для новой последовательности ответ равен (x − 1)(y + 1) + (x − 1)z + (y + 1)z = xy + x − y − 1 + xz + yz, то есть ответ изменится на x − y − 1, и если x − y > 2, то продолжительность увеличится. Таким образом, в правильном ответе среди чисел x, y, z не должно быть различающихся на 2 и более.
Итак, если n делится на 3, то необходимо взять x = y = z = n/3. Если n не делится на 3, то одно или два из этих чисел нужно увеличить на 1, в зависимости от остатка от деления n на 3.
Возможный правильный ответ:
ЧВХ ЧЧВВХХ ЧЧВВХХХ ЧЧЧВВХХХ
