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

Подготовка к олимпиаде по информатике:

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

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

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

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

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

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

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

Вот и закончился школьный тур Всероссийской олимпиады школьников. Как мне показалось, задания были несколько сложнее, чем в прошлом году. В данной статье хотелось бы представить свое решение задачи №3 «Не про спиннеры». Для написания текста программы буду использовать язык Python 3.

Задача.

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

Читайте также:  Бесконтактный генератор для велосипеда

Решение.

Рассмотрим размер исходного листа 3 × 1 (три клетки по горизонтали и одна клетка по вертикали). Как в образце.

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

  1. Обозначим каждую клетку прямоугольника цифрой от 1 до 3.
  2. Парами чисел (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.

Читайте также:  Sentinel runtime что это за программа

Задача по информатике на PASCAL. Помогите кто чем сможет.

Оцените статью
Добавить комментарий