Задания 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) и выводит на экран искомое количество способов.
|
Пример Ввод |
Вывод |
|
2 3 |
8 |
Задача 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) и выводит на экран количество различных возможных рациональных чисел.
|
Пример Ввод |
Вывод |
|
4 |
4 |
Задания подготовили Г. Непомнящий, Ю. Пасихов, И. Порублёв