Алгоритмы

Дана строка, в которой буква h встречается минимум два раза. Удалите из этой строки первое и последнее вхождение буквы h, а также все символы, находящиеся между ними.

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

Вводится строка.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	In the hole in the ground there lived a hobbit	In tobbit

В космические шахматы играют на бесконечной доске, поэтому клетки нумеруют парой чисел (см. пример и рисунок к нему). Фигуры ходят по обычным правилам. Составьте маршрут шахматного коня из клетки (0; 0) в заданную клетку (x; y).
Напомним, что конь за один ход перемещается на одну клетку по одной оси и на две по другой, то есть, например, из клетки (0; 0) он за один ход может попасть в клетки (1; 2), (2; 1), (-1; 2), (2; -1), (1; -2), (-2; 1), (-1; -2) и (-2; -1).

В качестве ответа Вам нужно вывести любой (не обязательно кратчайший) маршрут с началом в (0; 0) и концом в (x; y), длина которого не больше 10⁵ ходов.

Формат входных данных
Программа получает на вход два целых числа x и y, записанных в отдельных строках, - координаты конечной клетки маршрута коня. Клетка (x; y) не совпадает с началом координат. |x| <= 10⁵, |y| <= 10⁵.

Формат выходных данных
Программа должна вывести последовательность ходов, один ход в отдельной строке. В i-й строке должно быть выведено два числа x_i и y_i через пробел - координаты клетки, в которой окажется конь после i-го хода. Количество ходов не должно превышать 10⁵. Последний ход должен вести в заданную клетку
 

Ввод	Вывод
-2 2	-2 1 0 2 -1 0 -2 2

Рисунок к примеру

Дано число N (\(1<=N<=1000\)), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине. 

Входные данные 
В первой строке задаётся число N.

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

Примеры

№	Входные данные	Выходные данные
1	5	1 4 5 3 2

 

Пояснение

Худшее время работы достигается когда массив разбивается так, что одна часть содержит n−1 элементов, а вторая — 1. Этого можно добиться если на каждом этапе разбиения в середине будет максимальный элемент.
1) 1 4 5 3 2
2) 1 4 2 3 5
3) 1 3 2 4 5
4) 1 2 3 4 5
5) 1 2 3 4 5

 

На некоторых кросс-платформенных станциях метро (как, например, "Третьяковская") на разные стороны платформы приходят поезда разных направлений. Таня договорилась встретиться с подругой на такой станции, но поскольку подруга приехала из другого часового пояса, то из-за джетлага сильно проспала, и Тане пришлось долго её ждать. Поезда всегда ходят точно по расписанию, и Таня знает, что поезд стоит на платформе ровно одну минуту, а интервал между поездами (время, в течение которого поезда у платформы нет) составляет a минут для поездов на первом пути и b минут для поездов на втором пути. То есть на первый путь приезжает поезд и стоит одну минуту, затем в течение a минут поезда у платформы нет, затем в течение одной минуты у платформы стоит следующий поезд и т. д.

Пока Таня стояла на платформе, она насчитала n поездов на первом пути и m поездов на втором пути. Определите минимальное и максимальное время, которое Таня могла провести на платформе, или сообщите, что она точно сбилась со счёта.

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

Входные данные
Первая строка входных данных содержит число a - интервал между поездами на первом пути. Вторая строка содержит число b - интервал между поездами на втором пути. Третья строка содержит число n - количество поездов на первом пути, которые увидела Таня. Четвёртая строка
содержит число m - количество поездов на втором пути, которые увидела Таня. Все числа - целые,
от 1 до 1000.

Выходные данные
Программа должна вывести два числа: минимальное и максимальное время в минутах, которое Таня могла стоять на платформе, или одно число -1, если Таня точно ошиблась.
 

Ввод	Вывод
1 3 3 2	5 7
1 5 1 2	-1

Замечание: В первом примере по первому пути поезда ходят через 1 минуту. По второму - через 3. Стоя на платформе 5, 6 или 7 минут, Таня могла насчитать 3 поезда на первом пути и 2 на втором.
 

Некоторые уроки в школе для Вани и Пети  очень скучны. На этих уроках Петя и Ваня придумали игру. Сначала мальчики записывают на листке два различных натуральных числа a и b .
Ход игры заключается в следующем: среди записанных чисел выбирают p и q такие, что модуля их разности \(| p - q |\) еще нет на листке, и дописывают его.
Проигрывает тот, кто не может сделать ход.
Определите, кто из ребят окажется победителем при правильной игре обоих. Ваня вежливый мальчик, поэтому всегда ходит вторым.

Входные данные: В первой и единственной строке записано два различных натуральных числа 1 <= a , b <= 10^9 , разделенные пробелом - два исходных числа на листке.

Выходные данные: Выведите имя победителя в этой игре (Petya или Vanya)

Примечание: В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Ваня может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Ваня.

Примеры

№	Входные данные	Выходные данные
1	6 2	Petya
2	4 1	Vanya

Пятиклассник Петя любит решать различные математические задачи. Последняя его задача заключалась в том, чтобы по целым числам a, b, найти такие целые x и y, которые бы помогли построить треугольник ABC  минимальной (ненулевой) площади. Треугольник Пети должен иметь следующие координаты \(A = (0, 0)\), \(B = (a, b)\), \(C = (x, y)\).
Помогите ему определить какую минимальную площадь может иметь треугольник ABC?

Входные данные
Даны два целых числа a и b, по модулю не превосходящие 10⁹ (\(a^2 + b^2 > 0\)).

Выходные данные
Выведите одно число - минимальную возможную площадь треугольника ABC с точностью 10^- 6. 
 

Примеры

№	Входные данные	Выходные данные
1	4 0	2.0

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

1. Пусть a, b — числа, НОД которых надо найти.

2. Если b = 0, то число a — искомый НОД.

3. Если b > a, то необходимо поменять местами числа a и b.

4. Присвоить числу a значение a – b.

5. Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K (\(1 <= K <= 100\)). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (\(1 <= a,\ b <= 10^{18}\)). Вторая строка – два целых числа: c, d (\(1 <= c,\ d <= 10^{18}\)).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

 

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

 

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

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	20 27	540

Студент на первом курсе скачивал из интернета в среднем А Кбайт информации в день, а на втором курсе – В Кбайт, оплачивая одну и ту же сумму денег за полученный интернетный трафик в неделю. Какой наименьший объем информации в Кбайтах он скачивал за неделю?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	60 75	300

В теплице посадили в 2 ряда разные сорта орхидей. Цветы одного сорта разместили на расстоянии А см между растениями, а другого - на В см. Через какое расстояние орхидеи обоих сортов окажутся рядом? 

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	15 18	90

На математическом конкурсе ребята играли в увлекательную древнюю китайскую головоломку Танграм. В одном игровом комплекте было А остроугольных, а в другом - В тупоугольных треугольников. Какое наименьшее число участников могут пользоваться комплектами из одинакового количества каждого вида треугольников?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	12 15	60

Длина шага папы – А см, а у маленькой дочери – В см. Они начинают идти, поставив ноги на одну отметку. Какое расстояние они пройдут, чтобы их ноги опять встали вровень?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	70 15	210

На складе в коробки упаковывают волейбольные мячи. Сначала мячи пакуются в сетки ровно по  N штук в каждую, а потом сетки - в коробки, причем в одну коробку помещается не более L сеток. Последняя коробка может быть неполная. Всего имеется М мячей.  Сколько всего понадобится коробок, сколько сеток будет в последней коробке и сколько мячей останется на складе не упаковано  (упаковать нужно как можно больше мячей)? Написать программу: вводятся три числа целых M, L, N в одной строке; вывести три числа в одной строке - сначала количество потребовавшихся коробок, затем количество сеток в последней коробке, а затем количество не упакованных мячей
 
Примеры

№	Входные данные	Выходные данные
1	40 4 3	4 1 1

 

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

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

Входные данные: В первой строке вводится число n - количество селений (1 <= n <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Выходные данные: Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 10 2 7 3	2 2 1 1

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин  – ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

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

Входные данные: Первая строка входных данных содержит натуральное число N (1 ≤ N ≤ 1000)  – количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число  – для первого сотрудника, второе  – для второго и т.д.). Все расстояния  – положительные целые числа, не превышающие 1000. Далее записано еще N чисел  – тарифы за проезд одного километра в такси (первое число  – в первой машине такси, второе  – во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000. 

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

Примеры

№	Входные данные	Выходные данные
1	3 10 20 30 50 20 30	1 3 2
2	5 10 20 1 30 30 3 3 3 2 3	5 1 3 2 4

На планете Шелезяка поднялась буря из алмазной пыли. Как известно, алмазная пыль вызывает у роботов паралич. В момент начала бури все роботы были заняты работой вдоль одной прямой дороги. Вдоль этой же дороги расположены m ремонтных мастерских. Поэтому было решено направить каждого робота в ближайшую ремонтную мастерскую, чтобы обновить свою смазку. 
Необходимо для каждого робота определить ближайшую к нему ремонтную мастерскую.
 

Входные данные 
В первой строке вводится число n - количество роботов(\(1 <= n <= 100000\)). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до места работы i-го робота. В третьей строке входных данных задается число m - количество ремонтных мастерских (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-й ремонтной мастерской. Все расстояния положительны и не превышают 109.  Робот и мастерская могут располагаться в одной точке.

Выходные данные
Выведите n чисел - для каждого робота выведите номер ближайшей к нему ремонтной мастерской. Ремонтные мастерские пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

 

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 10 2 7 3	2 2 1 1

Требуется отсортировать массив по неубыванию методом "вставок".

Входные данные 
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные 
Вывести получившийся массив.
 

Пример

№	Входные данные	Выходные данные
1	5 5 4 3 2 1	1 2 3 4 5

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

1. Можно увеличить первую цифру числа на 1, если она не равна 9.
2. Можно уменьшить последнюю цифру на 1, если она не равна 1.
3. Можно циклически сдвинуть все цифры на одну вправо.
4. Можно циклически сдвинуть все цифры на одну влево.

Например, применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно. Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как получить из одного числа другое за минимальное количество операций.

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

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

Примеры

№	Входные данные	Выходные данные
1	1234 4321	1234 2234 3234 4323 4322 4321

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

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

Формат входных данных
В первых двух строках вводятся два натуральных числа N, K (\(1 <= N <= 100000\), \(1 <= K <= N\)) — количество бункеров и количество выходов соответственно. В третьей строке через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. В четвертой строке идёт число M (\(1 <= M <= 100000\)) — количество туннелей. В следующих M  строках вводятся пары чисел – номера бункеров, соединенных туннелем.
По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

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