Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 952 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 185 186 187 188 189 190 191 >> Отображать по:
#113664
Форум. Вывести дерево
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано количество сообщений на некотором форуме (\(N\) натуральное, не более \(1000\)).

Также таблица, в которой указано какие сообщения на каком уровне находятся.

В первой колонке таблицы написаны номера сообщений (натуральные числа, не превосходят \(10^6\)).

Во второй колонке напротив номера сообщения стоит либо 0, если сообщение является корнем (началом) некоторой темы, либо номер того сообщения, ответом на которое является текущее.

Пример. Следующие исходные данные: 

4
1 0 
2 0
3 1
4 3
соответствуют такой структуре форума:

Гарантируется что данные во втором столбце корректны (то есть в качестве «родительского» может быть указано только существующее сообщение, а также что структура не имеет циклов и что от любого сообщения есть путь к «корню» форума).

Вывести структуру форума в виде дерева. На одной строке выведите номер одного сообщения, с отступами нужной величины. Отступы заполнить символами ‘*’ (звездочка). Сообщения каждого следующего уровня должны иметь отступ слева на две звездочки больше, чем сообщения предыдущего, при этом сообщения внутри ветки должны располагаться по возрастанию номеров.

Например, для теста 

3

1 0

2 0

3 1

Ответ будет

1

**3

2

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

Сначала вводится натуральное число \(N\) (не превышает \(1000\)) – общее количество сообщений на форуме.

Затем вводится \(N\) строк таблицы, по \(2\) числа на строке – номер текущего сообщения и номер того сообщения, ответом на которое является текущее (или \(0\)).

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

Выведите структуру форума в описанном формате.

Примеры
Входные данные
2
1 0
7 1
Выходные данные
1
**7
Входные данные
3
1 0
4 1
9 1
Выходные данные
1
**4
**9
#113806
Пароли
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Недавно произошла утечка информации из мега-популярной социальной сети. Среди конфиденциальной информации, попавшей в сеть, оказались и пароли всех пользователей.

Михаил, школьник, увлекающийся компьютерной безопасностью, нашёл произошедший инцидент очень интересным. Экспериментируя с социальной сетью, он нашёл ещё одну брешь в её системе безопасности! Войти в аккаунт можно, если ввести строку, содержащую настоящий пароль от аккаунта как подстроку. Например, если пользователь, чей пароль « abc » введёт « abc », « abcd » или « imaabcnema », у него успешно получиться авторизоваться в системе, но у него не получится если он введёт « axbc ».

Миша хочет узнать, сколько существует упорядоченных пар пользователей таких, что если первый пользователь введёт пароль, то он сможет войти в аккаунт второго пользователя.

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

В первой строчке вводится одно целое число N — число пользователей ( 1 ≤ N ≤ 20 000 ). В следующих N строках вводятся пароли пользователей, по одному в строке. Пароль содержит от 1 до 10 маленьких букв латинского алфавита.

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

Выведите единственное число — количество пар, которое интересует Мишу.

Система оценки

Решение, правильно работающее при 1 ≤ N ≤ 2 000 , будет оцениваться в 40 баллов.

Примечание

Во втором примере первый пользователь может войти в аккаунт второго и третьего пользователя, а второй пользователь — в аккаунт первого и третьего пользователя.

Примеры
Входные данные
3
aaa
aa
abb
Выходные данные
1
Входные данные
3
x
x
xy
Выходные данные
4
Входные данные
5
mir
mirta
ta
ir
t
Выходные данные
6
#113811
ЗигЗаг
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Зиг и Заг играют в игру. Зиг говорит букву, а Заг — слово. Но слово не простое, а такое, что начинается с буквы Зига. Но и это не всё. Слово это должно быть в специальном списке слов, а из всех таких должно оно быть произнесено наименьшее число раз. А из всех слов из списка, начинающихся с буквы Зига, которые были произнесены минимальное число раз Заг должен взять лексикографический минимальное. Загу сложно. Помогите Загу.

Вам дан список S из k разрешённых слов. Так же вам даны буквы Зига за первые n ходов. На каждую из этих ходов найдите слово, которое Заг должен сказать.

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

В первой строке ввода содержится 2 числа k и n ( 1 ≤ k ≤ 10 5 , 1 ≤ n ≤ 10 5 ) — число слов в списке и число ходов.

В следующих k строках даны различные слова из списка, по одному в строке. Каждое из слов имеет длину не более 21 символа.

В следующих n строках даны буквы Зига, по одной в строке. Буквы даны в том порядке, в котором Зиг своими ходами их называет.

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

Выведите n строк, в i -й — то слово, которое Заг должен ответить на ход Зига. Гарантируется, что Заг всегда может сделать ход.

Система оценки

Решения, работающие при n ≤ 500 и k ≤ 500 будут оцениваться в 60 балов.

Примеры
Входные данные
4 5
zagreb
split
zadar
sisak
z
s
s
z
z
Выходные данные
zadar
sisak
split
zagreb
zadar
Входные данные
5 3
london
rim
pariz
moskva
sarajevo
p
r
p
Выходные данные
pariz
rim
pariz
Входные данные
1 3
zagreb
z
z
z
Выходные данные
zagreb
zagreb
zagreb
#113931
Сделай треугольник!
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

У Маши есть три палочки длиной \(a\), \(b\) и \(c\) сантиметров. За одну минуту Маша может увеличить длину любой из палочек на один сантиметр. Ломать палочки не разрешается.

За какое минимальное время Маша сможет собрать треугольник положительной площади, сторонами которого будут палочки, если концы палочек должны быть вершинами треугольника?

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

В единственной строке даны три целых числа \(a\), \(b\) и \(c\) (\(1 \leq a, b, c \leq 100\)) — длины палочек, которые есть у Маши.

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

Выведите одно целое число — минимальное количество минут, за которое Маша сможет сделать треугольник положительной площади из своих палочек.

Примечание

В первом примере Маша может сделать треугольник из палочек, не меняя длины ни одной из палочек.

Во втором примере Маша не может построить треугольник положительной площади из палочек, которые у нее есть, но может удлинить палочку длиной \(2\) сантиметра на один сантиметр за одну минуту, после чего построить треугольник из палочек со сторонами \(3\), \(3\) и \(5\) сантиметров.

В третьем примере Маша может за \(33\) минуты удлинить одну из палочек длиной \(10\) сантиметров на \(33\) сантиметра, а затем за \(48\) минут удлинить другую палочку длиной \(10\) сантиметров на \(48\) сантиметров. Таким образом, Маша может собрать треугольник со сторонами \(43\), \(58\) и \(100\) сантиметров за \(81\) минуту. Можно показать, что Маша не сможет получить треугольник за меньшее время.

Примеры
Входные данные
3 4 5
Выходные данные
0
Входные данные
2 5 3
Выходные данные
1
Входные данные
100 10 10
Выходные данные
81
#113938
Уравнения математической магии
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько существует неотрицательных решений данного уравнения. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

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

Вам предстоит решить задачу для нескольких возможных значений параметра \(a\). В первой строке находится целое число \(t\) (\(1 \le t \le 1000\)) — количество этих значений.

В последующих \(t\) строках находятся значения параметра \(a\), каждое значение — целое число от \(0\) до \(2^{30} - 1\) включительно.

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

Для каждого значения параметра \(a\) выведите строке одно целое число — количество неотрицательных решений уравнения с данным значением параметра. Ответы выводите в том же порядке, в каком параметры следуют во входных данных.

Можно доказать, что количество решений всегда конечно.

Примечание

Определим операцию побитового исключительного ИЛИ (XOR).

Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\).

Пусть \(r = x \oplus y\) — результат операции XOR над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:

\(\) r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. \(\)

Для первого значения параметра только \(x = 0\) является решением уравнения.

Для второго значения параметра решениями уравнения являются \(x = 0\) и \(x = 2\).

Примеры
Входные данные
3
0
2
1073741823
Выходные данные
1
2
1073741824
Страница: << 185 186 187 188 189 190 191 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест