Олимпиада по информатике

1. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ
2. ПО ИНФОРМАТИКЕ
3. 2018-2019 УЧЕБНЫЙ ГОД
5. ЗАДАНИЕ 5 КЛАСС

1. В доме девять этажей, но лифт сломался, и теперь в нём работают только две кнопки. Нажатие на первую кнопку приводит к тому, что лифт поднимается на пять этажей вверх, а при нажатии на вторую кнопку лифт спускается на три этажа вниз. Подниматься выше девятого этажа или спускаться ниже первого этажа нельзя, ходить по лестнице тоже нельзя. Как подняться с первого этажа на девятый?

2. В игре «Камень, ножницы, бумага» двое игроков одновременно показывают при помощи руки один из трёх условных символов – «камень», «ножницы» или «бумага». Игрок выигрывает, если он показал камень, а его противник – ножницы («камень тупит ножницы»), если он показал ножницы, а его противник – бумагу («ножницы режут бумагу»), если он показал бумагу, а его противник – камень («бумага накрывает камень»). Если два игрока показали одинаковые символы, то игра заканчивается вничью.

Алёша и Боря сыграли в эту игру девять раз. Алёша два раза показал камень, три раза – ножницы, четыре раза – бумагу. Боря три раза показал камень, четыре раза – ножницы, два раза – бумагу, но порядок, в котором они показывали эти символы, неизвестен. Определите, какое наибольшее число раз мог выиграть Алёша. А какое наибольшее число раз мог выиграть Боря? Объясните свой ответ.

1. Три вора – Камнев, Ножницын и Бумагин хотят переправиться через реку. У каждого вора два больших баула. В лодке три места, одно место занимает один человек или один баул. Грести умеет только Камнев. При этом если Камнев останется в лодке или на берегу с баулом Ножницына и Ножницына не будет рядом, то Камнев обчистит баул Ножницына. Аналогично Ножницын обчистит баул Бумагина в его отсутствие, а Бумагин обчистит баул Каменева в его отсутствие. Как им переправиться на другой берег? Опишите алгоритм их действий.

2. Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 10, при этом число гирек в наборе должно быть как можно меньше. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться. Объясните, как любую массу от 1 до 10 граммов можно взвесить при помощи предложенного набора.

3. Вам нужно умножить некоторое большое число X на 15. У вас есть калькулятор, но на калькуляторе сломались все кнопки операций, кроме сложения. Поэтому вы можете только складывать разные числа (например, можно сложить число X и число X, тогда получится 2X, затем можно сложить число 2X и 2X и получится 4X, а можно сложить 2X и X и получится 3X, то есть можно складывать любые ранее полученные числа между собой). Определите, при помощи какого минимального числа сложений можно получить число 15X. Приведите последовательность операций, при помощи которых можно получить число 15X за указанное число сложений.

1. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
2. ПО ИНФОРМАТИКЕ
3. 2018-2019 УЧЕБНЫЙ ГОД
4. ЗАДАНИЕ 6 КЛАСС

1. В доме девять этажей, но лифт сломался, и теперь в нём работают только две кнопки. Нажатие на первую кнопку приводит к тому, что лифт поднимается на пять этажей вверх, а при нажатии на вторую кнопку лифт спускается на три этажа вниз. Подниматься выше девятого этажа или спускаться ниже первого этажа нельзя, ходить по лестнице тоже нельзя. Как подняться с первого этажа на девятый?

2. В игре «Камень, ножницы, бумага» двое игроков одновременно показывают при помощи руки один из трёх условных символов – «камень», «ножницы» или «бумага». Игрок выигрывает, если он показал камень, а его противник – ножницы («камень тупит ножницы»), если он показал ножницы, а его противник – бумагу («ножницы режут бумагу»), если он показал бумагу, а его противник – камень («бумага накрывает камень»). Если два игрока показали одинаковые символы, то игра заканчивается вничью.

Алёша и Боря сыграли в эту игру девять раз. Алёша два раза показал камень, три раза – ножницы, четыре раза – бумагу. Боря три раза показал камень, четыре раза – ножницы, два раза – бумагу, но порядок, в котором они показывали эти символы, неизвестен. Также известно, что игра ни разу не закончилась вничью. Определите, какое наибольшее число раз мог выиграть Алёша. А какое наибольшее число раз мог выиграть Боря? Объясните свой ответ.

1. Три вора – Камнев, Ножницын и Бумагин хотят переправиться через реку. У каждого вора два больших баула. В лодке три места, одно место занимает один человек или один баул. Грести умеет только Камнев. При этом если Камнев останется в лодке или на берегу с баулом Ножницына и Ножницына не будет рядом, то Камнев обчистит баул Ножницына. Аналогично Ножницын обчистит баул Бумагина в его отсутствие, а Бумагин обчистит баул Каменева в его отсутствие. Как им переправиться на другой берег? Опишите алгоритм их действий.

2. Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 20, при этом число гирек в наборе должно быть как можно меньше. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться. Объясните, как любую массу от 1 до 20 граммов можно взвесить при помощи предложенного набора.

3. Вам нужно умножить некоторое большое число X на 27. У вас есть калькулятор, но на калькуляторе сломались все кнопки операций, кроме сложения. Поэтому вы можете только складывать разные числа (например, можно сложить число X и число X, тогда получится 2X, затем можно сложить число 2X и 2X и получится 4X, а можно сложить 2X и X и получится 3X, то есть можно складывать любые ранее полученные числа между собой). Определите, при помощи какого минимального числа сложений можно получить число 27X. Приведите последовательность операций, при помощи которых можно получить число 27X за указанное число сложений.

1. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
2. ПО ИНФОРМАТИКЕ
3. 2018-2019 УЧЕБНЫЙ ГОД
5. ЗАДАНИЕ 7 – 8 КЛАССЫ

Каждая задача оценивается в 10 баллов. Итоговый балл выставляется как сумма баллов за 4 задачи с лучшим результатом (то есть для получения максимального балла нужно решить 4 любые задачи). Вы можете отправить на проверку не более 5 решений суммарно по всем задачам 1–5.

В задачах 1–4 оценивается последнее решение, которое было принято на проверку.

1. Задача 1. Спиральная дорожка (10 баллов)

Лужайка в парке имеет форму прямоугольника размером a × b метров, разбитого на квадраты со стороной 1 метр. Необходимо поставить внутри лужайки ограждения между некоторыми квадратами так, чтобы образовалась спиральная дорожка, закручивающаяся к центру лужайки. Определите длину такого ограждения.

На рисунке изображена лужайка размером 4 × 6 и ограждение, которое необходимо поставить на ней. Длина ограждения для такой лужайки будет равна 15.

Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные a и b (записываемые английскими буквами), операции сложения (обозначается «+»), вычитания (обозначается «−»), умножения (обозначается «*»), деления (обозначается «/») и круглые скобки для изменения порядка действий. Запись вида «2a» для обозначения произведения числа 2 и переменной a неверная, нужно писать «2 * a».

Пример правильного (по форме записи) выражения: a + (b − a) * 2.

1. Задача 2. Книжная полка (10 баллов)

В библиотеке на полке стоят 8 томов полного собрания сочинений одного писателя. Библиотекарь обозначил их латинскими буквами от A до H в порядке выхода томов.

Получилась следующая последовательность:

1. E D G H C B F A

Библиотекарь решил переставить эти книги так, чтобы они шли по порядку: A, B, C, D, E, F, G, H. За одно действие библиотекарь может взять несколько подряд идущих книг, достать их с полки и, не меняя порядок следования книг, перевернуть их и поставить на место в обратном порядке. Например, если библиотекарь достанет книги с H по F и перевернёт их, то новый порядок следования книг будет таким: E, D, G, F, B, C, H, A.

Помогите библиотекарю упорядочить этот ряд книг за минимальное число действий. То, что некоторые книги окажутся перевёрнутыми вверх ногами, библиотекарю не важно.

Ответом на эту задачу является последовательность операций. Одна операция записывается в одной строке. Описание каждой операции состоит из двух латинских букв (от A до H), которые являются обозначениями крайних томов в переворачиваемом фрагменте, например, выше был рассмотрен пример для операции «H F».

Чем меньше операций будет в вашем алгоритме, тем больше баллов вы получите, при условии, что в результате применения вашего алгоритма тома будут расставлены по порядку от A до H.

1. Задача 3. Гирьки (10 баллов)

Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 40. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться.

Например, при помощи трёх гирек массами 1, 1 и 5 граммов можно отмерить любую целочисленную массу от 1 до 7 граммов по следующей схеме (x – взвешиваемая масса):

1. грамм: x = 1,

2. грамма: x = 1 + 1,

3. грамма: x + 1 + 1 = 5,

4. грамма: x + 1 = 5,

5. граммов: x = 5, 6 граммов: x = 5 + 1, 7 граммов: x = 5 + 1 + 1.

Ответом на эту задачу являются несколько целых чисел, записанных через пробел, – массы гирек, при помощи которых можно отмерить любую целочисленную массу от 1 до 40. В наборе должно быть не более 8 чисел. Числа в наборе могут повторяться. Чем меньше гирек будет в предложенном наборе, тем больше баллов вы получите, при условии, что, используя гирьки из данного набора, можно отмерить каждую целочисленную массу от 1 до 40.

1. Задача 4. Возведение в степень (10 баллов)

Вы хотите возвести данное число a в некоторую целочисленную степень n, но ваш калькулятор умеет только перемножать числа. Например, вы можете вычислить a² = a × a, затем вы можете вычислить a³ = a² × a или a⁴ = a² × a².

Вы можете по-разному организовать вычисление значения aⁿ. Например, вычислить a⁵ можно за 4 умножения:

1. a² = a × a,

2. a³ = a² × a,

3. a⁴ = a³ × a, 4) a⁵ = a⁴ × a.

Но можно вычислить a⁵ всего лишь за 3 умножения:

1) a² = a × a,

2) a³ = a²×a,

3) a⁵ =a³×a².

Вам необходимо определить, за какое минимальное число умножений можно вычислить следующие степени: 7, 15, 23, 63. Вычисление каждой из этих степеней должно быть независимо от остальных, то есть при вычислении 15-й степени нельзя использовать вычисления, проделанные ранее для вычисления 7-й степени. Вы решаете четыре независимые задачи – за какое минимальное число умножений можно вычислить 7-ю степень, 15-ю степень, 23-ю степень и 63-ю степень.

Ответ на это задание записывается в четырёх строках. Каждая строка должна содержать последовательность вычисления каждой из указанных степеней. Первая строка должна содержать последовательность вычисления 7-й степени, вторая строка – 15-й степени, третья строка – 23-й степени, четвертая строка – 63-й степени.

Каждая строка содержит через пробел несколько целых чисел – значения степеней в том порядке, в котором они вычисляются. Например, для вычисления 5-й степени решение можно записать в виде строки

2 3 5

или

2 4 5, что означает, что последовательно вычисляются степени a², a³, a⁵ (одно возможное решение) или a², a⁴, a⁵ (другое возможное решение). Такм образом, каждая строка должна начинаться числом 2, а заканчиваться тем значением степени, которое нужно вычислить (7, 15, 23, 63).

Чем меньше операций умножения вы будете использовать, тем больше баллов вы получите, при условии, что предложенные последовательности вычисления степеней являются корректными.

1. Задания по программированию

Решением задач 5–7 является программа, написанная на одном из языков программирования.

Задачи 5–7 необязательно решать для получения полного балла.

Ограничение по времени работы программы в задачах 5–7: 1 секунда.

Решения задач 5–7 оцениваются, только если они выдают правильный ответ на всех примерах входных и выходных данных, приведённых в условии задачи. Проверка решений производится сразу же после отправки, по каждой задаче оценивается решение, набравшее наибольшее число баллов. На странице «Итог» вы можете видеть окончательный балл по всем задачам.

Программа не должна выводить никаких иных сообщений, кроме того, что требуется найти в задаче. Во всех задачах целые числа во входных и выходных данных записываются только цифрами (то есть недопустимо использование записи 1000000.0 или 1e+6 вместо числа 1000000). Каждое число во входных данных записано в отдельной строке.

1. Задача 5. Спиннеры

Спиннер – модная игрушка c подшипником в основании, к которому прикреплены лопасти. Афанасий открыл бизнес по производству спиннеров. Он выяснил, что за спиннер, у которого N лопастей, покупатели готовы платить A + B × N рублей, но при этом покупатель не станет покупать спиннер, если его цена будет выше C рублей. Определите максимальное число лопастей спиннера, который согласится приобрести покупатель.

Программа получает на вход три числа A, B, C (стоимость основания спиннера, стоимость одной лопасти и максимальная стоимость всего спиннера). Все числа – целые положительные, не превосходящие 2×10⁹ , при этом A ≤ C.

Программа должна вывести одно число – максимальное число лопастей спиннера.

1. Пример входных и выходных данных

   Ввод	Вывод	Примечание
   20 10 55	3	Спиннер с 3 лопастями будет стоить 50 рублей, а с 4 лопастями – 60 рублей. Максимальная возможная стоимость спиннера – 55 рублей, поэтому максимальное число лопастей равно 3.

2. Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 60 баллов.

1. Примеры оформления решения задачи

Ниже даны примеры ввода и вывода данных к этой задаче на нескольких языках программирования. Выберите один из языков программирования, допишите соответствующую программу и отправьте её на проверку с использованием одного из допустимых компиляторов.

1. Задача 6. Снова спиннеры

Денис тоже решил заняться производством и продажей спиннеров, но он считает, что у спиннера может быть только три или четыре лопасти. У него есть ровно M лопастей, которые он может прикреплять к основаниям, и неограниченный запас оснований. Он хочет изготовить несколько трёхлопастных и несколько четырёхлопастных спиннеров так, чтобы использовать все M лопастей. Определите, сколько спиннеров каждого вида он должен произвести.

Программа получает на вход одно целое положительное число M, не превосходящее 2×10⁹ , – количество лопастей, которое есть у Дениса.

Программа должна вывести два целых числа – количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть несколько решений, нужно вывести любое из них. Если Денис не может использовать ровно M лопастей для производства спиннеров, программа должна вывести два числа 0.

1. Примеры входных и выходных данных

1. Система оценивания

Решение, правильно работающее только для случаев, когда M не превосходит 100, будет оцениваться в 60 баллов.

1. Задача 7. Не про спиннеры

Саша совсем не любит спиннеры, поэтому он рисует в тетрадке. Он взял тетрадный лист из N × M клеточек и пронумеровал все клетки различными числами. Теперь ему стало интересно, сколько различных прямоугольников он может вырезать из этого листа бумаги по границам клеточек.

Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.

Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).

1. Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 10, будет оцениваться в 40 балла.

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 200, будет оцениваться в 70 баллов.

2. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
3. ПО ИНФОРМАТИКЕ
4. 2018-2019 УЧЕБНЫЙ ГОД
6. ЗАДАНИЕ 9 – 11 КЛАССЫ

Ограничение по времени работы программы в каждой задаче – 1 секунда.

Решения оцениваются, только если они выдают правильный ответ на всех примерах входных и выходных данных, приведённых в условии задачи.

Программа не должна выводить никаких иных сообщений, кроме того, что требуется найти в задаче. Во всех задачах целые числа во входных и выходных данных записываются только цифрами (то есть недопустимо использование записи 1000000.0 или 1e+6 вместо числа 1000000). Каждое число во входных данных записано в отдельной строке.

1. Задача 1. Спиннеры

Спиннер – модная игрушка c подшипником в основании, к которому прикреплены лопасти. Афанасий открыл бизнес по производству спиннеров. Он выяснил, что за спиннер, у которого N лопастей, покупатели готовы платить A + B × N рублей, но при этом покупатель не станет покупать спиннер, если его цена будет выше C рублей. Определите максимальное число лопастей спиннера, который согласится приобрести покупатель.

Программа получает на вход три числа A, B, C (стоимость основания спиннера, стоимость одной лопасти и максимальная стоимость всего спиннера). Все числа – целые положительные, не превосходящие 2×10⁹ , при этом A ≤ C.

Программа должна вывести одно число – максимальное число лопастей спиннера.

1. Пример входных и выходных данных

   Ввод	Вывод	Примечание
   20 10 55	3	Спиннер с 3 лопастями будет стоить 50 рублей, а с 4 лопастями – 60 рублей. Максимальная возможная стоимость спиннера – 55 рублей, поэтому максимальное число лопастей равно 3.

2. Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 60 баллов.

1. Примеры оформления решения задачи

Ниже даны примеры ввода и вывода данных к этой задаче на нескольких языках программирования. Выберите один из языков программирования, допишите соответствующую программу и отправьте её на проверку с использованием одного из допустимых компиляторов.

1. Задача 2. Снова спиннеры

Денис тоже решил заняться производством и продажей спиннеров, но он считает, что у спиннера может быть только три или четыре лопасти. У него есть ровно M лопастей, которые он может прикреплять к основаниям, и неограниченный запас оснований. Он хочет изготовить несколько трёхлопастных и несколько четырёхлопастных спиннеров так, чтобы использовать все M лопастей. Определите, сколько спиннеров каждого вида он должен произвести.

Программа получает на вход одно целое положительное число M, не превосходящее 2×10⁹ , – количество лопастей, которое есть у Дениса.

Программа должна вывести два целых числа – количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть несколько решений, нужно вывести любое из них. Если Денис не может использовать ровно M лопастей для производства спиннеров, программа должна вывести два числа 0.

1. Примеры входных и выходных данных

1. Система оценивания

Решение, правильно работающее только для случаев, когда M не превосходит 100, будет оцениваться в 60 баллов.

1. Задача 3. Не про спиннеры

Саша совсем не любит спиннеры, поэтому он рисует в тетрадке. Он взял тетрадный лист из N × M клеточек и пронумеровал все клетки различными числами. Теперь ему стало интересно, сколько различных прямоугольников он может вырезать из этого листа бумаги по границам клеточек.

Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.

Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).

1. Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 10, будет оцениваться в 40 баллов.

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 200, будет оцениваться в 70 баллов.

10. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
11. ПО ИНФОРМАТИКЕ
12. 2018-2019 УЧЕБНЫЙ ГОД
14. Для проверяющих 5 КЛАСС
16. Задание 1

В доме девять этажей, но лифт сломался, и теперь в нём работают только две кнопки. Нажатие на первую кнопку приводит к тому, что лифт поднимается на пять этажей вверх, а при нажатии на вторую кнопку лифт спускается на три этажа вниз. Подниматься выше девятого этажа или спускаться ниже первого этажа нельзя, ходить по лестнице тоже нельзя. Как подняться с первого этажа на девятый?

1. Решение

Нужно подняться на 8 этажей, если выполнили x операций «подняться на 5», и y операций «спуститься на 3», то 5x-3y=8. Решение можно найти подбором, , например, такое: y = 4, x = 4. Можно также заметить, что выполнение операции «подняться на 5» и операции «спуститься на 3» приводит к подъему на 2 этажа, поэтому эти операции нужно выполнить по 4 раза.

Для полного решения необходимо ещё привести пример последовательности операций. Пример.

1. Критерии оценивания

Правильно приведенная последовательность действий – 5 баллов.

Последовательность действий, в которой общее число операций «Подняться на 5» и «Спуститься на 3» найдено верно, но в результате неправильного порядка происходит однократный выход выше 9 этажа или ниже 1 этажа – 3 балла.

Последовательность действий, в которой общее число операций «Подняться на 5» и «Спуститься на 3» найдено верно, но число выходов выше 9 этажа или ниже 1 этажа больше одного – 2 балла.

Правильно указано число операций «Подняться на 5» и «Спуститься на 3» – 2 балла.

1. Задание 2

В игре «Камень, ножницы, бумага» двое игроков одновременно показывают при помощи руки один из трёх условных символов – «камень», «ножницы» или «бумага». Игрок выигрывает, если он показал камень, а его противник – ножницы («камень тупит ножницы»), если он показал ножницы, а его противник – бумагу («ножницы режут бумагу»), если он показал бумагу, а его противник – камень («бумага накрывает камень»). Если два игрока показали одинаковые символы, то игра заканчивается вничью.

Алёша и Боря сыграли в эту игру девять раз. Алёша два раза показал камень, три раза – ножницы, четыре раза – бумагу. Боря три раза показал камень, четыре раза – ножницы, два раза – бумагу, но порядок, в котором они показывали эти символы, неизвестен. Определите, какое наибольшее число раз мог выиграть Алёша. А какое наибольшее число раз мог выиграть Боря? Объясните свой ответ.

1. Решение

Составим таблицу, сколько раз каждый из мальчиков показывал каждый символ:

Боря мог выиграть все 9 раз, если 3 раза Боря показал камень, Алёша – ножницы, 4 раза Боря показал ножницы, Алёша – бумагу, 2 раза Боря показал бумагу, Алёша – камень.

Посчитаем, сколько раз Алёша мог выиграть у Бори. Такое могло произойти в следующих случаях:

1. Алёша показывает камень, Боря – ножницы. Это могло произойти не более 2 раз.

2. Алёша показывает ножницы, Боря – бумагу. Это могло произойти не более 2 раз.

3. Алёша показывает бумагу, Боря – камень. Это могло произойти не более 7 раз.

Таким образом, Алёша мог выиграть не более 7 раз. Необходимо также привести пример, когда Алёша выиграл у Бори 7 раз.

1. Алёша показывает камень, Боря показывает ножницы – 2 раза.

2. Алёша показывает ножницы, Боря показывает бумагу – 2 раза.

3. Алёша показывает бумагу, Боря показывает камень – 3 раза.

4. Алёша показывает бумагу, Боря показывает ножницы – 1 раз.

5. Алёша показывает ножницы, Боря показывает ножницы – 1 раз.

Алёша выигрывает в случаях 1-3, то есть 7 раз.

1. Критерии оценивания

Оценка складывается из двух оценок – ответ на вопрос о том, сколько раз мог выиграть Алёша (максимум 3 балла) и сколько раз мог выиграть Боря (максимум 2 балла).

Правильно указано, что Алёша мог выиграть 7 раз, показано, что Алёша не мог выиграть более 7 раз, приведён пример, когда Алёша выигрывает 7 раз – 3 балла.

Отсутствует объяснение, почему Алёша не может выиграть более 7 раз, или отсутствует пример, когда Алёша выигрывает 7 раз – 2 балла.

Дан только ответ, что Алёша может выиграть не более 7 раз – 1 балл.

Правильно указано, что Боря может выиграть 9 раз, приведён пример – 2 балла.

Только ответ, что Боря может выиграть 9 раз без примера – 1 балл.

1. Задание 3

Три вора – Камнев, Ножницын и Бумагин хотят переправиться через реку. У каждого вора два больших баула. В лодке три места, одно место занимает один человек или один баул. Грести умеет только Камнев. При этом если Камнев останется в лодке или на берегу с баулом Ножницына и Ножницына не будет рядом, то Камнев обчистит баул Ножницына. Аналогично Ножницын обчистит баул Бумагина в его отсутствие, а Бумагин обчистит баул Каменева в его отсутствие. Как им переправиться на другой берег? Опишите алгоритм их действий.

1. Решение

Возможный алгоритм действий.

1. Камнев перевозит два своих баула и возвращается назад.

2. Камнев перевозит Ножницына с баулом Ножницына, возвращается с Ножницыном.

3. Камнев перевозит Ножницына с баулом Ножницына, возвращается один назад.

4. Камнев перевозит Бумагина с баулом Бумагина, оставляет их на другом берегу, возвращается назад с двумя своими баулами.

5. Камнев перевозит баул Бумагина и возвращается назад.

6. Камнев перевозит два своих баула.

1. Критерии оценивания

Приведён верный алгоритм – 5 баллов.

Алгоритм с одной ошибкой (например, однажды возникает ситуация, когда один вор может обчистить баул другого вора, или один баул остаётся неперевезённым) – 2 балла.

Алгоритм с двумя ошибками – 1 балл.

1. Задание 4

Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 10, при этом число гирек в наборе должно быть как можно меньше. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться. Объясните, как любую массу от 1 до 10 граммов можно взвесить при помощи предложенного набора.

1. Решение

В оптимальном наборе гирек для уравновешивания любых масс необходимо использовать гирьки, массы которых являются степенями тройки: 1, 3, 9, 27 и т. д. Это связано с тем, что любое число можно представить в уравновешенной троичной системе счисления, при этом цифра 1 будет соответствовать тому, что гирька данной массы кладётся на одну чашку весов, цифра −1 будет соответствовать гирьке на другой чашке весов, а 0 означает, что данная гирька не используется.

Приведем пример уравновешивания всех масс от 1 до 10 при помощи гирек массами 1, 3, 9.

1. = 1.

2. = 3 − 1,

3. = 3,

4. = 3 + 1,

5. = 9 − 3 − 1,6 = 9 − 3,

1. = 9 − 3 + 1,

2. = 9 − 1,

3. = 9,

4. = 9 + 1.

От учащегося требуется привести пример конструкции из трёх гирек (их массы могут отличаться от примера 1, 3, 9) и показать, что любую массу можно уравновесить при помощи данного набора гирек.

1. Критерии оценивания

Приведён пример набора из трёх гирек, объяснено, как уравновесить каждую массу от 1 до 10 при помощи данного набора гирек – 5 баллов.

Только приведён пример правильного набора, без обоснования – 3 балла.

Приведён пример набора из трёх гирек, при этом одна какая-то масса от 1 до 10 не может быть уравновешена при помощи этого набора – 1 балл.

Приведён пример набора из четырёх гирек (например, 1, 2, 4, 8), показано, как уравновесить каждую массу от 1 до 10 при помощи данного набора – 3 балла.

Только приведён пример набора из четырёх гирек, удовлетворяющий условию задачи, без обоснования, почему каждую массу от 1 до 10 можно уравновесить при помощи гирек из данного набора – 1 балл.

1. Задание 5

Вам нужно умножить некоторое большое число X на 15. У вас есть калькулятор, но на калькуляторе сломались все кнопки операций, кроме сложения. Поэтому вы можете только складывать разные числа (например, можно сложить число X и число X, тогда получится 2X, затем можно сложить число 2X и 2X и получится 4X, а можно сложить 2X и X и получится 3X, то есть можно складывать любые ранее полученные числа между собой). Определите, при помощи какого минимального числа сложений можно получить число 15X. Приведите последовательность операций, при помощи которых можно получить число 15X за указанное число сложений.

1. Решение

Задачу можно решить за пять операций. Например:

1. 2X = X + X.

2. 3X = 2X + X.

3. 6X = 3X + 3X.

4. 12X = 6X + 6X.

5. 15X = 12X + 3X.

1. Критерии оценивания

Верный алгоритм с использованием 5 операций – 5 баллов.

Верный алгоритм с использованием 6 операций – 3 балла.

Верный алгоритм с использованием 7 операций – 1 балл.

Неверный алгоритм или число операций больше 7 – 0 баллов.

1. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
2. ПО ИНФОРМАТИКЕ
3. 2018-2019 УЧЕБНЫЙ ГОД
5. Для проверяющих 6 КЛАСС
7. Задание 1

В доме девять этажей, но лифт сломался, и теперь в нём работают только две кнопки. Нажатие на первую кнопку приводит к тому, что лифт поднимается на пять этажей вверх, а при нажатии на вторую кнопку лифт спускается на три этажа вниз. Подниматься выше девятого этажа или спускаться ниже первого этажа нельзя, ходить по лестнице тоже нельзя. Как подняться с первого этажа на девятый?

1. Решение

Нужно подняться на 8 этажей, если выполнили x операций «подняться на 5», и y операций «спуститься на 3», то 5x-3y=8. Решение можно найти подбором, , например, такое: y = 4, x = 4. Можно также заметить, что выполнение операции «подняться на 5» и операции «спуститься на 3» приводит к подъему на 2 этажа, поэтому эти операции нужно выполнить по 4 раза.

Для полного решения необходимо ещё привести пример последовательности операций. Пример.

1. Критерии оценивания

Правильно приведенная последовательность действий – 5 баллов.

Последовательность действий, в которой общее число операций «Подняться на 5» и «Спуститься на 3» найдено верно, но в результате неправильного порядка происходит однократный выход выше 9 этажа или ниже 1 этажа – 3 балла.

Последовательность действий, в которой общее число операций «Подняться на 5» и «Спуститься на 3» найдено верно, но число выходов выше 9 этажа или ниже 1 этажа больше одного – 2 балла.

Правильно указано число операций «Подняться на 5» и «Спуститься на 3» – 2 балла.

1. Задание 2

В игре «Камень, ножницы, бумага» двое игроков одновременно показывают при помощи руки один из трёх условных символов – «камень», «ножницы» или «бумага». Игрок выигрывает, если он показал камень, а его противник – ножницы («камень тупит ножницы»), если он показал ножницы, а его противник – бумагу («ножницы режут бумагу»), если он показал бумагу, а его противник – камень («бумага накрывает камень»). Если два игрока показали одинаковые символы, то игра заканчивается вничью.

Алёша и Боря сыграли в эту игру девять раз. Алёша два раза показал камень, три раза – ножницы, четыре раза – бумагу. Боря три раза показал камень, четыре раза – ножницы, два раза – бумагу, но порядок, в котором они показывали эти символы, неизвестен. Также известно, что игра ни разу не закончилась вничью. Определите, какое наибольшее число раз мог выиграть Алёша. А какое наибольшее число раз мог выиграть Боря? Объясните свой ответ.

1. Решение

Составим таблицу, сколько раз каждый из мальчиков показывал каждый символ:

Боря мог выиграть все 9 раз, если 3 раза Боря показал камень, Алёша – ножницы, 4 раза Боря показал ножницы, Алёша – бумагу, 2 раза Боря показал бумагу, Алёша – камень.

Посчитаем, сколько раз Алёша мог выиграть у Бори. Такое могло произойти в следующих случаях:

1. Алёша показывает камень, Боря – ножницы. Это могло произойти не более 2 раз.

2. Алёша показывает ножницы, Боря – бумагу. Это могло произойти не более 2 раз.

3. Алёша показывает бумагу, Боря – камень. Это могло произойти не более 7 раз.

Таким образом, Алёша мог выиграть не более 7 раз, но этот вариант недостижим, так как в этом случае в 7 партиях выигрывает Алёша:

1. Алёша показывает камень, Боря показывает ножницы – 2 раза.

2. Алёша показывает ножницы, Боря показывает бумагу – 2 раза.

3. Алёша показывает бумагу, Боря показывает камень – 3 раза.

Оставшиеся две партии должны быть такими:

1. Алёша показывает бумагу, Боря показывает ножницы – 1 раз.

2. Алёша показывает ножницы, Боря показывает ножницы – 1 раз.

В этом случае один раз игра заканчивается вничью, что недопустимо по условию задачи, то есть Алёша не мог выиграть 7 партий.

Приведём пример, когда Алёша выиграл 6 партий.

1. Алёша показывает камень, Боря показывает ножницы – 2 раза.

2. Алёша показывает ножницы, Боря показывает бумагу – 2 раза.

3. Алёша показывает бумагу, Боря показывает камень – 2 раза.

4. Алёша показывает ножницы, Боря показывает камень – 1 раз.

5. Алёша показывает бумагу, Боря показывает ножницы – 2 раза.

Алёша выигрывает в случаях 1-3, то есть 6 раз.

1. Критерии оценивания

Оценка складывается из двух оценок – ответ на вопрос о том, сколько раз мог выиграть Алёша (максимум 3 балла) и сколько раз мог выиграть Боря (максимум 2 балла).

Правильно указано, что Алёша мог выиграть 6 раз, показано, что Алёша не мог выиграть более 6 раз, приведён пример, когда Алёша выигрывает 6 раз – 3 балла.

Отсутствует объяснение, почему Алёша не может выиграть более 6 раз, или отсутствует пример, когда Алёша выигрывает 6 раз – 2 балла.

Дан только ответ, что Алёша может выиграть не более 6 раз – 1 балл.

Указано, что Алёша может выиграть 7 раз, приведён пример для 7 выигрышей Алёши, при этом одна партия заканчивается вничью (как в задании для 5 класса) – 1 балл.

Правильно указано, что Боря может выиграть 9 раз, приведён пример – 2 балла.

Только ответ, что Боря может выиграть 9 раз без примера – 1 балл.

1. Задание 3

Три вора – Камнев, Ножницын и Бумагин хотят переправиться через реку. У каждого вора два больших баула. В лодке три места, одно место занимает один человек или один баул. Грести умеет только Камнев. При этом если Камнев останется в лодке или на берегу с баулом Ножницына и Ножницына не будет рядом, то Камнев обчистит баул Ножницына. Аналогично Ножницын обчистит баул Бумагина в его отсутствие, а Бумагин обчистит баул Каменева в его отсутствие. Как им переправиться на другой берег? Опишите алгоритм их действий.

1. Решение

Возможный алгоритм действий.

1. Камнев перевозит два своих баула и возвращается назад.

2. Камнев перевозит Ножницына с баулом Ножницына, возвращается с Ножницыном.

3. Камнев перевозит Ножницына с баулом Ножницына, возвращается один назад.

4. Камнев перевозит Бумагина с баулом Бумагина, оставляет их на другом берегу, возвращается назад с двумя своими баулами.

5. Камнев перевозит баул Бумагина и возвращается назад.

6. Камнев перевозит два своих баула.

1. Критерии оценивания

Приведён верный алгоритм – 5 баллов.

Алгоритм с одной ошибкой (например, однажды возникает ситуация, когда один вор может обчистить баул другого вора, или один баул остаётся неперевезённым) – 2 балла.

Алгоритм с двумя ошибками – 1 балл.

1. Задание 4

Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 20, при этом число гирек в наборе должно быть как можно меньше. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться. Объясните, как любую массу от 1 до 20 граммов можно взвесить при помощи предложенного набора.

1. Решение

В оптимальном наборе гирек для уравновешивания любых масс необходимо использовать гирьки, массы которых являются степенями тройки: 1, 3, 9, 27 и т. д. Это связано с тем, что любое число можно представить в уравновешенной троичной системе счисления, при этом цифра 1 будет соответствовать тому, что гирька данной массы кладётся на одну чашку весов, цифра −1 будет соответствовать гирьке на другой чашке весов, а 0 означает, что данная гирька не используется.

Приведём пример уравновешивания всех масс от 1 до 20 при помощи гирек массами 1, 3, 9, 27.

1. = 1.

2. = 3 − 1,

3. = 3,

4. = 3 + 1,

5. = 9 − 3 − 1,

6. = 9 − 3,

7. = 9 − 3 + 1,

8. = 9 − 1,

9. = 9,

10. = 9 + 1,

11. = 9 + 3 − 1,

12. = 9 + 3,

13. = 9 + 3 + 1,

14. = 27 − 9 − 3 − 1,

15. = 27 − 9 − 3,

16. = 27 − 9 − 3 + 1,

17. = 27 − 9 − 1,

18. = 27 − 9,19 = 27 − 9 + 1,

20 = 27 − 9 + 3 − 1.

От учащегося требуется привести пример конструкции из четырёх гирек (их массы могут отличаться от примера 1, 3, 9, 27) и показать, что любую массу можно уравновесить при помощи данного набора гирек.

1. Критерии оценивания

Приведён пример набора из четырёх гирек, объяснено, как уравновесить каждую массу от 1 до 20 при помощи данного набора гирек – 5 баллов.

Только приведён пример правильного набора, без обоснования – 3 балла.

Приведён пример набора из четырёх гирек, при этом одна какая-то масса от 1 до 20 не может быть уравновешена при помощи этого набора – 1 балл.

Приведён пример набора из пяти гирек (например, 1, 2, 4, 8, 16), показано, как уравновесить каждую массу от 1 до 20 при помощи данного набора – 3 балла.

Только приведён пример набора из пяти гирек, удовлетворяющий условию задачи, без обоснования, почему каждую массу от 1 до 20 можно уравновесить при помощи гирек из данного набора – 1 балл.

1. Задание 5

Вам нужно умножить некоторое большое число X на 27. У вас есть калькулятор, но на калькуляторе сломались все кнопки операций, кроме сложения. Поэтому вы можете только складывать разные числа (например, можно сложить число X и число X, тогда получится 2X, затем можно сложить число 2X и 2X и получится 4X, а можно сложить 2X и X и получится 3X, то есть можно складывать любые ранее полученные числа между собой). Определите, при помощи какого минимального числа сложений можно получить число 27X. Приведите последовательность операций, при помощи которых можно получить число 27X за указанное число сложений.

1. Решение

Задачу можно решить за шесть операций. Например:

1. 2X = X + X.

2. 3X = 2X + X.

3. 6X = 3X + 3X.

4. 9X = 6X + 3X.

5. 18X = 9X + 9X.

6. 27X = 18X + 9X.

1. Критерии оценивания

Верный алгоритм с использованием 6 операций – 5 баллов.

Верный алгоритм с использованием 7 операций – 3 балла.

Верный алгоритм с использованием 8 операций – 1 балл.

Неверный алгоритм или число операций больше 8 – 0 баллов.

6. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
7. ПО ИНФОРМАТИКЕ
8. 2018-2019 УЧЕБНЫЙ ГОД
10. Для проверяющих 7-8 КЛАССЫ
12. Задача 1. Спиральная дорожка

Лужайка в парке имеет форму прямоугольника размером a × b метров, разбитого на квадраты со стороной 1 метр. Необходимо поставить внутри лужайки ограждения между некоторыми квадратами так, чтобы образовалась спиральная дорожка, закручивающаяся к центру лужайки. Определите длину такого ограждения.

На рисунке изображена лужайка размером 4 × 6 и ограждение, которое необходимо поставить на ней. Длина ограждения для такой лужайки будет равна 15.

Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные a и b (записываемые английскими буквами), операции сложения (обозначается «+»), вычитания (обозначается «−»), умножения (обозначается «*»), деления (обозначается «/») и круглые скобки для изменения порядка действий. Запись вида «2a» для обозначения произведения числа 2 и переменной a неверная, нужно писать «2 * a». Пример правильного (по форме записи) выражения: a + (b − a) * 2.

1. Решение

Посчитаем общее число горизонтальных и вертикальных отрезков длины 1 между клетками на рисунке лужайки. Их число равно a × (b − 1) + b × (a − 1).

После того, как будет поставлено ограждение, отрезков, в которых не будет поставлено ограждение, останется a × b − 1, так как получится цепочка из a × b клеток, между двумя соседними клетками в цепочке ограждение отсутствует.

Таким образом, ответом является выражение a * (b − 1) + b * (a − 1) − (a * b − 1). Это выражение можно упростить до вида (a − 1) * (b − 1), которое можно просто получить подбором, рассматривая примеры для разных значений a и b.

1. Задача 2. Книжная полка

В библиотеке на полке стоят 8 томов полного собрания сочинений одного писателя. Библиотекарь обозначил их латинскими буквами от A до H в порядке выхода томов.

Получилась следующая последовательность:

1. E D G H C B F A

Библиотекарь решил переставить эти книги так, чтобы они шли по порядку: A, B, C, D, E, F, G, H. За одно действие библиотекарь может взять несколько подряд идущих книг, достать их с полки и, не меняя порядок следования книг, перевернуть их и поставить на место в обратном порядке. Например, если библиотекарь достанет книги с H по F и перевернёт их, то новый порядок следования книг будет таким: E, D, G, F, B, C, H, A.

Помогите библиотекарю упорядочить этот ряд книг за минимальное число действий. То, что некоторые книги окажутся перевёрнутыми вверх ногами, библиотекарю не важно.

Ответом на эту задачу является последовательность операций. Одна операция записывается в одной строке. Описание каждой операции состоит из двух латинских букв

(от A до H), которые являются обозначениями крайних томов в переворачиваемом фрагменте, например, выше был рассмотрен пример для операции «H F».

Чем меньше операций будет в вашем алгоритме, тем больше баллов вы получите, при условии, что в результате применения вашего алгоритма тома будут расставлены по порядку от A до H.

1. Решение

Наилучшее решение этой задачи содержит четыре операции:

G B

B C

H A

E A

Есть и другие варианты решения, использующие четыре операции.

1. Задача 3. Гирьки

Есть чашечные весы без делений. Для взвешивания груза также можно использовать гирьки, массы которых – целое число граммов. Вам необходимо предложить набор гирек, при помощи которого можно отмерить на весах любую массу, равную целому числу граммов от 1 до 40. Гирьки можно класть на каждую чашку весов, чашки весов должны находиться в равновесии, при этом на одной из чашек весов должен находиться взвешиваемый груз. Массы гирек в наборе могут повторяться.

Например, при помощи трёх гирек массами 1, 1 и 5 граммов можно отмерить любую целочисленную массу от 1 до 7 граммов по следующей схеме (x – взвешиваемая масса):

1. грамм: x = 1,

2. грамма: x = 1 + 1,

3. грамма: x + 1 + 1 = 5,

4. грамма: x + 1 = 5,

5. граммов: x = 5, 6 граммов: x = 5 + 1, 7 граммов: x = 5 + 1 + 1.

Ответом на эту задачу являются несколько целых чисел, записанных через пробел, – массы гирек, при помощи которых можно отмерить любую целочисленную массу от 1 до 40. В наборе должно быть не более 8 чисел. Числа в наборе могут повторяться. Чем меньше гирек будет в предложенном наборе, тем больше баллов вы получите, при условии, что, используя гирьки из данного набора, можно отмерить каждую целочисленную массу от 1 до 40.

1. Решение

Возникает желание использовать в ответе степени двойки: 1, 2, 4, 8, 16, 32. Но такое решение не является оптимальным, поскольку не использует возможность класть гирьки на обе чашки весов. Если гирьки можно класть на обе чащи весов, то каждая из гирек может учитываться с коэффициентом −1 или +1, в зависимости от того, лежит ли она на одной чашке со взвешиваемой массой или на противоположной, а также с коэффициентом 0, если гирька не участвует во взвешивании. Поэтому вместо степеней двойки можно использовать степени тройки: 1, 3, 9, 27. Возможность представления всех масс от 1 до 40 следует из того, что все целые числа можно представить в симметричной троичной системе счисления, то есть в виде сумм степеней тройки, умноженных на коэффициенты 0, 1 и −1, а также из того факта, что 40 = 1 + 3 + 9 + 27.

Ответ: 1 3 9 27.

1. Задача 4. Возведение в степень

Вы хотите возвести данное число a в некоторую целочисленную степень n, но ваш калькулятор умеет только перемножать числа. Например, вы можете вычислить a² = a × a, затем вы можете вычислить a³ = a² × a или a⁴ = a² × a².

Вы можете по-разному организовать вычисление значения aⁿ. Например, вычислить a⁵ можно за 4 умножения:

1. a² = a × a,

2. a³ = a² × a,

3. a⁴ = a³ × a, 4) a⁵ = a⁴ × a.

Но можно вычислить a⁵ всего лишь за 3 умножения:

1) a² = a × a, 2) a³ = a²×a,

3) a⁵ = a³×a².

Вам необходимо определить, за какое минимальное число умножений можно вычислить следующие степени: 7, 15, 23, 63. Вычисление каждой из этих степеней должно быть независимо от остальных, то есть при вычислении 15-й степени нельзя использовать вычисления, проделанные ранее для вычисления 7-й степени. Вы решаете четыре независимые задачи – за какое минимальное число умножений можно вычислить 7-ю степень, 15-ю степень, 23-ю степень и 63-ю степень.

Ответ на это задание записывается в четырёх строках. Каждая строка должна содержать последовательность вычисления каждой из указанных степеней. Первая строка должна содержать последовательность вычисления 7-й степени, вторая строка – 15-й степени, третья строка – 23-й степени, четвертая строка – 63-й степени.

Каждая строка содержит через пробел несколько целых чисел – значения степеней в том порядке, в котором они вычисляются. Например, для вычисления 5-й степени решение можно записать в виде строки

2 3 5 или

2 4 5, что означает, что последовательно вычисляются степени a², a³, a⁵ (одно возможное решение) или a², a⁴, a⁵ (другое возможное решение). Таким образом, каждая строка должна начинаться числом 2, а заканчиваться тем значением степени, которое нужно вычислить (7, 15, 23, 63).

Чем меньше операций умножения вы будете использовать, тем больше баллов вы получите, при условии, что предложенные последовательности вычисления степеней являются корректными.

1. Решение

В этой задаче также возникает желание использовать двоичную систему счисления, как и в алгоритме быстрого возведения в степень. Например, чтобы вычислить a⁷ степень, необходимо вычислить a² и a⁴, а затем перемножить a, a², a⁴. Всего понадобится 4 умножения. Для вычисления a¹⁵, a²³, a⁶³ через двоичную систему счисления понадобится 6, 7 и 10 умножений соответственно.

Но есть способ вычислить a¹⁵, a²³, a⁶³ используя меньшее число умножений — 5, 6 и 8. Пример наилучшего решения.

2 3 5 7

2 3 6 12 15

2 3 5 10 20 23

2 3 6 12 15 30 60 63

1. ШКОЛЬНЫЙ ЭТАП ВСЕРОССИЙСКО ОЛИМПИАДЫ ШКОЛЬНИКОВ
2. ПО ИНФОРМАТИКЕ
3. 2018-2019 УЧЕБНЫЙ ГОД
5. Для проверяющих 9-11 КЛАССЫ
7. Задача 1. Спиннеры
   1. Автор задачи — Михаил Прохоров
   2. Тесты

1. Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 60 баллов.

1. Решение

По условию задачи A + B × N ≤ C, откуда N ≤ (C – A) / B. Программа должна вывести целочисленное частное от деления (C – A) / B, то есть округлить результат вниз до целого числа. Для этого в языке Pascal используется операция div

Пример полного решения на Питоне.

a = int(input())

b = int(input())

c = int(input())

n = (c - a) // b print(n)

60 баллов набирали решения, в которых значение N увеличивалось в цикле на 1, пока выполнялось условие A + B × N ≤ C. Пример решения на 60 баллов.

a = int(input())

b = int(input())

c = int(input())

n = 0

while a + b * n

n = n + 1

print(n - 1)

1. Задача 2. Снова спиннеры

Программа получает на вход одно целое положительное число M, не превосходящее 2×10⁹ , – количество лопастей, которое есть у Дениса.

Программа должна вывести два целых числа – количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть несколько решений, нужно вывести любое из них. Если Денис не может использовать ровно M лопастей для производства спиннеров, программа должна вывести два числа 0.

1. Тесты

1. Система оценивания

Решение, правильно работающее только для случаев, когда M не превосходит 100, будет оцениваться в 60 баллов.

1. Решение

Задача имеет решения для любого M, кроме 1, 2, 5. Заметим, что если число M делится на 3, то можно изготовить только трёхлопастные спинеры, их количество будет равно M / 3. Если M даёт остаток 1 при делении на 3, то необходимо изготовить как минимум один четырёхлопастный спиннер. Если M даёт остаток 2 при делении на 3, то понадобится минимум 2 трёхлопастных спиннера. Таким образом, можно считать, что число четырёхлопастных спиннеров равно остатку от деления M на 3, запишем это количество в переменную n₄. Для нахождения остатка от деления в языке Pascal используется операция mod, в языках C, C++ и Python операция «%». Оставшиеся лопасти будем использовать для производства трёхлопастных спиннеров, их количество будет равно (M – 4 n₄) / 3. Если при этом число трёхлопастных спиннеров получилось отрицательным, то задача решения не имеет.

Пример решения на языке Python.

m = int(input())

n4 = m % 3

n3 = (m - 4 * n4) // 3

if n3 = 0:

print(n3)

print(n4)

else:

print(0)

print(0)

2. Задача 3. Не про спиннеры
   1. Автор задачи — Александр Серянин

Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.

Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).

1. Тесты

Если программа работает более 1 с, то результат на засчитывают.

Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 10, будет оцениваться в 40 баллов.

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 200, будет оцениваться в 70 баллов.

1. Решение

Пронумеруем столбцы листа числами от 1 до N, строки листа числами от 1 до M. Пусть клетка, находящаяся в одном углу прямоугольника имеет координаты x₁, y₁, а противоположная клетка — координаты x₂, y₂. Тогда выполнены неравенства 1 ≤ x₁ ≤ x₂ ≤ N, 1 ≤ y₁ ≤ y₂ ≤ M. Задача сводится к подсчёту количества четвёрок чисел x₁, y₁, x₂, y₂, удовлетворяющих этим неравенствам.

Если это делать при помощи четырёх циклов, то получится решение сложности O(N²M²), которое набирает 40 баллов.

Пример такого решения на Питоне.

n = int(input())

m = int(input())

ans = 0

for x1 in range(n):

for x2 in range(x1, n):

for y1 in range(m):

for y2 in range(y1, m):

ans += 1

print(ans)

Для получения больших баллов необходимо оптимизировать это решение.

Например, можно заметить, что задачу можно решать независимо по каждой из двух осей координат, то есть нужно подсчитать количество подходящих пар x₁, x₂ и количество подходящих пар y₁, y₂ и перемножить два найденных числа. Такое решение будет иметь сложность O(N² + M²) и набирает 70 баллов.

Пример такого решения:

n = int(input())

m = int(input())

ans_x = 0

ans_y = 0

for x1 in range(n):

for x2 in range(x1, n):

ans_x += 1

for y1 in range(m):

for y2 in range(y1, m):

ans_y += 1

print(ans_x * ans_y)

Страница 27 из 28