Темы --> Информатика --> Язык программирования --> Типы данных
    Символы(9 задач)
    Строки(121 задач)
    Целые числа(112 задач)
    Битовые операции(28 задач)
    Логический тип(3 задач)
    Структуры(18 задач)
    Вещественные числа(33 задач)
    Множества(16 задач)
    Словари(21 задач)
---> 51 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
#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
#113578
Перо и страстная любовь
  
Темы: [Строки]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Перо и страстная любовь ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Мультиграмма – это слово, которое состоит из конкатенации двух и более анаграмм. Первая из этих анаграмм называется корнем мультиграммы. Например, слово bbabab – мультиграмма с корнем bba, потому что она состоит из анаграмм bba и bab.

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

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

Единственная строка содержит слово, состоящее не более, чем из 10 5 строчных букв латинского алфавита.

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

Если данное слово – мультиграмма, выведите кратчайший из её корней. Иначе выведите -1.

Примечание

Решения, работающие когда длина строки не превосходит 500, будут оцениваться в 20 баллов.

Решения, работающие когда длина строки не превосходит 5000, будут оцениваться в 40 баллов.

Примеры
Входные данные
aaaa
Выходные данные
a
Входные данные
ab
Выходные данные
-1
Входные данные
bbabab
Выходные данные
bba
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест