В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.
Выполняется один или несколько шагов по удалению чисел в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.
Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса.
Например, пусть n = 13, k = 2.
На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.
Таким образом, число 13 будет удалено на третьем шаге.
Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.
Формат входных данных
Первая строка входных данных содержит целое число n.
Вторая строка входных данных содержит целое число k.
Формат выходных данных
Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.
Ограничения
3 ≤ n ≤ 1018
2 ≤ k ≤ 100, k < n
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Группа юных археологов работает на раскопках здания древней библиотеки. Летом они обнаружили остатки старой книги и, изучив их, сделали следующие выводы.
Книга содержит несколько страниц, каждая страница содержит либо текст, либо иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма номеров страниц с текстом равна s.
К сожалению, ни общее количество страниц в книге, ни количество иллюстраций установить не удалось. Тем не менее, юных археологов заинтересовал вопрос, какое минимальное количество иллюстраций могло быть в книге.
Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание (буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая иллюстрацию):
И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;
И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;
И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.
Минимальное количество иллюстраций равно 3.
Требуется написать программу, которая по заданным целым числам k и s определяет минимальное количество иллюстраций, которое могло быть в книге.
Формат входных данных
Первая строка входных данных содержит целое число k.
Вторая строка входных данных содержит целое число s.
Формат выходных данных
Требуется вывести одно целое число — минимальное количество иллюстраций в книге.
Ограничения
0 ≤ k ≤ 109
k + 1 ≤ s ≤ 1012
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
В лаборатории теоретической пиротехники изучают новые технологии организации фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят операцию возведения корневого дерева в степень.
Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина является родителем. При этом от любой вершины можно добраться до корня, последовательно переходя от вершины к ее родителю. Вершина, которая не является родителем никакой другой вершины, называется листом. Если вершина x является родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что вершина и ее родитель соединены ребром.
На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин 2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.
Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.
Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T1 — само дерево T. Для m > 1 рассмотрим дерево Tm − 1. Выполним следующую операцию: для каждого листа x дерева Tm − 1 создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом Tm.
На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.
Рис. 2. Пример возведения дерева в степени 1, 2 и 3.
Путем в дереве называется последовательность вершин, в которой две соседние вершины соединены ребром. Все вершины в пути должны быть различны.
Для того, чтобы оценить красоту фейерверка, необходимо определить, какое максимальное количество вершин может содержать путь в дереве, которым представляется фейерверк. На рис. 3 приведен путь в дереве T2, содержащий максимальное количество вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.
Рис. 3. Путь в дереве T2, содержащий максимальное количество вершин.
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.
Формат входных данных
Первая строка входных данных содержит два натуральных числа n и m — количество вершин в базовом дереве фейерверка T и его мощность.
Вторая строка описывает дерево T и содержит (n − 1) целых чисел: p2, p3, ..., pn — номера родителей вершин 2, 3, ..., n, соответственно.
Формат выходных данных
Требуется вывести одно целое число — красоту фейерверка, представляемого деревом Tm.
Ограничения
3 ≤ n ≤ 200000, 1 ≤ m ≤ 200000
1 ≤ pi ≤ i − 1
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
В научной лаборатории разрабатывается новая архитектура суперкомпьютера, позволяющая эффективно обрабатывать большие объемы данных.
Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k – 1. Отрезком [L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R, включительно.
Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является корректным, если его длина (R − L + 1) равна 2i для некоторого i, а число L делится на 2i. Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6] и [7, 7].
Ключевой операцией в новой архитектуре является операция STORE, которая за одно действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного отрезка.
Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые c1 ячеек памяти необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее, последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.
Ученым надо выяснить, какое минимальное количество операций STORE необходимо выполнить, чтобы проинициализировать память требуемым образом.
Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для инициализации памяти достаточно трех операций STORE:
STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],
Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не является корректным отрезком памяти.
Требуется написать программу, которая по заданному содержимому памяти определяет минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.
Формат входных данных
Первая строка входных данных содержит три целых числа: k, n и m.
Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci и vi.
Формат выходных данных
Требуется вывести одно целое число – минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.
Ограничения
0 ≤ k ≤ 30, 1 ≤ n ≤ 105, 1 ≤ m ≤ 109
1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
