Матрица: правый нижний эленент

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Матрица А считается меньше (больше) матрицы В, если при просмотре слева направо и сверху вниз после всех равенств элементов матриц следующий элемент из матрицы А меньше (больше), чем соответствующий элемент из В. Такое сравнение называется лексикографическим и напоминает способ сравнения слов в словаре.
Дана прямоугольная матрица A размером nxm, все элементы которой различны. Над ней можно выполнять следующие действия:
1. Поменять местами 2 произвольных столбца;
2. Поменять местами 2 произвольных строки.
Пусть A_max максимальная матрица, получаемая из исходной матрицы путем любого требуемого количества вышеприведённых операций. Необходимо написать программу, находящую последний (правый нижний) элемент из A_max.

Входные данные

В первой строке входного файла записаны целые числа n, m (1 <= n,m <= 400). Далее в n строках содержится сама матрица. Каждая из этих строк содержит m целых чисел от 0 до 2147483647. Все элементы матрицы различны.

Выходные данные

Выведите искомый правый нижний элемент матрицы A_max.

Пример

Ввод

Test #1
2 3
1 2 3
4 5 6

Test #2
2 3
3 2 1
4 5 6

Вывод

Test #1
1

Test #2
3

Броневик I

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Имеется поисковая система, состоящая из броневика и нескольких разведчиков. Эта система была направлена для поисков сейфа с секретной документацией противника. В лабиринте один из посланных разведчиков обнаружил цель поисков - сейф. Сам разведчик вывезти сейф не в состоянии, но броневик, с которого были посланы разведчики, может это сделать. Разведчик составил план своего пути в виде списка команд: U (вверх), D (вниз), L (влево), R (вправо), и передал его на броневик. Путь разведчика не обязательно является кратчайшим. Броневик поедет к сейфу, проезжая с клетки на клетку, только если разведчик проходил здесь в этом же направлении, так как иначе он рискует попасть в ловушку. Требуется определить, какое минимальное количество топлива нужно броневику, чтобы доехать до сейфа.

Входные данные

В первой строке входного файла записаны целые числа M и T (1 <= M,T <= 100), где M - трата топлива для движения на 1, T - трата топлива для поворота на 90 градусов. Во второй строке записано целое число N (0 < N <= 100). В третьей - строка из N символов, задающая движение разведчика, каждый символ которой - это один из четырех символов U, D, L, R.

Выходные данные

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

Пример

Ввод

Test #1
3 7
6
UURDLL

Test #2
1 1
3
URD

Вывод

Test #1
13

Test #2
5

Черное-белое

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

На координатной плоскости нарисован многоугольник, все вершины которого имеют целые координаты, а все стороны параллельны осям координат. Все единичные клетки координатной плоскости окрашены в шахматном порядке в черный и белый цвета. Квадрат, у которого левый нижний угол имеет координаты (0, 0), имеет черный цвет. Ваша задача найти количество черных и белых квадратов внутри данного многоугольника.

Входные данные

В первой строке содержится натуральное число N (4 <= N <= 1000) - количество вершин многоугольника. Далее в N строках перечислены координаты вершин многоугольника в порядке обхода против часовой стрелки. Все координаты целые и не превосходят 10^9 по абсолютной величине. Многоугольник не содержит самопересечения и самокасания.

Выходные данные

Выведите два числа через пробел - количество черных клеток и количество белых клеток внутри многоугольника.

Пример

Ввод

12
1 0
2 0
2 1
3 1
3 2
2 2
2 3
1 3
1 2
0 2
0 1
1 1

Вывод

1 4

Радиопередатчики

ограничение времени на тест: 4.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Известно, что если рядом расположены два передатчика, вещающие на одной частоте, то качество приема резко ухудшается. Вам даны местоположения N передатчиков. Известно, что каждый из них может использовать одну из двух доступных частот. Мощности всех передатчиков равны между собой и равны W. В данном случае под мощностью понимается радиус действия уверенного приема вокруг передатчика. Какую наибольшую мощность W могут иметь эти передатчики, чтобы не существовало области положительной площади уверенного приема двух передатчиков, вещающих на одинаковой частоте? Выбор частоты вещания каждого передатчика остается за вами. Профессор Кнутмен утверждает, что существует решение этой задачи за время, пропорциональное квадрату числа N, и это решение достаточно эффективно для полного решения этой задачи.

Входные данные

В первой строке входного файла содержится целое число N (3 <= N <= 7500) -- количество передатчиков. Далее в N строках записаны координаты каждого передатчика. Все координаты целые числа, не превосходящие 10000 по абсолютной величине. Все передатчики имеют различные координаты.

Выходные данные

В первую строку выведите максимальную мощность передатчиков W. Мощность выводите не менее чем с шестью знаками после запятой. Во вторую строку выведите N чисел -- номера частот передатчиков. Число 1 в i-ой позиции обозначает, что i-ый передатчик должен вещать на первой частоте. Число 2 обозначает, что на второй. Если решений несколько, выведите любое.

Пример

Ввод

4
0 0
0 1
1 0
1 1

Вывод

0.70710678118654752
1 2 2 1

Резисторы

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Радиолюбитель Петя решил собрать детекторный приемник. Ему понадобился резистор с сопротивлением R Ом. В распоряжении Пети есть набор из n резисторов, сопротивления которых равны r1, r2,..., rn Ом соответственно. Петя помнит, как вычисляется сопротивление последовательного соединений двух резисторов Rnew = R1 + R2 и параллельного соединения двух резисторов Rnew = (R1 * R2) / (R1 + R2). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора резисторов такую, что ее сопротивление ближе всего к R Ом (то есть абсолютная величина разности значений должна быть минимальна).
Напомним, что схема, составленная из одного резистора, -- последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, -- последовательно-параллельная, также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, -- последовательно-параллельная.
Разумеется, Петя не обязан использовать для изготовления схемы все имеющиеся резисторы.

Входные данные

В первой строке входного файла заданы числа n, R (1 <= n <= 7; 10 <= R <= 3000). Число R - вещественное, заданное не более чем с 4 знаками после запятой. Во второй строке содержится последовательность сопротивлений имеющихся в наличии резисторов r1, r2,..., rn. Значения всех сопротивлений могут быть вещественными числами от 10 до 3000.

Выходные данные

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

Пример

Ввод

3 1.66
1 2 1

Вывод

1.666666666666666