--->
58 задач
<---
Источники
Входные данные
Дано число A, длина числа не превышает 250 знаков.
Выходные данные
Выведите такое наибольшее целое число X, что X2≤A.
Примеры
Входные данные
8
Выходные данные
2
#207
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется подсчитать количество последовательностей длины \(N\), состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.
Входные данные
На вход программы поступает целое число \(N\) (\(1\le N\le100\)).
Выходные данные
Выведите количество искомых последовательностей.
Примеры
Входные данные
1
Выходные данные
2
#420
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.
Напомним, что двоичным деревом называется набор вершин, организованных в виде дерева. Каждая вершина имеет не более двух детей, один из которых называется левым, а другой – правым. Как левый, так и правый ребенок, а также оба могут отсутствовать.
Если вершина Y – ребенок вершины X, то говорят, что вершина X является родителем вершины Y. У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.
Соединим каждую вершину, кроме корня, с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.
Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:
- если вершина красная, то ее родитель – черный;
- количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.
Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.
 |
Если считать закрашенные вершины черными, а незакрашенные – красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) – нет. Для дерева на рисунке (б) нарушается первое свойство – у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство – на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 – две.
Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.
Входные данные
В первой строке вводится число n – количество вершин в дереве ( 1
n1000).
Пусть вершины дерева пронумерованы числами от 1 до n. Следующие n строк содержат по два числа – для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор вводимых чисел действительно задает двоичное дерево.
Выходные данные
Выведите одно число – количество способов раскрасить вершины заданного двоичного дерева в красный и черный цвета так, чтобы оно стало красно-черным деревом.
 |
Примеры
Входные данные
6 6 0 1 5 0 0 0 0 3 4 0 0
Выходные данные
3
Входные данные
4 2 0 3 0 4 0 0 0
Выходные данные
0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Для натуральных чисел \(a\) и \(n\) вычислить \(a^n\).
Входные данные
В первой строке находятся разделённые пробелом \(a\) и \(n\). 1 <= \(a\) <= 9, 1 <= \(n\) <= 7000.
Выходные данные
Выводится одно число - результат без стоящих впереди нулей, стоящих впереди и позади пробелов.
Примеры
Входные данные
1 1
Выходные данные
1
Входные данные
1 6789
Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Даны два целых неотрицательных числа: \(M\) и \(N\). Найти их сумму.
Входные данные
В первой строке содержится \(M\), во второй - \(N\). 0 <= \(M\), \(N\) < 1030 000.
Выходные данные
В первой строке вывести сумму без пробелов и ведущих нулей.
Примеры
Входные данные
2 3
Выходные данные
5
Входные данные
6 7
Выходные данные
13
Выбрано
:
|