Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Гномы и сокровища#82069

В подземелье живут гномы. У них есть древняя традиция деления золота:

Когда гном получает N монет:
1. Если N = 0, гном грустит и ничего не делает
2. Если N = 1, гном оставляет монету себе и кричит "МОЁ!"
3. Если N > 1:
- Гном берёт себе 1 монету и кричит "МОЁ!"
- Остальные (N-1) монет делит пополам
- Левую половину (N-1)/2 отдаёт левому ученику-гному
- Правую половину (N-1) - (N-1)/2 отдаёт правому ученику-гному
- Каждый ученик делает то же самое по традиции

Подсчитайте, сколько раз прозвучит крик "МОЁ!" при делении N монет.

Формат входных данных
Одно число N (0 ≤ N ≤ 10^9) - начальное количество монет.

Формат выходных данных
Одно число - сколько раз прозвучит "МОЁ!"

Рекурсия

✓ 1✗ 3—Войти и решать

Рекурсивное закрашивание (2024-2025, 11)#80755

Разбирая старые задачи олимпиады, Петя наткнулся на алгоритм рекурсивного закрашивания растрового изображения. У Пети есть черно-белое (bitmap) изображение размером 13 на 13 пикселей. На изображении присутствует замкнутый контур, как приведено на рисунке. Пиксели внутри контура пронумерованы.

Традиционно для компьютерной графики, система координат имеет начало в верхнем левому углу, ось X направлена слева направо, а ось Y – сверху вниз.
Алгоритм рекурсивного закрашивания заключается в рекурсивном вызове процедуры «Закрасить», которой передаются два параметра – координаты X и Y пикселя.
Процедура Закрасить(X, Y), может быть описана следующим образом:
1. Если цвет пикселя с координатами (X, Y) белый, то:

a. Изменить цвет пикселя с этими координатами на черный;
b. Вызвать процедуру Закрасить(X+1, Y);
c. Вызвать процедуру Закрасить(X, Y+1);
d. Вызвать процедуру Закрасить(X-1, Y);
e. Вызвать процедуру Закрасить(X, Y-1);

2.Иначе завершить процедуру.
Известно, что последний закрашенный пиксель, перед завершением процедуры, имел номер 29. Сколько существует пикселей внутри контура, в которых можно исходно вызвать процедуру «Закрасить» так, чтобы получить такой результат?

В ответе укажите целое число.

Рекурсия

—Войти и решать

Определение символа в позиции - 6#65090

Строка формируется из заглавных английских букв следующим образом

Начинаем с "A".
Каждый следующий шаг: к предыдущей строке приписываем новую строку, в которой каждый символ предыдущей строки сдвинут вправо на 2 по алфавиту (A→C, B→D, ..., Y→A, Z→B).

Вот первые четыре шага:

Шаг 1: A
Шаг 2: AС
Шаг 3: AССE
Шаг 4: ACCECEGG

Какой символ стоит на 50-й позиции после 7-го шага?

Первый символ слева стоит на позиции 1.

Рекурсия

—Войти и решать

Определение символа в позиции - 5#64819

Строка формируется из заглавных английских букв следующим образом

Начинаем с "A".
Каждый следующий шаг: к предыдущей строке приписываем новую строку, в которой каждый символ предыдущей строки сдвинут вправо на 1 по алфавиту (A→B, B→C и т. д. Z→A).

Вот первые четыре шага:

Шаг 1: A
Шаг 2: AB
Шаг 3: ABBC
Шаг 4: ABBCBCCD

Какой символ стоит на 100-й позиции после 8-го шага?

Первый символ слева стоит на позиции 1.

Рекурсия

—Войти и решать

Определение символа в позиции - 4#64818

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из одной единицы. Каждая из последующих строк создается следующим действием: берется предыдущая строка и после каждой ее цифры вставляется цифра на единицу большая и затем еще раз исходная цифра. Вот первые 3 строки, созданные по этому правилу:
(1) 1
(2) 121
(3) 121232121
(4) 121232121232343232121232121
Какая цифра будет стоять в позиции 1094 в строке (9)?

Первая цифра слева стоит на позиции 1

Рекурсия

—Войти и решать

Определение символа в позиции - 3#64817

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из четырех единиц. Каждая из последующих строк создается следующим действием: берется предыдущая строка и перед каждой ее цифрой вставляется цифра на единицу большая. Вот первые 3 строки, созданные по этому правилу:
(1) 1111
(2) 21212121
(3) 3221322132213221
Какая цифра будет стоять в позиции 479 в строке (9)?

Первая цифра слева стоит на позиции 1

Рекурсия

—Войти и решать

Определение символа в позиции - 2#64816

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из четырех единиц. Каждая из последующих строк создается следующим действием: берется предыдущая строка и после каждой ее цифры вставляется цифра на единицу большая. Вот первые 3 строки, созданные по этому правилу:
(1) 1111
(2) 12121212
(3) 1223122312231223
Какая цифра будет стоять в позиции 479 в строке (9)?

Первая цифра слева стоит на позиции 1

Рекурсия

—Войти и решать

Определение символа в позиции#64815

Строки, состоящие из последовательностей цифр, формируются следующим образом. Первая строка состоит из четырех единиц. Каждая из последующих строк создается следующим действием: берется предыдущая строка и после каждой ее цифры вставляется цифра на единицу большая. Вот первые 3 строки, созданные по этому правилу:
(1) 1111
(2) 12121212
(3) 1223122312231223
Какая цифра будет стоять в позиции 100 в строке (9)?

Первая цифра слева стоит на позиции 1

Рекурсия

—Войти и решать

Умножение многочленов#55172

Ввести в символьной форме два многочлена от x с целыми коэффициентами и вывести их произведение в порядке убывания степеней - также в символьной форме.

Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 10⁴.

Входные данные
В двух строках находятся многочлены.

Выходные данные
В единственной строке выводится многочлен.

Рекурсия

✓ 1✗ 2—Войти и решать

Дерево игры#55129

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.

Входные данные
Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое N - число узлов в дереве игры. Следующая N - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла. 2 <= N <= 1000.

Выходные данные
Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.

Рекурсия

✓ 1✗ 0—Войти и решать

Быстрое возведение в степень#53684

Напишите функцию быстрого возведения в степень. Количество действий должно быть пропорционально двоичному логарифму n.

Входные данные
Вводится 2 числа - a (вещественное) и n (целое неотрицательное).

Выходные данные
Необходимо вывести значение aⁿ.

Задачи на процедуры и функции Рекурсия

✓ 2✗ 0—Войти и решать

Степень для отрицательного показателя#53643

Напишите рекурсивную функцию, возводящую число a в степень n. Гарантируется, что все числа "помещаются" в стандартные вещественные (a и ответ) и целые (n) типы.

Входные данные
Вводится 2 числа - a и n (число n может быть отрицательным).

Выходные данные
Необходимо вывести значение aⁿ

Быстрое возведение в степень Остатки Рекурсия

✓ 1✗ 0—Войти и решать

Интересные разбиения#50575

Недавно на кружке по математике Миша узнал про разбиения на слагаемые. Разбиением числа \(n\) на слагаемые называется представление его в виде суммы неубывающего набора натуральных чисел. Например, \(9=1+2+2+4\) является разбиением числа 9 на слагаемые.

Миша называет разбиение интересным, если никакие два слагаемых в наборе не равны и не отличаются ровно на 1. Так, например, разбиение, приведенное выше не является интересным, а разбиение \(9=1+3+5\) — является.

Помогите Мише вывести все интересные разбиения числа \(n\) на слагаемые.

Формат входных данных
На ввод подается одно целое число \(n\) (\(1 \le n \le 80\)).

Формат выходных данных
Выведите все интересные разбиения числа \(n\) на слагаемые. Разбиения можно выводить в любом порядке. Соблюдайте формат из примера.

Рекурсия

✓ 7✗ 2—Войти и решать

XOR и сумма#38518

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

Битовые операции Динамическое программирование Рекурсия

✓ 1✗ 1—Войти и решать

Перебор строк №1#37810

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все слова, состоящие из n букв, которые можно построить из букв этого алфавита.

Рекурсивный перебор Рекурсия

✓ 1✗ 3—Войти и решать

Полные квадраты#33145

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0+ 1, 0+ 1+ 3, 0+ 1+ 3+ 5,

. . . , 0 + 1 + 3 + . . . + (2n − 1), . . ., составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, . . . , n², . . ..

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, . . . ,k+ 1+ 3+. . .+ (2n−1), . . .. В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности,

либо выясняет, что в ней вообще не встречается полных квадратов.

Формат входных данных

В единственной строке содержится целое число k — начальное число в последовательности

(−10¹² <= k <= 10¹²).

Обратите внимание, что для считывания и хранения такого большого числа необходимо использовать 64-битный тип данных.

Формат выходных данных

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной

последовательности. Если в последовательности не встречается квадратов целых чисел, выведите

«none».

Ввод	Вывод
0	0
-5	2
2	none

Разбор случаев Рекурсия Целые числа

✓ 0✗ 1—Войти и решать

Circular Barn#29547

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.

ФД хочет разместить ровно ri коров в комнате i (1≤r_i≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.

ФОРМАТ ВВОДА:

Первая строка ввода содержит n и k. Последующие n строк содержат r₁…r_n.

ФОРМАТ ВВОДА:

Выведите минимальное суммарное расстояние пройденное коровами.

Ввод	Вывод
6 2 2 5 4 2 6 2	14

ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.

Динамическое программирование Динамическое программирование: два параметра Задача на реализацию Рекурсия

✓ 1✗ 1—Войти и решать