Задания 1-го тура NetOI-2012
Решения принимаются до 0 часов 17 ноября 2012 г. Сдавать решения можно только один раз. Работает on-line проверка решений на авторских тестах. Количество
проверок не ограничено.
ВНИМАНИМЕ! Не путайте
on-line проверку решения
и отправку решения на официальную проверку!
Задача Rectangle
На
квадратном листе бумаги «в клеточку» (размером N * N клеток)
нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых
клеток, различные прямоугольники не накладываются друг на друга и могут
касаться только углами. Найдите количество этих прямоугольников.
|
Пример
Ввод
|
Вывод
|
|
4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
|
2
|
Технические условия. Программа
Rectangle читает с клавиатуры число N (2
≤ N ≤ 100), а в каждой из следующих N
строк содержится по N цифр 0 или 1 через пробел (1
- если клетка принадлежит одному из прямоугольников, и 0, если - нет).
Программа выводит на экран единственное число - количество прямоугольников.
Задача Parket1
Чтобы
изобразить на паркете Новый Узор, необходимо N1
дощечек размера 1×1, N2 дощечек размера
2×1, N3 размера 3×1, N4
размера 4×1 и N5 дощечек размера 5×1.
Купить можно только дощечки размером 5×1. Дощечки можно резать, но нельзя
склеивать. Например, когда нужно пять дощечек 2×1, их нельзя сделать из
двух дощечек 5×1, но можно из трех. Для этого две из них режем на три
части 2×1, 2×1 и 1×1 каждую, а третью - на две части
2×1 и 3×1. Получаем нужные пять дощечек 2×1, а две дощечки
1×1 и одна 3×1 идут в отходы. Напишите программу, которая, прочитав
количества дощечек N1, N2, N3,
N4 и N5, найдет минимальное
количество дощечек 5×1, которое нужно купить.
Технические условия. Программа Parket1 читает с клавиатуры через
пробел пять чисел N1, N2, N3,
N4 и N5 (именно в таком
порядке). Все числа неотрицательные, и их сумма меньше 2*109.
Программа выводит на экран количество дощечек 5×1, которое нужно купить.
|
Пример
Ввод
|
Вывод
|
|
0 5 0 0 0
|
3
|
|
1 1 1 1 1
|
3
|
Задача Birthday
Маленькому
Ване на день рождения подарили большую прямоугольную шоколадку, которая
содержит m*n квадратных плиточек. Ваня ест только
квадратные шоколадки, поэтому он решил выломать квадратный кусок (возможно, это
будет вся шоколадка), съесть его, а остальное раздать друзьям. Разумеется,
ломать плиточки нельзя. Помогите Ване подсчитать количество способов, которыми
он может полакомиться шоколадом.
Технические условия. Программа Birthday читает с клавиатуры через пробел два числа m
и n (1<=m,n<=1000) и выводит на
экран искомое количество способов.
Задача Fazenda
В
соответствии с Законом о земле каждый гражданин обязан получить участок земли и
зарегистрировать его в Большом Прозрачном Доме (БПД). Участок земли имеет форму
треугольника, в реестре БПД указаны расстояния от каждой вершины до прямой,
проходящей через две другие вершины (высоты треугольника). Граждане начали интересоваться
у главного программиста БПД, какой площади их участок и какой длины придется строить
забор. К сожалению, главный программист не участвовал в NetOI и поэтому не смог
помочь. Помогите Вы.
Технические условия. Программа Fazenda читает с клавиатуры через пробел высоты
треугольника - вещественные числа h1, h2, h3
(1<=h1,h2,h3<=10000) и выводит
на экран площадь и периметр треугольника. Если треугольник не существует, необходимо
вывести через пробел дважды 0.
|
Примеры
Ввод
|
Вывод
|
|
40 30 24
|
6.0000000000Е+02
1.2000000000Е+02
|
|
70 10 25
|
0.0000000000Е+00
0.0000000000Е+00
|
Задача Second
Обозначим
i-е простое число как Рi (Р1=2, Р2=3,
Р3=5 и т.д.). Для данного числа n рассмотрим
выражение: Р1 / Р2 / Р3 / ... / Рn.
Напишите программу, подсчитывающую количество различных рациональных чисел,
которые можно получить, расставляя в данном выражении скобки. Например, если n=4,
то таких чисел будет тоже 4: (((2/3)/5)/7 = 2/105, 2/(3/(5/7)) = 10/21,
(2/3)/(5/7) = 14/15 и 2/((3/5)/7) = 70/3.
Технические условия. Программа Second читает с клавиатуры целое число n
(от 2 до 100) и выводит на экран количество различных возможных
рациональных чисел.
Задания подготовили Г. Непомнящий,
Ю. Пасихов, И. Порублёв
