Однажды Васе понадобилось найти вторую порядковую статистику последовательности целых чисел, то есть такое значение, которое попадет на второе место после сортировки всех различных элементов данной последовательности. Другими словами, надо найти наименьший элемент строго больший минимума. Помогите Васе справиться с этой задачей.
В первой строке входных данных содержится целое число n (1 ≤ n ≤ 100) — количество чисел в последовательности. Во второй строке через пробел записаны n целых чисел — элементы последовательности. Эти числа не превосходят по модулю 100.
Если в заданной последовательности вторая порядковая статистика существует, выведите ее, иначе выведите NO.
4
1 2 2 -4
1
5
1 2 3 1 1
2
Вася хочет поставить в офис новый стол для переговоров. Для этого он тщательно все измерил и составил план своего офиса: офис Васи представляет собой прямоугольную комнату n × m метров. Каждый квадратный метр офиса может быть либо занят чем-то, либо свободен. Стол для переговоров имеет прямоугольную форму, и должен стоять так, чтобы его стороны были параллельны стенам офиса. Вася не хочет ничего менять или передвигать, поэтому все клетки, занимаемые столом, должны быть свободны. Чтобы за столом поместилось как можно больше людей, его периметр должен быть как можно больше. Помогите Васе определить наибольший возможный периметр стола, помещающегося в офисе.
В первой строке через пробел записано 2 целых числа n и m (1 ≤ n, m ≤ 25) — размеры офиса. Далее следует n строк по m символов 0 или 1. 0 обозначает, что соответствующий квадратный метр офиса свободен. 1 обозначает, что соответствующий квадратный метр офиса чем-то занят. Гарантируется, что хотя бы один квадратный метр Васиного офиса свободен.
Выведите одно число — наибольший возможный периметр стола, помещающегося в Васином офисе.
3 3
000
010
000
8
5 4
1100
0000
0000
0000
0000
16
Вася устроился на работу системным администратором в корпорацию X. Первым его заданием было соединить n серверов с помощью m двусторонних прямых соединений так, чтобы данные с любого сервера можно было передать на любой другой по проложенной сети. Каждое прямое соединение должно соединять два различных сервера, причем между каждой парой серверов должно быть не более одного прямого соединения. Корпорация Y, конкурент корпорации X, сделала Васе предложение, от которого он не смог отказаться: Вася должен проложить сеть так, чтобы в случае выхода из строя сервера с номером v, передача данных между некоторыми двумя серверами, отличными от v, становилась невозможной, то есть сеть переставала быть связной. Помогите Васе проложить сеть.
В первой строке входных данных через пробел записаны 3 целых числа n, m, v (3 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ v ≤ n), n — число серверов, m — число прямых соединений, v — номер сервера, при поломке которого должна ломаться вся сеть.
Если искомой схемы соединений не существует, выведите -1. Иначе выведите m строк по 2 числа в каждой — описание всех прямых соединений в сети. Каждое прямое соединение описывается двумя числами — номерами двух соединяемых серверов. Серверы нумеруются начиная с 1. Если решений несколько, выведите любое.
5 6 3
1 2
2 3
3 4
4 5
1 3
3 5
6 100 1
-1
Дано n отрезков на числовой прямой. Вы можете забить в любую целочисленную точку числовой прямой гвоздь, при этом все отрезки, содержащие эту точку, оказываются прибиты. Если гвоздь попадает в конец отрезка, то этот отрезок считается прибитым. Какое наименьшее число гвоздей нужно забить чтобы все отрезки оказались прибиты?
В первой строке содержится целое число n (1 ≤ n ≤ 1000) — количество отрезков. Далее в n строках содержится описание отрезков. Каждый отрезок описывается двумя целыми числами — координатами концов. Все координаты не превосходят по модулю 10000. Отрезки могут вырождаться в точки.
В первую строку выведите одно число — какое наименьшее число гвоздей нужно забить чтобы все отрезки оказались прибиты. Во вторую строку выведите координаты забитых гвоздей через пробел в любом порядке. Если решений несколько, выведите любое.
2
0 2
2 5
1
2
5
0 3
4 2
4 8
8 10
7 7
3
7 10 3
Чтобы как можно быстрее узнавать последние новости о своей любимой принципиально новой операционной системе, BolgenOS community Нижнего Тагила решило разработать схему, согласно которой первый член community, узнавший какую-либо новость, звонит кому-то другому, тот звонит третьему и так далее. То есть человеку с номером i был назначен человек с номером fi, которому он должен звонить, как только сам узнает новость. Со временем участники BolgenOS community поняли, что их схема не всегда срабатывает — некоторые могут так и не узнать новость. Теперь они хотят дополнить ее: в схему добавляется несколько указаний вида (xi, yi), означающих, что человек xi должен позвонить еще и человеку yi. Какое наименьшее число указаний нужно добавить, чтобы, независимо от того, кто первый узнал новость, в итоге новость узнали все?
В первой строке входных данных записано число n (2 ≤ n ≤ 105) — количество участников BolgenOS community Нижнего Тагила. Во второй строке через пробел записано n целых чисел fi (1 ≤ fi ≤ n, i ≠ fi) — номер человека, которому звонит человек с номером i.
В первую строку выходных данных выведите одно число — какое наименьшее число указаний нужно добавить. Далее выведите один из возможных вариантов добавления этих указаний в схему, по одному указанию в строке. Если решений несколько, выведите любое.
3
3 3 2
1
3 1
7
2 3 1 3 4 4 1
3
2 5
2 6
3 7