Задача С. Минимальное произведение

Школьный этап Всероссийской олимпиады школьников по информатике и ИКТ

Учебный год

Решения заданий для 9–11 классов

Задача А. Считалка

Условие

Для выбора водящего в детской игре N человек становятся в круг, после чего произносится считалка. На первом слове считалки указывается на первого человека в кругу, на втором слове – на второго человека и т. д. После N-го человека снова идёт первый человек (все люди в кругу пронумерованы числами от 1 до N, круг зацикливается, после человека с номером N идёт человек с номером 1).

Всего в считалке M слов. Определите, на какого человека придётся последнее слово считалки.

Программа получает на вход два целых положительных числа. Первое число N – количество людей в кругу. Второе число M – количество слов в считалке. Оба числа не превосходят 10⁹.

Программа должна вывести одно целое число от 1 до N – номер человека в кругу на которого придётся последнее слово считалки.

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

Ввод

Вывод

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

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

Решение

Ответом является остаток от деления числа M на число N, за единственным исключением – если остаток равен нулю, то есть M делится на N, то считалка остановится на последнем человеке и программа должна вывести значение N, а не 0. Это нужно рассмотреть при помощи одного условия if.

Пример решения задачи на языке Python:

N = int(input()) M = int(input()) if M % N == 0: print(N) else: print(M % N)

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

Задача В. Конфеты

Условие

На столе стоят три вазы с конфетами. В левой вазе лежат A конфет, в средней вазе лежат B конфет, в правой вазе лежат C конфет. Лена съедает одну конфету из левой вазы, затем – одну конфету из средней вазы, затем из правой, средней, левой, средней, правой, средней и т. д. (слева направо, затем налево, опять направо и т.д.)

Если Лена хочет взять конфету из какой-то вазы, а конфет там нет, она расстраивается и идёт спать. Определите, сколько конфет съест Лена.

Программа получает на вход три целых неотрицательных числа A, B, C – количество конфет в левой, средней, правой вазе. Сумма трёх данных чисел не превосходит 2×10⁹.

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

Ввод	Вывод	Примечание
		Лена съест конфеты из левой, средней, правой, 3 средней, левой, средней, правой вазы. После этого она захочет съесть конфету из средней вазы, но в ней уже не осталось конфет.

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

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

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

Решение

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

Для получения полного решения заметим, что процесс взятия конфет содержит цикл «левая ваза, средняя ваза, правая ваза, средняя ваза», который затем повторяется. За один проход такого цикла число A уменьшается на 1, число B уменьшается на 2, число C уменьшается на 1. Посчитаем, сколько раз будет выполнен цикл — это минимум из чисел A, [B / 2] и C (под записью [B / 2] подразумевается целая часть от деления B на 2, то есть операция целочисленного деления). Запишем количество проходов цикла в переменную k и уменьшим значение переменных A и C на k, а значение переменной B на 2k. За k исполнений цикла суммарно будет взято 4k конфет.

Следующий проход цикла не будет выполнен полностью. Посмотрим на значение переменных A, B, C в том порядке, в котором берутся конфеты из соответствующих ваз. Если A = 0, то нельзя на следующем шаге взять конфету из первой вазы, и ответом будет 4k. Если B = 0, то будет взята конфета из первой вазы, но во второй вазе конфеты кончились, поэтому ответ будет 4k + 1. Если же C = 0, то, аналогично, можно взять еще две конфеты из левой и средней вазы, и ответ будет 4k + 2. Наконец, если все эти условия не выполнены, то ответ будет 4k + 3.

Пример решения задачи на языке Python (операция «//» в Python обозначает целочисленное деление):

a = int(input()) b = int(input()) c = int(input()) k = min(a, b // 2, c) a -= k b -= 2 * k c -= k if a == 0:

print(4 * k) elif b == 0:

print(4 * k + 1) elif c == 0: print(4 * k + 2) else: print(4 * k + 3)

Задача С. Минимальное произведение

Условие

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).

В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.

Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.