Задачи очного тура региональной олимпиады Информатика-2004

Вы продавец, и у Вас имеются монеты номиналом 1, 5, 10, 50 копеек, 1, 2, 5 рублей в неограниченном количестве. Сумму 4 рубля 50 копеек можно выдать с помощью 450 однокопеечных монет, либо с помощью 45 десятикопеечных монет, либо с помощью 9 пятидесятикопеечных монет. Но лучше всего эту сумму выдать с помощью трех монет – двух двухрублевых и одной пятидесятикопеечной. Сдайте сдачу в `N` рублей `M` копеек так, чтобы она состояла из минимального количества монет.

Во входном файле содержатся два целых числа `N` и `M` (`0\ ≤\ N\ <\ 10`, `0\ ≤\ M\ <\ 100`), разделенных пробелом – сумма сдачи в рублях и копейках.

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

4 50

3

Назовем целое число `N` замечательным, если для него справедливо равенство `N^2=(N\ -\ 1)^2\ +\ M^2`, где `M` – целое число. Даны два целых числа `A` и `B`. Найти количество замечательных чисел из диапазона `[A,B]` включительно. Например, в диапазоне `[1,10]` таких чисел два, а именно числа 1 и 5.

Во входном файле содержатся два целых числа `A` и `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^9`), разделенных пробелом.

В выходной файл записать количество замечательных чисел из заданного диапазона.

1 10

2

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

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

Во входном файле содержатся девять целых чисел от 1 до 1000, разделенных пробелами – длины сторон треугольников.

В выходной файл записать в первой строке 3 числа, соответствующих сторонам одного из подобных треугольников, во второй строке 3 числа, соответствующих сторонам другого подобного треугольника. Если есть несколько вариантов, вывести один (любой) из них.

2 15 3 9 3 4 12 3 5

3 4 5
9 12 15

Даны `N` целых чисел `А_1,\ А_2,\ …,\ А_N`, все числа принадлежат диапазону `[-100;100]`. Дано целое число `k` (`k\ ≤\ N`). Найти `k` чисел из `А_1,\ А_2,\ …,\ А_N`, образующих максимальное произведение.

Во входном файле в первой строке содержатся два целых числа `k` и `N` (`1\ ≤\ k\ ≤\ 10`, `k\ ≤\ N\ ≤\ 100`), разделенные пробелом, а во второй строке – `N` целых чисел, разделенных пробелами.

В выходной файл записать `k` чисел из `N` данных чисел, образующих максимальное произведение, разделяя их пробелами (лишние пробелы игнорируются). Если есть несколько вариантов, вывести один (любой) из них.

3 7
-3 -1 -2 0 1 9 2

-3 -2 9

Муравей Бильбо в поисках пищи ползает по квадратному полю размерами 1000x1000. Левый нижний угол поля имеет координаты (0,0). Бильбо может передвигаться только параллельно границам поля и может поворачивать только в точках с целыми координатами. При движении муравей оставляет запаховый след (который постепенно выветривается, ослабляется), чтобы потом найти обратную дорогу в муравейник. При поиске пищи муравей никогда не ходит по собственным следам, но может их пересекать. Как только муравей нашел какую-либо пищу, он ползет назад по своим собственным следам, но если на обратном пути ему встречаются два следа, то он выбирает тот, у которого запах слабее и идет в сторону уменьшения запаха. Определить длину пути муравья до пищи и обратного пути.

Во входном файле в первой строке содержится целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество отрезков пути до пищи, во второй строке – координаты муравейника (начало пути), затем `N` строк с координатами конца каждого отрезка пути до кусочка пищи в порядке прохождения.

В выходной файл в первой строке вывести длину пути от муравейника до кусочка пищи, а во второй строке – длину обратного пути.

8
1 2
7 2
7 5
3 5
3 1
5 1
5 3
1 3
1 5

27
19

Робот должен определять вес объекта, рассматривая его с трех сторон: спереди, слева и сверху. Объект состоит из единичных кубиков, может быть вписан в куб размером `N\ times\ N\ times\ N`, но может быть несвязным. Каждый из видов рассматриваемого объекта представляется в виде матрицы размером `N\ times\ N`, заполненной символами '*' и '.', символ '*' означает, что при рассматривании объекта в данном направлении виден как минимум один кубик, а '.' – что нет ни одного кубика при рассматривании объекта в данном направлении. Пример для `N=3`.

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

Во входном файле в первой строке содержится целое число `N` (`1\ ≤\ N\ ≤\ 10`) – размер объекта, далее следует `3*N` строк, содержащих по `N` символов '*' и '.' – виды объекта в следующем порядке: спереди, слева и сверху.

В выходной файл записать одно целое число – максимальное количество кубиков, из которых может состоять объект.

3
..*
.**
***
*..
**.
***
***
***
**.

13

Необходимо осушить прямоугольное озеро. Озеро было разделено на квадратные участки, и на каждом участке была измерена его глубина. Размеры озера получились `N\ times\ M`. Для осушения озера используются насосы, которые опускаются на дно и выкачивают всю воду с этого участка, а также воду, стекающую с других участков. Вода стекает с участка, только если на соседнем участке уровень воды ниже (см. рис). Соседними являются участки, имеющие общую сторону.

Во входном файле в первой строке содержатся два целых числа `N` и `M` (`1\ ≤\ N\ ≤\ 100`, `1\ ≤\ M\ ≤\ 100`) – размеры озера, далее следует `N` строк, в каждой строке по `M` целых чисел от 1 до 100 – глубина озера на соответствующем участке.

В выходной файл выведите минимальное количество насосов для полного осушения озера.

3 4
6 3 2 1
5 4 4 7
3 5 6 7

2