Темы --> Информатика --> Язык программирования --> Типы данных
    Символы(9 задач)
    Строки(121 задач)
    Целые числа(112 задач)
    Битовые операции(28 задач)
    Логический тип(3 задач)
    Структуры(18 задач)
    Вещественные числа(33 задач)
    Множества(16 задач)
    Словари(21 задач)
---> 7 задач <---
Источники --> Личные олимпиады --> COCI
    COCI 2016-2017(0 задач)
    COCI 2015-2016(36 задач)
    COCI 2014-2015(0 задач)
Страница: 1 2 >> Отображать по:
#113538
Вечеринка Петара
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Вечеринка Петара ]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
32 megabytes

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.

Петар хочет знать, сколько возможных наборов типов шуток может быть на его вечеринке, если он пригласит людей в соответствии с вышеуказанными правилами.

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .

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

Выведите единственное число - количество возможных наборов типов шуток на вечеринке.

Примеры
Входные данные
4
2 1 3 4
1 2
1 3
3 4
Выходные данные
6
Входные данные
4
3 4 5 6
1 2
1 3
2 4
Выходные данные
3
Входные данные
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
Выходные данные
10
#113540
Игра Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Игра Мирко ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мирко большой любитель шахмат и программирования, но обычные шахматы уже наскучили ему, поэтому он начал экспериментировать и придумал свою игру. Он взял шахматную доску с N рядами и N столбцами и расположил на ней K ладей. Игра Мирко следует таким правилам: 1. У каждой ладьи есть своя сила, заданная натуральным числом. 2. Ладья видит все клетки поля в своем ряду и своем столбце кроме той, на которой стоит сама. 3. Клетка считается атакованной в том случае, если побитовый XOR сил всех ладей, которые видят эту клетку, положителен. Изначально Мирко некоторым образом расположил ладьи на поле, и теперь собирается сделать P перемещений. Каждый раз он будет брать одну ладью и ставить ее на другую клетку поля (при этом ладья не обязательно будет перемещена вдоль ряда или столбца в котором она стоит). После каждого перемещения, определите сколько клеток на поле атакованы.

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

Первая строка содержит 3 целых числа N , K , P ( 1 ≤ N ≤ 1000000000 , 1 ≤ K , P ≤ 10000 ). Каждая из следующих K строк содержит 3 натуральных числа R i , C i , X i ( 1 ≤ R i , C i ≤ N , 1 ≤ X i ≤ 1000000000 ), которые обозначают что на клетке ( R i , C i ) стоит ладья с силой X i . Каждая из следующих P строк содержит 4 натуральных числа R 1 , C 1 , R 2 , C 2 ( 1 ≤ R 1, C 1, R 2, C 2 ≤ N ), которые означают что ладья, стоящая на клетке ( R 1, C 1 ), была передвинута на поле ( R 2, C 2 ). Гарантируется, что в момент перемещения на клетке ( R 1, C 1 ) есть ладья и что ни в какой момент времени на одной клетке нет двух и более ладей.

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

Выведите P строк, где в k -й строке записано единственное число - количество клеток поля, атакованных после первых k перемещений.

Примеры
Входные данные
2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2
Выходные данные
4
0
Входные данные
2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2
Выходные данные
4
2
Входные данные
3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2
Выходные данные
6
7
7
9
#113558
Телефон Марко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Телефон Марко ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Марко обнаружил новую функцию на его телефоне - Т9. На его телефоне имеется стандартная клавиатура на 9 кнопок:

Для того чтобы вводить текст на этой клавиатуре необходимо несколько раз нажимать клавишу с соответствующей буквой. Точнее, если это первая буква на клавише, нужно нажать 1 раз, если вторая буква - 2 раза, и так далее. Например, если мы хотим ввести слово "giht", то необходимо нажать клавиши следующим образом: g-4 i-444 h-44 t-8. Новая возможность, которую открыл Марко, упрощает ввод текста, потому что больше не требуется нажимать по одной клавише несколько раз подряд - достаточно всего одного нажатия. Программа будет пытаться понять, какое слово из словаря вы пытаетесь ввести.

Марко довольно скептически относится к новым технологиями (как минимум к новым для него) и он боится, что ошибки будут довольно часто. Марко наизусть знает весь словарь мобильного телефона. Он состоит из N слов, состоящих из строчных латинских букв, длина каждого слова не превышает 1000000 символов. Марко даст массив нажатий на клавиши S длиной не более 1000, и хочет узнать как много слов из словаря он может получить при такой последовательности нажатий если используется функция Т9.

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

Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 1000 ) - количество слов в словаре. Каждая из следующих N строк содержит одно слово из словаря S i ( 1 ≤ | S i | ≤ 1000000 ). Последняя строка содержит строку S ( 1 ≤ | S | ≤ 1000 ), состоящую из цифр от 2 до 9.

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

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

Примеры
Входные данные
3
tomo
mono
dak
6666
Выходные данные
1
Входные данные
2
ja
la
52
Выходные данные
2
Входные данные
3
dom
fon
tom
366
Выходные данные
2
#113572
Трезвый Доминик
  
Темы: [Строки]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Трезвый Доминик ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Хан не хотел учиться один, поэтому он пригласил своего друга Доминика позаниматься вместе с ним. После того, как они решили рекордное количество задач за вечер, Доминик поехал домой. Внезапно его остановила полиция, подозревая, что он водил в пьяном виде. Чтобы проверить Доминика, полицейские начали задавать ему вопросы.

Полицейский: Давайте начнём с чего-то простого. Какова асимптотика сортировки пузырьком?

Доминик: О, это просто. O ( n 2 ) .

Полицейский: Скажите английский алфавит наоборот.

Доминик: Легко, zyxwvutsrqponmlkjihgfedcba.

Полицейский: Вы просто запомнили это. Представьте, что строчные буквы латинского алфавита записаны по кругу по часовой стрелке. Начинайте с буквы 'a' и называйте все буквы подряд. После каждой сказанной буквы я могу приказать теперь называть в обратном порядке, спросить сколько раз была названа какая-то буква или ничего не делать. Приступайте.

Доминик: Хм... a, b, c...

Возможно, Доминик не настолько трезв, чтобы решить эту задачу. Помогите ему.

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

Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) – количество приказов полицейского. Каждая из последующих Q строк содержит один из приказов в формате "SMJER n" или "UPIT n x". Приказ первого типа обозначает, что после n -й сказанной буквы требуется поменять направление. Приказ второго типа обозначает, что Доминик должен сказать, сколько раз он произнес букву x после n сказанных букв.

Во всех запросах 1 ≤ n ≤ 10 9 , а x – строчные латинские буквы. В запросах n идут в строго возрастающем порядке.

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

Для каждого запроса вида "UPIT n x", выведите ответ на этот запрос, каждый в отдельной строке, в том же порядке, что и в вводе.

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

40 баллов: n ≤ 1000

60 баллов: n ≤ 10 5

100 баллов: n ≤ 10 9

Примечание

В первом примере Доминик говорит a, b, c, d, c, b, a, z, y, x.

Во втором примере Доминик говорит a, z, a, z, y, x, w.

Примеры
Входные данные
5
UPIT 1 b
UPIT 3 b
SMJER 4
UPIT 7 a
UPIT 10 z
Выходные данные
0
1
2
1
Входные данные
5
SMJER 1
SMJER 2
SMJER 3
UPIT 5 a
UPIT 7 w
Выходные данные
2
1
Входные данные
4
UPIT 100 a
UPIT 200 c
UPIT 300 a
UPIT 400 b
Выходные данные
4
8
12
16
#113573
Миссия джедая Ивана
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Миссия джедая Ивана ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Юный джедай Иван был заброшен на Звезду Смерти с заданием уничтожить её. Для того, чтобы уничтожить Звезду Смерти, ему требуется массив неотрицательных целых чисел a i длины N . К сожалению, у Ивана нет этого массива, но есть секретный документ с требованиями к этому массиву, который ему передал его старый друг Дарт Вейдер.

В этом документе содержится квадратная матрица m размера N , где элемент в i -й строке в j -м столбце равен побитовому "И" чисел a i и a j . Для повышения безопасности главная диагональ матрицы была уничтожена и вместо чисел на ней были записаны нули. Помогите Ивану восстановить массив a и выполнить свою миссию.

Гарантируется, что решение всегда существует. Если решений несколько, выведите любое.

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

В первой строке содержится число N ( 1 ≤ N ≤ 1000 ) – размер матрицы. Каждая из последующих N строк содержит по N целых чисел m ij ( 0 ≤ m ij ≤ 9 ) – элементы матрицы.

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

В единственной строке выведите N целых неотрицательных чисел, не превышающих 100 – требуемый массив a .

Примечание

40 баллов — (1 ≤ N ≤ 5) .

100 баллов — (1 ≤ N ≤ 1 000) .

Примеры
Входные данные
3
0 1 1
1 0 1
1 1 0
Выходные данные
1 1 1
Входные данные
5
0 0 1 1 1
0 0 2 0 2
1 2 0 1 3
1 0 1 0 1
1 2 3 1 0
Выходные данные
1 2 3 1 3
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест