Страница: << 5 6 7 8 9 10 11 >> Отображать по:
#495
Матрица
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан набор натуральных чисел: a1, …, aN. По этому набору строится таблица чисел размером N x N по следующему правилу: в клетку i-го столбца j-й строки записывается большее из чисел ai и aj при i ≠ j (если ai = aj, то записывается это число); на пересечении i-го столбца и i-й строки записывается число 0.

Дана таблица чисел. Требуется определить, могла ли она быть построена по данным правилам из какого-либо набора чисел a1, …, aN.

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

В первой строке входных данных задается натуральное число N – размер таблицы (1 ≤ N ≤ 500). В следующих N строках содержится по N чисел – числа соответствующей строки из таблицы (все числа целые неотрицательные и не превосходят 1 000).

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

В одну строку выведите через пробел числа a1, …, aN. Если решений несколько, выведите любое из них. Если набора, удовлетворяющего данной таблице, не существует, выведите одно число "-1".

Примеры
Входные данные
3
0 4 6
4 0 6
6 6 0
Выходные данные
4 4 6
Входные данные
2
0 1
2 0
Выходные данные
-1
#496
Точки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.

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

В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).

В каждой из следующих N строк записаны по два числа xi, yi – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 106. Некоторые точки могут совпадать.

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

Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.

Примеры
Входные данные
1
0 0
Выходные данные
5.6568542495
Входные данные
2
1 1
1 2
Выходные данные
7.6568542495
#497
Автобусы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В столице одной Очень Демократической Страны все жители в 8 часов утра одновременно выходят со станций метро, ближайших к месту своей работы, и дальше добираются до работы на автобусах. Мэр города хочет построить еще одну станцию метро так, чтобы после этого время, к которому все люди доберутся до места своей работы (то есть время, когда последний работник окажется на работе), было наименьшим возможным.

Автобусное сообщение в столице устроено следующим образом. Есть N автобусных остановок, в частности, возле каждой станции метро расположено по остановке. Между N – 1 парой остановок постоянно курсируют автобусы, время движения от одной остановки до другой – 1 минута. Временем ожидания и пересадки можно пренебречь. Автобусное сообщение в столице организовано так, что от любой автобусной остановки до любой другой можно добраться на автобусах (возможно, с пересадками).

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

В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

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

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

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

Выведите два числа – сначала наибольшее время за которое кто-то будет и после строительства добираться на работу, а затем номер автобусной остановки, рядом с которой следует построить новую станцию метро. (Строить можно возле тех автобусных остановок, возле которых еще нет станций метро). Если решений несколько, выведите одно из них.

Подзадачи и система оценки

Данная задача содержит две подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Подзадача 1 (40 баллов)

В этой подзадаче \(N \leq 2000\)

Подзадача 2 (60 баллов)

Дополнительные ограничения отсутствуют.

Примеры
Входные данные
8 2
1 2
1 2
1 3
1 4
2 5
2 6
6 7
6 8
Выходные данные
1
6
Входные данные
8 2
5 3
1 2
1 3
1 4
2 5
2 6
6 7
6 8
Выходные данные
2
6
#506
Строки в книге
  
Темы: [Целые числа]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В книге на одной странице помещается \(K\) строк. Таким образом, на 1-й странице печатаются строки с 1-й по \(K\)-ю, на второй — с (\(K\)+1)-й по (2∙\(K\))-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

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

Вводятся два числа: \(K\) — количество строк, которое печатается на странице, и \(N\) — номер строки (1≤\(K\)≤200, 1≤\(N\)≤20000).

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

Выведите два числа — номер страницы, на которой будет напечатана эта строка, и номер строки на странице.

Примеры
Входные данные
50 1
Выходные данные
1 1
Входные данные
20 25
Выходные данные
2 5
Входные данные
15 43
Выходные данные
3 13
#507
Симметричная последовательность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

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

Сначала вводится число \(N\) — количество элементов исходной последовательности (1 ≤ \(N\) ≤ 100). Далее идут \(N\) чисел — элементы этой последовательности, натуральные числа от 1 до 9.

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

Выведите сначала число \(M\) — минимальное количество элементов, которое надо дописать к последовательности, а потом \(M\) чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.

Примеры
Входные данные
9
1 2 3 4 5 4 3 2 1
Выходные данные
0
Входные данные
5
1 2 1 2 2
Выходные данные
3
1 2 1
Входные данные
5
1 2 3 4 5
Выходные данные
4
4 3 2 1
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест