Алгоритмы

 

Примеры

№	Входные данные	Выходные данные
1	1
2	5	121
3	562340	3333312222122213312

Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться. 

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

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

Примеры

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

Робот Сильвер едет по шоссе. Вдоль дороги стоят n пунктов оплаты — по одному на каждый километр. На пункте i написана плата cost[i]: столько робот отдаёт, если останавливается у этого пункта. Пункт, мимо которого он проехал не останавливаясь, не оплачивается.
Перед шоссе есть бесплатный въезд, а после — бесплатный съезд. Робот стартует со въезда, едет только вперёд, и от каждой остановки до следующей проезжает 1 или 2 пункта. Доехать ему надо до съезда.
Найдите наименьшую сумму, которую заплатит робот.

Формат входных дынных
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

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

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение T_n.

Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2³¹ - 1.

Выходные данные
Выведите значение T_n.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).

 

Примеры

№	Входные данные	Выходные данные
1	4	4
2	25	1389537

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницу, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
 

Примеры

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

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

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

Примеры

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

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницей, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры

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

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение T_n.

Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2³¹ - 1.

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

Примеры

№	Входные данные	Выходные данные
1	4	4
2	25	1389537

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры

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

Примеры

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

В одной очень влиятельной организации для упрощения контроля въезда автотранспорта сотрудников на территорию решили, что автомобильные номера у всех сотрудников должны иметь одинаковое произведение цифр, равное числу N.
Номера в этой стране могут быть любыми натуральными числами, а жители страны очень любят «маленькие» номера — чем меньше число в номере автомобиля, тем более престижным он считается.
Директор организации хочет, чтобы ни у кого из сотрудников не было более престижного номера, чем у него. Поскольку организация очень влиятельная, директор может получить любой номер по своему желанию.

Входные данные
Программа получает на вход одно натуральное число N, не превосходящее 10¹⁸, — произведение
цифр автомобильных номеров сотрудников очень влиятельной организации.
Обратите внимание, значение N может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

Выходные данные
Выведите одно целое число — минимальное значение номера автомобиля директора очень влиятельной организации.
Если ни одного подходящего номера не существует, программа должна вывести число «−1».

Примеры

№	Входные данные	Выходные данные
1	70	257
2	101	-1

Маленький Миша любит играть счетными палочками. Счетные палочки он берет у своей сестры первоклассницы. Так как он редко возвращает их назад, маме приходится часто покупать новые палочки. Поэтому не все палочки у Миши одинаковые, но все палочки имеют целочисленную длину.
Сегодня Миша строит из палочек следующую фигуру. Он начал из угла комнаты. Мы с вами обозначим, условно, этот угол координатой (0, 0). Дальше Миша выкладывает палочку параллельно одной из двух стен, исходящей из данного угла. Будем считать, что стены ровные и образуют друг с другом в точке (0, 0) угол 90 градусов. При этом, Миша никогда не выкладывает две подряд палочки одновременно параллельно одной и той же стене (другими словами, он всегда чередует направление палочек).
Миша, хоть и маленький и не знает геометрии, но все же всегда радуется, если конец его фигуры находится как можно дальше от стартового угла. Помогите Мише выложить фигуру, которая его обрадует. Любые две палочки, которые выкладывает Миша всегда имеют минимум одну точку касания или пересечения.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит целое число n (1<= n <= 100000) — количество палочек, которые есть у Миши. Вторая строка содержит n целых чисел a1,...,an (1 <= ai <= 10000) - длины Мишиных палочек.

Выходные данные
Выведите одно целое число — квадрат максимального расстояния от угла с координатой (0,0) до конечной точки фигуры, которую построил Миша.
 
 

Примеры

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

Когда  Громозека держит в руках сразу две печеньки с числами, он сразу пробует преобразовать большее число в меньшее. При преобразовании он использует только две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка. Громозека любит, чтобы преобразование происходило как можно быстрее. Помогите Громозеке составить последовательность команд, при которой из большего числа получится меньшее, причем за наименьшее количество команд.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке). A >= B.

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

Примеры

№	Входные данные	Выходные данные
1	21 2	-1 :2 :2 -1 :2

Громозека и Алиса старые друзья. Встречаясь на какой-то планете, они постоянно заходят в кафе. Но Алиса не любит заходить в каждое a-ое кафе, а Громозека в каждое g-ое кафе. Чтобы никого не обидеть, они не заходят в те кафе, в которые не хотят заходить одновременно и Алиса и Громозека. На очередной прогулке у них на пути N кафе. Во сколько кафе они смогут зайти?

Входные данные
Единственная строка содержит три целых числа - a , g , N ( 1 <= a , g , N <= 10⁹ ).

Выходные данные
Выведите единственное число - количество кафе, в которые смогут зайти Громозека и Алиса.
 

Примеры

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

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

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где A_i,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех A_i,j выполнено 1 <= A_i,j <= 10⁵.

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


Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.

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

Входные данные
В первой строке дано натуральное число n (1 <= n <= 7).

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

 

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

Формат входных данных
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи. В следующих N строках записано по два целых числа A_i и B_i (оба числа от 1 до 10⁹) - возможное время приезда i-го друга.

Формат выходных данных
Выведите N пар чисел L_i и R_i - номера дней, в которые приедет и уедет i-й друг соответственно (A_i ≤ L_i ≤ R_i ≤ B_i). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.
 
 

Примеры

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

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

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

Вводится одно число 0 < N < 31.

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

Выведите одно число — количество маршрутов.
 

Примеры

№	Входные данные	Выходные данные
1	4	7

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

Например, схема игры 5-3-2 означает, что в команде пять защитников, три полузащитника и два нападающих. В соответствии с современными представлениями на схему игры накладываются следующие ограничения: должно быть не менее одного и не более пяти защитников, не менее одного и не более пяти полузащитников и не более трех нападающих. Отметим, что нападающих может в команде и не быть совсем. Будем рассматривать только такие схемы.

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

Будем также считать, что игрок в некоторый момент времени находится в линии полузащиты, если он находится на расстоянии не более 20 метров от центральной линии. Соответственно, игрок находится в линии защиты, если он находится не более чем в 40 метрах от «своей» лицевой линии, и в линии нападения, если находится не более чем в 40 метрах от «чужой» лицевой линии.


Например, в ситуации, изображенной на рисунке, в линии защиты находятся четыре игрока, в линии полузащиты — три, в линии нападения — также три.

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

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

Входные данные
Входной файл содержит десять строк, содержащих по два целых числа x_i и y_i каждая, — координаты каждого из игроков команды (0 ≤ x_i ≤ 120, x_i ≠ 40, x_i ≠ 80, 0 ≤ y_i ≤ 80).

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

Примеры

№	Входные данные	Выходные данные
1	97 0 13 18 2 6 119 11 42 21 72 80 75 78 106 45 22 67 28 47	9 2-5-3 3-5-2 3-4-3 4-5-1 4-4-2 4-3-3 5-4-1 5-3-2 5-2-3

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

Входные данные
Вводятся четыре числа, не превосходящие 100, задающие номера конечных остановок. Сначала для первого, потом второго автобуса (см. примеры и рисунок).

Выходные данные
Ваша программа должна выводить одно число – искомое количество остановок.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 6 4 2	2	первый автобус ходит с 3-й остановки по 6-ю и обратно, а второй с 2-й по 4-ю и обратно. Пересесть с одного автобуса на другой можно на 3-й и 4-й остановках. Их две.
2	3 1 5 10	0	автобусы не имеют общих остановок.