Страница: 1 2 >> Отображать по:
#3585
Народный IPO
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Компания «Рога и копыта» решила провести народный IPO (первоначальное публичное предложение акций компании на продажу широкому кругу лиц). Как обычно у Остапа Бендера не обошлось без аферы.

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

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

Тем не менее, изменяя порядок удовлетворения заявок покупателей можно влиять на количество вырученных денег. Помогите Остапу Бендеру наиболее выгодно продать «Рога и копыта». Акций у компании так много, что Остап может продать любой процент акций, в том числе дробный.

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

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

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

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

Примечание

В первом тесте выгоднее сначала удовлетворить заявку второго человека, в результате чего будет продано 25% акций компании. Первому человеку будет продано 25% от оставшейся части (т.е. 18,75% от общего числа акций). Суммарная выручка в таком случае составит 25 × 10 + 18, 75 × 5 = 343, 75 рублей.

Примеры
Входные данные
2
25 5
25 10
Выходные данные
2 1
Входные данные
3
10 30
20 15
30 10
Выходные данные
1 2 3
#3587
Сдвиг
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Вася придумали систему шифровки для обмена записками. Суть ее заключается в следующем. Дана исходная строка 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
#3588
Башня
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя в очередной купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из 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
#3589
Фибоначчиева система счисления
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: 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
#3590
Палиндромика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Игра «Палиндромика» набирает все большую популярность в казино Рулеттенбурга. Правила «Палиндромики» довольно просты: в начале игры на листок записывается строка и игроки поочередно стирают первый или последний символ. Побеждает игрок, перед ходом которого строка представляет собой палиндром. Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево.

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

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

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

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

Выведите номер игрока, который победит в игре (число 1 или 2) при оптимальной игре каждого из игроков.

Примеры
Входные данные
3
uho
Выходные данные
1
Входные данные
6
ababab
Выходные данные
2
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест