Темы --> Информатика --> Язык программирования --> Типы данных
    Символы(9 задач)
    Строки(121 задач)
    Целые числа(112 задач)
    Битовые операции(28 задач)
    Логический тип(3 задач)
    Структуры(18 задач)
    Вещественные числа(33 задач)
    Множества(16 задач)
    Словари(21 задач)
---> 356 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 66 67 68 69 70 71 72 >> Отображать по:
#113663
Форум. Количество сообщений в самой длинной ветке
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

Найти количество сообщений в самой длинной ветке форума.

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

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

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

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

Выведите одно число – количество сообщений в самой длинной ветке форума.

Примеры
Входные данные
1
1 0
Выходные данные
1
Входные данные
2
1 0
7 1
Выходные данные
2
#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
#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
Страница: << 66 67 68 69 70 71 72 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест