Задача A. Ближайшие точки ≡

Условие

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: "На числовой прямой задано n точек. Необходимо найти среди них две ближайшие". Расстояние между двумя точками числовой прямой x и y равно |x − y|.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

Формат входного файла

Первая строка входного файла содержит количество точек n.

Вторая строка входного файла содержит n чисел x_i - координаты заданных точек числовой прямой.

Формат выходного файла

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

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

Если ответов несколько, выведите любой из них.

Ограничения

2 ≤ n ≤ 10⁵

x_i - целые числа, не превосходящие 10⁹ по абсолютной величине

Примеры тестов

5
10 3 6 2 5

1
2 4

Задача B. В какую группу? ≡

Условие

Межгалактический Институт Математики и Программирования набирает студентов. Все абитуриенты должны сдать два экзамена: по математике и информатике, после чего, исходя из результатов, их возьмут (или не возьмут) в одну из трех учебных групп, закреплённых за тремя кафедрами. Первая кафедра набирает в первую очередь студентов с высоким баллом по математике, вторая — по информатике, а третья предпочитает студентов, у которых баллы по информатике и математике меньше всего отличаются, даже если эти баллы низкие.

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

Руководитель первой кафедры каждый раз берет студента с максимальным баллом по математике среди всех оставшихся, а если таких несколько — студента с максимальным баллом по информатике среди них.

Руководитель второй кафедры принимает студента с максимальным баллом по информатике, а если таких несколько — студента с максимальным баллом по математике среди них.

Руководитель третей кафедры берет студента с минимальной про модулю разницей баллов по этим двум экзаменам и, если этому условию удовлетворяют несколько студентов, то поступает в точности как руководитель первой кафедры.

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

Формат входного файла

Входной файл содержит число N, за которым следует N пар целых чисел a_i b_i — баллы i-го абитуриента по математике и информатике соответственно. Гарантируется, что нет двух абитуриентов, у которых совпадают баллы по обоим экзаменам.

Формат выходного файла

Выходной файл должен содержать N целых чисел — номера студентов в порядке их зачисления.

Ограничения

1 ≤ N ≤ 10⁵; 1 ≤ a_i, b_i ≤ 10⁶

Примеры тестов

1
1 1

1

3 
1 1 2 1 2 2

3 2 1

Задача C. Автостоянка на улице Кантора ≡

Условие

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

Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.

Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).

Требуется написать программу, которая для каждого из N данных номеров мест определит их координаты.

Рекомендуется рассмотреть частичные решения

N = 1

C ≤ 10⁶

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ C_i ≤ 10⁹

Примеры тестов

1
1

1 0

2
20101204
226

6106 234
4 16

Задача D. rrrrr... ≡

Условие

Определим функцию r(p, q), где p и q — строки символов, следующим образом: функция удаляет первый символ из строки p, и присоединяет к концу получившейся строки первый символ строки q. Например, r('abc', 'def') = 'bcd'.

Исходя из данной строки x можно сгенерировать различные выражения, например r(x,x), r(r(x,r(x,x)),x) и т.п. Требуется сгенерировать выражение, значение которого равно строке y, либо определить, что это невозможно.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

ab
ba

r(x,x)

ab
xy

NO

Задача E. Беговые дорожки ≡

Условие

Между n спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с n − 1 беговой дорожкой, поэтому одновременно могут состязаться только n − 1 из n участников. По этой причине соревнования разбиваются на несколько забегов.

Правила соревнований требуют, чтобы каждый из бегунов:

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

Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного «неприятного» ему конкурента, и чувство антипатии является взаимным.

Требуется по заданному числу спортсменов, а также списку их антипатий, составить расписание забегов, удовлетворяющее требованиям организаторов. Гарантируется, что решение существует. При наличии нескольких решений, допустимо любое из них.

Формат входного файла

В первой строке входного файла находятся целые числа n m. В следующих m строках записаны пары чисел — номера спортсменов, которых нельзя ставить на соседние дорожки в одном забеге. Спортсмены нумеруются натуральными числами от 1 до n.

Формат выходного файла

Первая строка выходного файла должна содержать число забегов r в предлагаемой схеме. Следующие r строк должны состоять из n − 1 числа — номеров спортсменов, выставляемых на дорожки в каждом из забегов.

Ограничения

2 ≤ n ≤ 100.

1 ≤ r ≤ 1000.

Примеры тестов

4 1
2 3

4
4 2 1
1 3 4
2 1 3
3 4 2

Задача F. Оригами ≡

Условие

Складывание фигуры начинается с квадратного листа бумаги, лежащего на специальной (также квадратной) учебной доске для оригами. Доска размечена на n × n клеток, стороны которых параллельны её краям. Через все клетки доски проведены диагонали двух типов: пересекающие клетки сверху вниз слева направо (\) и справа налево (/). Две диагонали, соединяющие противоположные углы доски, называются главными.

Схема складывания фигуры состоит из последовательных указаний о сгибах. Каждый сгиб проходит вдоль одной из 4n − 2 диагоналей доски, при этом бумага всегда загибается в сторону центра доски. Таким образом, для диагоналей, расположенных выше главной, возможен только сгиб вниз, для диагоналей, расположенных ниже главной, — только сгиб вверх. Сгиб, проходящий через главную диагональ, возможен как в одну, так и в другую сторону.

Требуется по данному размеру n и схеме сгибов определить конечный вид листа. Для каждой клетки доски необходимо вывести символ, характеризующий её вид, сформированный сложенной бумагой. Соответствие символов содержимому клеток приведено на рисунке.

Ниже показан процесс складывания фигуры по схеме, приведённой в примере 2.

→

→

Формат входного файла

В первой строке входного файла находятся числа n и m. Вторая строка содержит схему сборки — описание m сгибов, которые необходимо выполнить с листом бумаги.

Каждый сгиб задаётся положением диагонали, вдоль которой он должен быть произведён, и состоит из трёх компонент.

1. Тип диагонали — символ '/' (ASCII 47) или '\' (ASCII 92).
2. Направление сгиба листа — символ 'u' (ASCII 117) для сгиба вниз или 'l' (ASCII 108) для сгиба вверх; однозначно определяет положение относительно главной диагонали.
3. Номер диагонали — целое число от 1 до n. Диагонали каждого типа, расположенные по одну сторону от главной, нумеруются по возрастанию от угла доски к главной диагонали.

Формат выходного файла

Выходной файл должен содержать n строк по n символов в каждой — вид каждой из клеток сборочной доски после выполнения всех сгибов, указанных в схеме.

Ограничения

1 ≤ n ≤ 100, 0 ≤ m ≤ 4n − 2.

Гарантируется, что к моменту выполнения любого сгиба по обе стороны от указанной диагонали имеется некоторый участок бумаги.

Примеры тестов

3 2
\u1/u3

~~^
~,#
,##

4 3
/l3\u2/u3

~~^~
~,#>
,##~
#'~~