Темы
Информатика(2656 задач)
--->
228 задач
<---
Город будущего застроен небоскребами, для передвижения между которыми и парковки транспорта многие тройки небоскребов соединены треугольной подушкой из однополярных магнитов. Каждая подушка соединяет ровно 3 небоскреба и вид сверху на нее представляет собой треугольник, с вершинами в небоскребах. Это позволяет беспрепятственно передвигаться между соответствующими небоскребами. Подушки можно делать на разных уровнях, поэтому один небоскреб может быть соединен различными подушками с парами других, причем два небоскреба могут соединять несколько подушек (как с разными третьими небоскребами, так и с одинаковым). Например, возможны две подушки на разных уровнях между небоскребами 1, 2 и 3, и, кроме того, магнитная подушка между 1, 2, 5.
Система магнитных подушек организована так, что с их помощью можно добираться от одного небоскреба, до любого другого в этом городе (с одной подушки на другую можно перемещаться внутри небоскреба), но поддержание каждой из них требует больших затрат энергии.
Требуется написать программу, которая определит, какие из магнитных подушек нельзя удалять из подушечной системы города, так как удаление даже только этой подушки может привести к тому, что найдутся небоскребы из которых теперь нельзя добраться до некоторых других небоскребов, и жителям станет очень грустно.
В первой строке входного файла находятся числа N и M — количество небоскребов в городе и количество работающих магнитных подушек соответственно (3 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). В каждой из следующих M строк через пробел записаны три числа — номера небоскребов, соединенных подушкой. Небоскребы пронумерованы от 1 до N. Гарантируется, что имеющиеся воздушные подушки позволяют перемещаться от одного небоскреба до любого другого.
Выведите в выходной файл сначала количество тех магнитных подушек, отключение которых невозможно без нарушения сообщения в городе, а потом их номера. Нумерация должна соответствовать тому порядку, в котором подушки перечислены во входном файле. Нумерация начинается с единицы.
3 1 1 2 3
1 1
3 2 1 2 3 3 2 1
0
5 4 1 2 3 2 4 3 1 2 4 3 5 1
1 4
Петя и Вася придумали систему шифровки для обмена записками. Суть ее заключается в следующем. Дана исходная строка S. S' — циклический сдвиг строки влево (первый символ становится последним, а остальные перемещаются на одну позицию влево), S" — циклический сдвиг строки S' и т.д. Петя с Васей выписывают на листок бесконечную последовательность символов SS'S"S"'.... Если им необходимо зашифровать символ C, то они ищут какое-либо вхождение этого символа в выписанную последовательность и записывают его порядковый номер k. Нумерацию символов они ведут с единицы.
Злоумышленник Коля перехватил сообщение и выкрал исходную строку S. Однако он не может определить, какой символ стоит в последовательности SS'S"S"'... на k-ом месте. Помогите злоумышленнику Коле узнать, какой символ соответствует числу k.
Первая строка входного файла содержит строку, состоящую только из строчных латинских букв. Длина строки L не превышает 200 символов. Вторая строка входного файла содержит единственное целое число k (1 ≤ k ≤ L2).
Единственная строка выходного файла должна содержать символ, который окажется на k-ом месте сформированной строки.
abcd 5
b
abcd 16
c
Петя в очередной купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.
Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.
Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.
Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.
В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 1000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 103).
На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.
Гарантируется, что в оптимальном разбиении неприступность крепости не превосходит 2 × 109.
1 1 1
1 1
2 1 1 1000
2 1 2
8 3 1 2 3 4 1 6 7 8
2 2 6
Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: f0 = f1 = 1, fk = fk - 1 + fk - 2, где k > 1.
Фибоначчиева система счисления (ФСС) — это позиционная система счисления с алфавитом, состоящим из двух цифр: 0 и 1, а ее базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … (f0 = 1 в базис не включается). В фибоначчиевой системе, как и во всех позиционных системах счисления, «вес» каждого разряда определяется соответствующим элементом базиса этой системы. Так, 10011fib = 1 × 8 + 0 × 5 + 0 × 3 + 1 × 2 + 1 × 1 = 11. Если не наложить дополнительных ограничений, то представление чисел в такой системе счисления оказывается неоднозначным.
Например, 1110 = 1111fib = 10011fib = 10100fib
Однако, нетрудно доказать, что существует единственное представление данного числа в фибоначчиевой системе счисления, которое не содержит двух единиц подряд. Такое представление называется каноническим. Требуется написать программу, которая для натурального числа N будет выводить его каноническое представление в ФСС.
Во входном файле записано единственное число N (1 ≤ N ≤ 2· 109).
Единственная строка выходного файла должна содержать искомое представление.
5
1000
11
10100
Игра «Палиндромика» набирает все большую популярность в казино Рулеттенбурга. Правила «Палиндромики» довольно просты: в начале игры на листок записывается строка и игроки поочередно стирают первый или последний символ. Побеждает игрок, перед ходом которого строка представляет собой палиндром. Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево.
Алексей Иванович — азартный игрок, однако вместо участия в игре предпочитает делать ставки. Ему удалось узнать, какая строка будет предложена для игры. Алексею Ивановичу предсказать исход игры при оптимальных действиях обоих игроков не под силу. За помощью он обратился к вам.
В единственной строке входного файла содержится строка, предложенная игрокам. Строка состоит из маленьких латинских букв. Длина строки не превышает 250 символов.
Выведите номер игрока, который победит в игре (число 1 или 2) при оптимальной игре каждого из игроков.
3 uho
1
6 ababab
2