Подготовка к олимпиаде по информатике:
Задача Не про спиннеры
Саша совсем не любит спиннеры, поэтому он рисует в тетрадке. Он взял тетрадный лист из N × M клеточек и пронумеровал все клетки различными числами. Теперь ему стало интересно, сколько различных прямоугольников он может вырезать из этого листа бумаги по границам клеточек.
Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.
Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников). Примеры входных и выходных данных
Система оценивания
Решение, правильно работающее только для случаев, когда все входные числа не превосходят 10, будет оцениваться в 40 баллов.
Решение, правильно работающее только для случаев, когда все входные числа не превосходят 200, будет оцениваться в 70 баллов.
Вот и закончился школьный тур Всероссийской олимпиады школьников. Как мне показалось, задания были несколько сложнее, чем в прошлом году. В данной статье хотелось бы представить свое решение задачи №3 «Не про спиннеры». Для написания текста программы буду использовать язык Python 3.
Задача.
Саша совсем не любит спиннеры, поэтому он рисует в тетрадке. Он взял тетрадный лист из N × M клеточек и пронумеровал все клетки различными числами. Теперь ему стало
интересно, сколько различных прямоугольников он может вырезать из этого листа бумаги по границам клеточек.
Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.
Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).
Решение.
Рассмотрим размер исходного листа 3 × 1 (три клетки по горизонтали и одна клетка по вертикали). Как в образце.
Чтобы понять принцип подсчета различных прямоугольников, которые можно вырезать из данного листа, обратимся к следующей схеме:
- Обозначим каждую клетку прямоугольника цифрой от 1 до 3.
- Парами чисел (1 1), (1 2), (1 3), (2 1), (2 2) (3 1) обозначим возможные вырезанные прямоугольники. Первая цифра обозначает начало такого прямоугольника, вторая цифра — количество клеток слева направо. Итого получаем 6 различных прямоугольников. Как в таблице с примерами входных и выходных данных.
Схема решения -1
Из рисунка видно, что ни один из прямоугольников не повторяется.
В первом столбце — 3 варианта, во втором — 2, в третьем — 1.
Таким образом, чтобы посчитать количество различных прямоугольников на листе размера 1 × n (n — натуральное число) необходимо: 1 + 2 + 3 + … + n
Реализовать такой алгоритм довольно просто:
Шаг 2
Теперь рассмотрим вариант листа вида m × n. Например: 3 × 3.
Мы знаем, что в строке 1 × 3 ровно 1 + 2 + 3 = 6 произвольных прямоугольников.
Начнем рассматривать прямоугольник 3 × 3 снизу вверх, делая следующие рассуждения:
Схема решения — 2
Случаи, когда мы берем полоску клеток 2 × 3 или 3 × 3 ничем не отличается от случая 1 × 3 и имеет столько же решений.
Таким образом: 6 + 6 * 2 + 6 * 3 — формула подсчета количества различных прямоугольников на листе 3 × 3.
Напишем полный текст программы с комментариями:
Думаю, решение выглядит довольно просто.
Есть другие варианты решения задачи — пишите в комментариях на сайте или в группе в Контакте. Было бы интересно!
Денис тоже решил заняться производством и продажей спиннеров, но он считает, что у спиннера может быть только три или четыре лопасти. У него есть ровно М лопастей, которые он может прикреплять к основаниям, и неограниченный запас оснований. Он хочет изготовить несколько трехлопастных и несколько четырехлопастных спиннеров так, чтобы использовать все М лопастей. Определите, сколько спиннеров каждого вида он должен произвести.
Программа получает на вход одно целое положительное число М, не превосходящее 2*10^9,- количество лопастей, которое есть у Дениса.
Программа должна вывести два целых числа- количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть несколько решений, нужно вывести любое из них. Если Денис не может использовать ровно М лопастей для производства спиннеров, программа должна вывести два числа 0.
Задача по информатике на PASCAL. Помогите кто чем сможет.