Автор: | Методическая комиссия по информатике | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.
Готовясь к контрольной работе, Антон столкнулся со следующей задачей: "На числовой прямой задано n точек. Необходимо найти среди них две ближайшие". Расстояние между двумя точками числовой прямой x и y равно |x − y|.
Требуется написать программу, которая поможет Антону решить поставленную задачу.
Первая строка входного файла содержит количество точек n.
Вторая строка входного файла содержит n чисел xi - координаты заданных точек числовой прямой.
В первой строке выходного файла необходимо вывести минимальное расстояние между двумя точками, заданными во входном файле.
Во второй строке выходного файла необходимо вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от 1 до n в порядке, в котором они заданы во входной файле.
Если ответов несколько, выведите любой из них.
2 ≤ n ≤ 105
xi - целые числа, не превосходящие 109 по абсолютной величине
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | М. Спорышев | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Межгалактический Институт Математики и Программирования набирает студентов. Все абитуриенты должны сдать два экзамена: по математике и информатике, после чего, исходя из результатов, их возьмут (или не возьмут) в одну из трех учебных групп, закреплённых за тремя кафедрами. Первая кафедра набирает в первую очередь студентов с высоким баллом по математике, вторая — по информатике, а третья предпочитает студентов, у которых баллы по информатике и математике меньше всего отличаются, даже если эти баллы низкие.
В день распределения руководители трех кафедр делают выбор по очереди, пока не разберут всех студентов.
Руководитель первой кафедры каждый раз берет студента с максимальным баллом по математике среди всех оставшихся, а если таких несколько — студента с максимальным баллом по информатике среди них.
Руководитель второй кафедры принимает студента с максимальным баллом по информатике, а если таких несколько — студента с максимальным баллом по математике среди них.
Руководитель третей кафедры берет студента с минимальной про модулю разницей баллов по этим двум экзаменам и, если этому условию удовлетворяют несколько студентов, то поступает в точности как руководитель первой кафедры.
Чтобы сократить время распределения студентов Вам требуется написать программу, которая зная баллы каждого студента по каждому из экзаменов распределит их по трем группам в требуемом порядке.
Входной файл содержит число N, за которым следует N пар целых чисел ai bi — баллы i-го абитуриента по математике и информатике соответственно. Гарантируется, что нет двух абитуриентов, у которых совпадают баллы по обоим экзаменам.
Выходной файл должен содержать N целых чисел — номера студентов в порядке их зачисления.
1 ≤ N ≤ 105; 1 ≤ ai, bi ≤ 106
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | В. Степанец, А. Кленин | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Автостоянка, находящаяся поблизости от улицы имени Г. Кантора, ограничена с севера и запада домами, а с востока и юга открыта в большое поле.
Чтобы упорядочить размещение автомобилей, владелец стоянки решил пронумеровать места на ней и выделить каждому клиенту номер и соответствующее место. Нумерацию решено производить так: месту в углу стоянки присвоен номер ноль, далее нумерация идёт по диагоналям в направлении с северо-востока на юго-запад.
0 | 1 | 3 | 6 | 10 | … |
2 | 4 | 7 | 11 | … | |
5 | 8 | 12 | … | ||
9 | 13 | … | |||
14 | … | ||||
… |
Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).
Требуется написать программу, которая для каждого из N данных номеров мест определит их координаты.
N = 1
C ≤ 106
1 ≤ N ≤ 105
0 ≤ Ci ≤ 109
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | А. Кленин | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Определим функцию r(p, q), где p и q — строки символов, следующим образом: функция удаляет первый символ из строки p, и присоединяет к концу получившейся строки первый символ строки q. Например, r('abc', 'def') = 'bcd'.
Исходя из данной строки x можно сгенерировать различные выражения, например r(x,x), r(r(x,r(x,x)),x) и т.п. Требуется сгенерировать выражение, значение которого равно строке y, либо определить, что это невозможно.
NO
,
если такого выражения не существует. Выражение не должно содержать пробелов.
Если решений несколько, то следует вывести любое из них.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | И. Бураго | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Между n спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с n − 1 беговой дорожкой, поэтому одновременно могут состязаться только n − 1 из n участников. По этой причине соревнования разбиваются на несколько забегов.
Правила соревнований требуют, чтобы каждый из бегунов:
Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного «неприятного» ему конкурента, и чувство антипатии является взаимным.
Требуется по заданному числу спортсменов, а также списку их антипатий, составить расписание забегов, удовлетворяющее требованиям организаторов. Гарантируется, что решение существует. При наличии нескольких решений, допустимо любое из них.
В первой строке входного файла находятся целые числа n m. В следующих m строках записаны пары чисел — номера спортсменов, которых нельзя ставить на соседние дорожки в одном забеге. Спортсмены нумеруются натуральными числами от 1 до n.
Первая строка выходного файла должна содержать число забегов r в предлагаемой схеме. Следующие r строк должны состоять из n − 1 числа — номеров спортсменов, выставляемых на дорожки в каждом из забегов.
2 ≤ n ≤ 100.
1 ≤ r ≤ 1000.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | И. Бураго | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Складывание фигуры начинается с квадратного листа бумаги, лежащего на специальной (также квадратной) учебной доске для оригами. Доска размечена на n × n клеток, стороны которых параллельны её краям. Через все клетки доски проведены диагонали двух типов: пересекающие клетки сверху вниз слева направо (\) и справа налево (/). Две диагонали, соединяющие противоположные углы доски, называются главными.
Схема складывания фигуры состоит из последовательных указаний о сгибах. Каждый сгиб проходит вдоль одной из 4n − 2 диагоналей доски, при этом бумага всегда загибается в сторону центра доски. Таким образом, для диагоналей, расположенных выше главной, возможен только сгиб вниз, для диагоналей, расположенных ниже главной, — только сгиб вверх. Сгиб, проходящий через главную диагональ, возможен как в одну, так и в другую сторону.
Требуется по данному размеру n и схеме сгибов определить конечный вид листа. Для каждой клетки доски необходимо вывести символ, характеризующий её вид, сформированный сложенной бумагой. Соответствие символов содержимому клеток приведено на рисунке.
Ниже показан процесс складывания фигуры по схеме, приведённой в примере 2.
![]() | → | ![]() | → | ![]() |
В первой строке входного файла находятся числа n и m. Вторая строка содержит схему сборки — описание m сгибов, которые необходимо выполнить с листом бумаги.
Каждый сгиб задаётся положением диагонали, вдоль которой он должен быть произведён, и состоит из трёх компонент.
Выходной файл должен содержать n строк по n символов в каждой — вид каждой из клеток сборочной доски после выполнения всех сгибов, указанных в схеме.
1 ≤ n ≤ 100, 0 ≤ m ≤ 4n − 2.
Гарантируется, что к моменту выполнения любого сгиба по обе стороны от указанной диагонали имеется некоторый участок бумаги.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|