1 Ответ
Задание 1. Робот-пылесос
Робот пылесос каждую ночь проводит уборку на территории склада, схему которого вы можете видеть ниже: прямоугольное поле размером w×h разделено на квадратные секции. Зарядная станция робота, с которой он начинает своё движение, расположена в одном из углов склада. На уборку каждой секции робот затрачивает одну минуту, после чего перемещается на соседнюю. К сожалению для уборщика, для удобства хранения товаров склад разделён полками, расположенными «змейкой». Сквозь полки робот пройти не может, поэтому по ходу движения ему приходится проходить через некоторые секции дважды (и дважды там убираться). На рисунке такие секции обозначены звёздочками. По данным w и h определите время, которое робот пылесос затратит на уборку склада.
Ответ = (W — 2)*(H — 2) + W*H
Задание 2. Маскарад
На школьном этапе ВсОШ по технологии участникам было предложено смоделировать и изготовить маску животного. С заданием успешно справились Белла, Захар, Егор и Харитон.
Поскольку тур олимпиады, на котором необходимо защищать проект, довольно продолжителен, для перекуса каждый из ребят принёс свой любимый «лесной» продукт питания: грибы, орехи, ягоды и фрукты. Участникам необходимо представить свою работу: маски медведя, орла, кенгуру и бегемота.
Известно, что: Харитон создал маску животного, впадающего в спячку. Харитон не любит есть грибы и фрукты. Белла и тот, кто принёс с собой орехи, создали маски хищников. Егор создал маску бегемота. Ни грибов, ни ягод у него с собой не было. Тот, кто создал маску орла, принёс с собой ягоды.
Определите, кто какую маску создал и что с собой принёс на перекус.
Животное: Медведь, Орел, Кенгуру, Бегемот
Перекус: Грибы, Орехи, Ягоды, Фрукты
Ответ:
Белла — маска орла, ягоды
Захар — маска кенгуру, грибы
Егор — маска бегемота, фрукты
Харитон — маска медведя, орехи
Задание 3. Разрезание строки
Сегодня на уроке информатики Данила узнал, что слова можно сравнивать в лексикографическом (алфавитном) порядке.
Лексикографический порядок слов это способ их упорядочивания, аналогичный расположению в словаре. Сравнение слов при этом осуществляется по следующим правилам.
Сравнение букв: cначала сравниваются первые символы слов. Слово, первый символ которого стоит раньше в алфавите, считается меньшим. Например, слово «яблоко» будет стоять после слова «груша», потому что «я» стоит позже «г».
Длина слов: если два слова начинаются с одинаковых букв, то дальше сравниваются их символы по порядку. Если одно слово является префиксом другого (например, «кот» и «котёнок»), то более короткое слово считается меньшим, даже если они совпадают до определённой позиции.
Примеры: «собака» < «собачка», «дерево» < «долина», «апельсин» > «ананас». Такая система упорядочивания полезна для сортировки списков слов, поиска и обработки текстовой информации.
В процессе подготовки к олимпиаде по информатике Данила написал на полоске бумаги слово «сириусолимп», разрезал полоску в nn местах и переставил получившиеся куски местами (все получившиеся части исходного слова были использованы). Он мечтает сделать исходный «сириусолимп» как можно большим.
Ответьте на вопросы.
1) Какое наибольшее слово в лексикографическом порядке он может получить при n=1 (то есть сделав единственный разрез)?
2) Какое наибольшее слово в лексикографическом порядке он может получить при n=2?
3) Какое наибольшее слово в лексикографическом порядке он может получить при n=3?
4) Какое наименьшее количество разрезов необходимо сделать, чтобы получить из «сириусолимп» наибольшее лексикографическое слово?
Задание 4. Головоломка с простыми числами
Для освоения темы «Простые числа» учитель математики Николай Николаевич предложил своим ученикам следующую задачу‑головоломку: в клетки таблицы 3×3 нужно расставить произвольные (возможно, повторяющиеся) целые числа от 0 до 10. После этого понадобится подсчитать суммы чисел в каждой из трёх строк и в каждом из трёх столбцов этой таблицы. Среди этих шести сумм нужно найти все простые числа и выписать каждое из них ровно по одному разу (то есть повторяющиеся простые числа не учитываются). Выигрывает тот ученик, у которого полученная сумма различных простых чисел окажется самой большой.
Рассмотрим пример. Один из учеников Николая Николаевича расположил в таблице числа следующим образом:
Среди полученных шести сумм по строкам и столбцам этой таблицы встречаются один раз простое число 3 и три раза простое число 5. Так как в итоге учитываются только различные простые числа, результат этого ученика равен сумме 3+5, то есть 8.
Вам предлагается поучаствовать в решении этой головоломки. Заполните ячейки в таблице целыми числами от 1 до 10. Далее проверяющая программа найдёт все суммы в вашей таблице по строкам и все суммы по столбцам и просуммирует все различные простые числа среди этих шести сумм. Чем больше окажутся значение этой суммы и количество различных простых чисел в ней, тем выше будет оценена попытка.
Замечание
Далее приводится список всех простых чисел, не превосходящих 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Задание 5. Всё могут короли!
Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно.
Задание 6. Натуральный ряд
В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на n-м месте в списке?
Задание 7. Городки
Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.
Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек. В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты.
Если длина палочки является чётным числом d, Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2. Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2(d пополам, округлённое вниз до целой части) и ⌈d2⌉ (d пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший.
Замечание
У Тимофея есть несколько палочек, самая длинная имеет длину 5. Более точно:
Нет палочек длины 1;
Одна палочка длины 2;
Нет палочек длины 3;
Одна палочка длины 4;
Две палочки длины 5.
Тимофей распилит пополам палочку длины 4 и получит две палочки длины 2. Также он распилит обе палочки длины 5 и получит две палочки длины 2 и две палочки длины 3. Вместе с имеющейся у него одной исходной палочкой длины 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2. Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1, которое можно получить из исходного набора, равно двум; палочек длины 3 двум; палочек длины 4 одному; палочек длины 5 двум).