Открытая олимпиада
"МАТЕМАТИКА-ИНФОРМАТИКА "ДНИ НАУКИ ОТИ МИФИ-2005"
http://www. *****/olymp/
*****@
Сумма.
Вычислить сумму:
Крибедж.
Игрокам в крибедж издавна известно, что
15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 .
Найти количество способов представления числа 1050 в виде суммы последовательных положительных целых чисел.
(Для 15 таких представлений четыре.)
Кирпичи.
Можно ли сложить штабель из n кирпичей таким образом, чтобы самый верхний кирпич полностью выступал над нижним кирпичом; при этом человек, вес которого 100 кирпичей, мог бы балансировать на середине верхнего кирпича, не обрушивая весь штабель?
Определитель.
Вычислить определитель n – го порядка:
Неравенство.
Доказать, что для любого числа E > 0 существует такое натуральное число n, что
| sin n – ½ | < E.
Точки.
На окружности расположено N точек. Их положение определяется углом φ между осью OX и радиусом, проведенным от центра окружности к этой точке. Угол задается в градусах. Никакие две точки на окружности не совпадают. Требуется среди данных точек найти такие, что сумма расстояний по окружности от каждой из этих точек до всех остальных была минимальна. Расстояние по окружности пропорционально минимальному углу, между радиусами, проведенными к этим точкам, поэтому сумму расстояний следует вычислять как сумму углов.
Формат входных данных.
Первая строка файла Point. in содержит целое число N (1 ≤ N ≤ 360) – количество точек. Далее следует N строк: каждая строка содержит целое число φ (1 ≤ φ ≤ 360), определяющее положение точки на окружности.
Формат выходных данных.
Первая строка файла Point. out содержит число K – количество точек, удовлетворяющих условию задачи. Далее следует K строк, содержащих номера этих точек в порядке считывания данных из файла. Номера точек требуется вывести в порядке возрастания номеров.
Пример:
Point. in | Point. out |
4 315 350 47 12 | 2 2 4 |
Песочница. |
Прямоугольная детская площадка полностью замощена N плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.
На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь.
Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.
Формат входных данных
Введем систему координат так, чтобы начало координат совпадало с одним из углов площадки, а оси координат шли вдоль сторон площадки. В этом случае противоположный угол площадки окажется в точке (X,Y).
Первая строка входного файла содержит два числа X и Y (натуральные числа, не превышающие 10000). Во второй строке заданы числа N и K (1£K£N£2000). Следующие N строк файла содержат по четыре целых числа Xi,1, Yi,1, Xi,2, Yi,2, задающих координаты двух противоположных углов плитки (0£Xi,1<Xi,2£X, 0£Yi,1<Yi,2£Y).
Формат выходных данных
В выходной файл выведите координаты двух противоположных углов найденного прямоугольника. Если решений несколько, выведите любое из них.
Пример
Пример входного и выходного файлов для приведенного рисунка.
sandbox. in | sandbox. out |
7 5 8 3 |
Стекло.
На столе расположено несколько треугольных осколков стекла. Были выдвинуты следующие предположения:
· все эти осколки принадлежали одному прямоугольному стеклу, которое исходно лежало так, что его стороны были параллельны краям стола;
· осколки получены в результате удара в некоторую точку стекла, не лежащую на его границе;
· в момент удара одна из вершин каждого осколка находилась в точке удара;
· некоторые осколки, возможно, были сдвинуты;
· стекло может быть восстановлено параллельным переносом осколков, то есть ни один из осколков не был повернут.
Напишите программу, помогающую при этих предположениях полностью восстановить прямоугольное стекло из всех имеющихся осколков или определяющую, что это сделать невозможно.
|
Формат входных данных
В первой строке входного файла записано число N — количество осколков (1≤N≤2000).
Введем систему координат таким образом, чтобы оси координат были параллельны сторонам стола. В каждой из следующих N строк записано по три пары чисел, задающих текущие координаты вершин осколков. Все координаты — целые числа, по модулю не превосходящие 10000. Все осколки имеют ненулевую площадь.
Формат выходных данных
Если стекло возможно восстановить при указанных предположениях, то в N строках выходного файла выведите координаты вершин осколков после восстановления стекла. Стекло должно быть восстановлено таким образом, чтобы координаты всех его углов были неотрицательны, и один из его углов располагался в начале координат. Перечисление осколков и их вершин должно соответствовать их порядку следования во входном файле.
В случае нескольких решений выведите любое из них.
В случае невозможности восстановить стекло в выходной файл выведите сообщение NO.
Примеры
glass. in | glass. out |
5 | |
4 20 -20 | NO |
