---> 3 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задана таблица, некоторые клетки содержат города. Расстояние между городами определяется как |x1 - x2| + |y1 - y2|. Требуется выбрать место для столицы так, чтобы суммарное расстояние до всех городов было минимальным. Столица не должна совпадать с существующим городом.

В некотором царстве, в некотором государстве было $N$ городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |$x_1$ - $x_2$| + |$y_1$ - $y_2$|.

Император решил построить $N$+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

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

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

В первой строке вводится число $N$ - количество городов (1 <= $N$ <= 100). Следующие $N$ строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.

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

Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.

Примеры
Входные данные
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2
Выходные данные
1 1
Входные данные
4
0 0
1 1
0 1
1 0
Выходные данные
0 -1
Дано N последовательностей. Требуется для каждой пары последовательностей найти медиану объединения этих последовательностей.

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

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

Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются последовательности. Каждая последовательность состоит из L чисел, по модулю не превышающих 30000.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример

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

3 6

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
	

	

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

7

10

9
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить $\frac{10}{4}=2.5$ литра воды, а продать они эту воду смогут за $2.5 \times 6=15$ золотых слитков. Таким образом, прибыль пандорианцев составила бы $15-10=5$ золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

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

В первой строке задано целое число N — количество дней в году на планете Арракис.

Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .

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

Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.

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

Примечание

Тесты к этой задаче состоят из трёх групп.

  • Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

  • Тесты 3–7. В тестах этой группы 2 ≤ N ≤ 1000 . Тесты в этой группе оцениваются независимо. Каждый успешно пройденный тест оценивается в 10 баллов.

  • Тесты 8–12. В тестах этой группы 2 ≤ N ≤ 100 000 . Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура. Тесты в этой группе оцениваются независимо. Каждый успешно пройденный тест оценивается в 10 баллов.

Примеры
Входные данные
6
10 3 5 3 11 9
Выходные данные
2 5
Входные данные
4
5 5 5 5
Выходные данные
0 0

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест