--->
96 задач
<---
Источники
Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.:
Дано натуральное число k (1 ≤ k ≤ 1018).
Выведите число, которое стоит на k-ом месте в последовательности.
5
1
Функция f с натуральными аргументами и значениями определена так:
Дано одно число n (1 ≤ n ≤ 1018).
Выведите f(n)
10
3
Одной из классических NP-полных задач является так называемая «Задача о рюкзаке». Формулируется она следующим образом. Дано n предметов, каждый из которых характеризуется весом wi и полезностью pi. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна. Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.
Первая строка входного файла содержит натуральные числа n(1 ≤ n ≤ 20) и W(1 ≤ W ≤ 109). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: wi — веса предмета и pi — его полезности (1 ≤ wi, pi ≤ 109).
В первой строке выходного файла выведите количество выбранных предметов и их суммарную полезность. Во второй строке выведите через пробел их номера в возрастающем порядке (предметы нумеруются с единицы в порядке, в котором они перечислены во входном файле). Если искомых наборов несколько, выберите тот, в котором наименьшее число предметов. Если же после этого ответ по-прежнему неоднозначен, выберите тот набор, в котором первый предмет имеет наименьший возможный номер, из всех таких выберите тот, в котором второй предмет имеет наименьший возможный номер, и т. д.
2 10 10 100 9 80
1 100 1
5 100 80 1000 50 550 50 550 50 550 50 550
2 1100 2 3
6 100 80 1000 50 550 50 550 50 550 50 550 100 1100
1 1100 6
Как известно, очередное число Фибоначчи равно сумме предыдущих двух. Первое и второе число Фибоначчи равны единице.
Программист Вася написал вычисление n-ого числа Фибоначчи с помощью рекурсивной функции. А сколько раз запустится эта функция прежде, чем будет получено значение?
Дано одно число n ( 1 ≤ n ≤ 50 )
Выведите одно число — количество запусков функции.
3
3
1
1
2
1
На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.
Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.
Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться.
Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.
Следующие N строк содержат целые положительные числа ci — количество букв соответствующего типа (1 ≤ ci ≤ 109). Таким образом, первое число означает количество букв "a", второе число задаёт количество букв "b" и так далее.
Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек.
3
1
1
1
2
2
3
4
3
В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке "abc"
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. Во всех тестах данной группы ci ≤ 100. Данная подзадача оценивается из 40 баллов.
Подзадача 2. Во всех тестах данной группы ci ≤ 1 000 000. Данная подзадача оценивается из 30 баллов.
Подзадача 3. Во всех тестах данной группы ci ≤ 109. Данная подзадача оценивается из 30 баллов.