---> 96 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 13 14 15 16 17 18 19 >> Отображать по:

Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.:

0 → 01 → 0112 → 01121220 →  ...
Составить алгоритм, который по введенному k определяет, какое число стоит на k-ом месте в последовательности.

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

Дано натуральное число k (1 ≤ k ≤ 1018).

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

Выведите число, которое стоит на k-ом месте в последовательности.

Примеры тестов

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

#111599
  
Темы: [Рекурсия]

Функция f с натуральными аргументами и значениями определена так:

  • f(0) = 0
  • f(1) = 1
  • f(2n) = f(n)
  • f(2n + 1) = f(n) + f(n + 1)
Составить программу вычисления f(n) по заданному n.

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

Дано одно число n (1 ≤ n ≤ 1018).

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

Выведите f(n)

Примеры тестов

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

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Одной из классических 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 
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, очередное число Фибоначчи равно сумме предыдущих двух. Первое и второе число Фибоначчи равны единице.

Программист Вася написал вычисление n-ого числа Фибоначчи с помощью рекурсивной функции. А сколько раз запустится эта функция прежде, чем будет получено значение?

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

Дано одно число n ( 1 ≤ n ≤ 50 )

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

Выведите одно число — количество запусков функции.

Примеры
Входные данные
3
Выходные данные
3
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.

Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 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 баллов.


Страница: << 13 14 15 16 17 18 19 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест