Алгоритмы

В теплице посадили в 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.

Громозека с планеты Чумороза впечатлителен, раним, легко приходит в уныние и начинает плакать, попутно выпуская из ноздрей едкий дым. 
Громозека привез со своей родной планеты N штук жевательных лент, которую так любят земные дети. Он хочет поделить все ленты между K детьми. Но, оказывается, если у детей размер жевательной ленты будет различным, то они начнут ругаться и ссориться. В этот момент Громозека придёт в уныние. 
Помогите Громозеке поделить все жевательные ленты таким образом, чтобы из них можно было набрать K штук одинаковых. Радость детей прямо пропорциональна длине жевательных лент. Громозека хочет, чтобы дети получили как можно больше радости.
 

Входные данные
В первой строке заданы два числа - N (1 <= N <= 10001) и K (1 <= K <= 10001). Далее, в каждой из последующих N строк, записано по одному числу - длина каждой привезенной жевательной ленты. Длина ленты задана в сантиметрах. Все длины лежат в интервале от 1 до 10⁷ сантиметров включительно.

Выходные данные
Выведите одно целое число - максимальную длину жевательной ленты в сантиметрах. В случае, если Громозека придёт в уныние, выведите 0.
 

Примеры

№	Входные данные	Выходные данные
1	4 11 802 743 457 539	200

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

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

• Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
• Суммарная прибыль от выполнения этих задач была максимальна.

Составьте план, обладающий описанными выше свойствами и определите прибыль, получаемую в результате выполнения этого плана.

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

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

В первой строке  находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа ti и pi (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

 

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
 

Формат входных данных
В первой строке находятся числа N и K. В следующих N строках L1, L2, ..., LN, по одному числу в строке.

Ограничения 

• 1 <= N <= 10 000,
• 1 <= K <= 10 000,
• 100 <= Li <= 10 000 000,
• все числа целые.

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

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

•  Налить воду в первую колбу до края (после этого в ней будет a миллилитров воды)
•  Полностью вылить воду из первой колбы
•  Налить воду во вторую колбу до края (после этого в ней будет b миллилитров воды)
•  Полностью вылить воду из второй колбы
•  Перелить воду из первой колбы во вторую. В этом случае, если во второй колбе достаточно места, чтобы уместить всю текущую воду первой колбы, вода из первой колбы переливается полностью во вторую. Если же во второй колбе места недостаточно, вторая колба заполняется до предела (в ней после этого будет b миллилитров воды), а в первой колбе остается все остальное.

Состоянием колб Вася называет упорядоченную пару (x, y), где x — текущее количество воды в первой колбе, а y— во второй. Вася хочет изучить поставленную самим собой задачу и понять, сколько различных состояний он может получить описанными выше переливаниями.
Входные данные
В единственной строке входного  через пробел записаны два натуральных числа a и b (1 ≤ a, b ≤ 100) — емкости первой и второй колбы соответственно.
Выходные данные
В единственной строке выходного выведите одно число — число различных состояний, которое можно получить описанными в задаче переливаниями воды.
 

Ввод	Вывод
2 5	14

Дана непустая строка s. Нужно найти такое наибольшее число k и строку t, что s совпадает со строкой t, выписанной k раз подряд.
Ограничение времени - 1 секунда.

Входные данные
Дана одна строка длины N, \(0 < N <= 10^6\), состоящая только из маленьких латинских букв.

Выходные данные
Выведите одно число - наибольшее возможное k.
 

 

Примеры

№	Входные данные	Выходные данные
1	aaaaa	5
2	abcabcabc	3
3	abab	2

Недавно Вася решил, что все существующие алгоритмы сортировки слишком сложны, и обязательно должен существовать более простой и эффективный алгоритм.
Для начала Вася решил рассмотреть следующий алгоритм: по данному массиву целых чисел a размером n, он создает пустой массив b, а дальше на каждой из n последующих итераций будет брать k-й элемент массива a (или последний, если такого нет), удалять его из a, а затем записывать в конец b. Таким образом, после n итераций Вася планирует в качестве массива b получить отсортированный по возрастанию массив a.
Однако, протестировав на нескольких примерах, Вася понял, что этот алгоритм работает не всегда. Так, например, если исходный массив a=[1,2,3,4] и k=2, то после 4 итераций массив b вовсе не будет отсортированным:
После первой итерации в b добавляется число 2, а массив a равен [1,3,4];
После второй итерации в конец b добавляется число 3, а массив a равен [1,4];
После третьей итерации в конец b добавляется число 4, а массив a равен [1];
На последней, четвертой итерации, в конец b добавляется число 1, а массив a становится пустым;
Таким образом, итоговый массив b будет выглядеть так: [2,3,4,1]. Нетрудно заметить, что он не является отсортированным по возрастанию. Однако, Вася решил так легко не сдаваться и по данному числу k научиться находить такой массив a, содержащий перестановку последовательности натуральных чисел от 1 до n, который будет сортироваться по возрастанию методом, описанным выше. Помогите ему - по данным числам n и k найдите хотя бы один подходящий массив a.

Формат входных данных
В единственной строке содержится два числа n и k - размер массива и номер элемента, берущегося на каждой итерации, соответственно (1≤k≤n≤1000).

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

Ввод	Вывод
5 1	1 2 3 4 5
5 5	5 4 3 2 1

Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.

Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.

Петя с друзьями при игре просто называют по очереди загаданные ими числа, а потом определяют, кто выиграл, и подсчитывают баллы. Однако при таком формате игры в принципе можно сжульничать, не загадывая число заранее, а, уже зная числа, названные предыдущими игроками, выбрать себе оптимальное "загаданное" число. Этим и пользуется Петя. Он называет число последним и старается выбрать число так, чтобы максимизировать свой выигрыш.

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

Входные данные
В первой строке вводится число n - количество игроков (2 <= n <= 100). Вторая строка содержит n чисел - баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). В третьей строке задано (n-1) число - числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.

Выходные данные
Выведите число, которое следует назвать Пете.

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

Ввод	Вывод
6 0 0 0 0 0 0 2 3 4 5 6	1
6 8 3 12 5 0 9 2 1 3 1 4	2

 

Примеры

№	Входные данные	Выходные данные
1	42 12	6