#1877

Выпуклая оболочка

Темы: [Многоугольники. Выпуклые оболочки]

На плоскости даны \(N\) точек. Вам требуется построить выпуклую оболочку данного множества точек. Если \(N\) нечетно, то оболочку нужно выводить в порядке обхода по часовой стрелке, иначе — против часовой стрелки.

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

Первая строка содержит количество точек \(N\), \(1\le N\le 20\,000\). Каждая из последующих \(N\) строк содержит два целых числа — координаты \(x_i\) и \(y_i\). Все числа по модулю не превосходят \(10^4\).

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

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

Примеры

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

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

#1886

Сортировка

Темы: [Использование сортировки]

Мария Ивановна, учитель средней школы 5 села Уборкино, заполняет классный журнал. Но она неожиданно столкнулась с проблемой: список имен, который у неё есть, не отсортирован. Помогите ей! Список необходимо отсортировать в алфавитном порядке по фамилиям. Люди с одинаковой фамилией должны идти в том же порядке, в котором они идут в исходном списке.

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

Первая строка входного файла содержит натуральное число \(N\) (\(1\leq N\leq 20\,000\)) — количество человек в классе. Далее идут \(N\) строк, содержащих по два слова, записанных через пробел: фамилия и имя ученика. В записи фамилии и имени встречаются только буквы латинского алфавита, причём первая буква всегда большая, а остальные — маленькие. Длина фамилии не менее 1 и не более 20. Длина имени не менее 1 и не более 20.

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

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

Примеры

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

4
Pupkin Vasya
Ivanov Petya
Iskandeev Semil
Ivanov Roma

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

4
Iskandeev Semil
Ivanov Petya
Ivanov Roma
Pupkin Vasya

#1887

Подстрока

Темы: [Поиск подстроки в строке]

Ваша задача — найти все вхождения данной строки в длинный текст.

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

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

Все символы с ASCII кодами 33126 (кроме «*») допустимы и могут встречаться как в строке, так и в тексте. Все пробелы и символы перевода строки во входном файле должны игнорироваться.

Длина строки не превосходит 10000, а длина текста не превосходит 200000 символов.

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

Выведите в выходной файл в возрастающем порядке все точки вхождения данной строки в данный текст. Точка вхождения — это количество символов от начала текста до первого символа вхождения, увеличенное на 1. Если вхождение начинается сразу после звездочки, то точка его вхождения равна 1.

Примеры

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

aa* bb
aaa

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

3
4

#1905

Удаление скобок

Темы: [Динамическое программирование по подстрокам]

Дана строка, составленная из круглых, квадратных и фигурных скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.

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

Строка из круглых, квадратных и фигурных скобок. Длина строки не превосходит 100 символов.

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

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

Примеры

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

([)]

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

[]

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

{([(]{)})]

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

[({})]

#1906

Распил брусьев

Темы: [Динамическое программирование по подстрокам]

Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет \(k\) рублей за распил одного бруска длиной \(k\) метров на две части.

Понятно, что различные способы распила приводят к различной суммарной стоимости заказа. Например, рассмотрим брус длиной 10 метров, который нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить сначала на отметке 2 м, потом 4 и, наконец, 7 м. Это приведет к стоимости 10+8+6=24, потому что сначала длина бруса, который пилили, была 10 м, затем она стала 8 м, и, наконец, 6 м. А можно распилить иначе: сначала на отметке 4 м, затем 2, затем 7м. Это приведет к стоимости 10+4+6=20, что лучше.

Определите минимальную стоимость распила бруса на заданные части.

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

Первая строка входных данных содержит целое число \(L\) (2≤\(L\)≤\(10^6\)) - длину бруса и целое число \(N\) (1≤\(N\)≤100) - количество распилов. Во второй строке записано \(N\) целых чисел \(С_i\) (0<\(C_i\)<\(L\)) в строго возрастающем порядке - места, в которых нужно сделать распилы.

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

Выведите одно натуральное число - минимальную стоимость распила.

Примеры

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

10 3
2 4 7

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