Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 513 514 515 516 517 518 519 >> Отображать по:
#113784
Количество соседних цветов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

Дан неориентированный граф без петель и кратных ребер, у которого n вершин и m ребер. У каждой вершины есть цвет. Требуется ответить на q запросов. Каждый запрос имеет один из двух типов:

1 v c – перекрасить вершину v в цвет c

2 v – вычислить количество различных цветов у соседей вершины v .

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

В первой строке даны три целых числа n , m и q ( 1 ≤ n ≤ 10 5 , 1 ≤ m , q ≤ 2·10 5 ).

Во второй строке через пробел даны n целых чисел 1 ≤ c 1 , ..., c n ≤ n – цвета вершин.

В следующих m строках заданы по два целых числа u и v – номера вершин, которые соединяет очередное ребро ( 1 ≤ u , v ≤ n , u ≠ v ).

В следующих q строках заданы запросы. Каждый запрос имеет один из двух типов:

1 v c – перекрасить вершину v в цвет c , 1 ≤ v , c ≤ n .

2 v – вычислить количество различных цветов у соседей вершины v , 1 ≤ v ≤ n .

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

Для каждого запроса второго типа выведите в отдельной строке ответ на него.

Примеры
Входные данные
4 3 3
1 2 3 4
1 2
1 3
1 4
2 1
1 4 3
2 1
Выходные данные
3
2
#113785
Количество элементов < x и инкремент на отрезке
  
ограничение по времени на тест
8.0 second;
ограничение по памяти на тест
256 megabytes

Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа. Запрос первого типа – вычислить количество элементов массива на отрезке от l до r меньших заданного числа x . Запрос второго типа – увеличить все элементы массива на отрезке от l до r на заданное число x .

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

В первой строке заданы два целых числа n и q – размер массива и количество запросов ( 1 ≤ n , q ≤ 2·10 5 ).

Во второй строке через пробел заданы n целых чисел - 10 9 ≤ a 1 , ..., a n ≤ 10 9 – элементы массива.

В следующих q строках содержатся запросы. Каждый из запросов имеет один из двух видов:

1 l r x – запрос количества элементов на отрезке от l до r меньших заданного числа x ( 1 ≤ l ≤ r ≤ n , - 10 9 ≤ x ≤ 10 9 ).

2 l r x – запрос инкремента на величину x на отрезке от l до r ( 1 ≤ l ≤ r ≤ n , - 10 6 ≤ x ≤ 10 6 ).

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

На каждый запрос первого типа выведите в отдельной строке ответ на этот запрос.

Примеры
Входные данные
5 3
1 2 3 4 5
1 1 5 5
2 2 4 2
1 1 5 5
Выходные данные
4
2
#113804
Блэкджек
  
Темы: [Формула]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

В блэкджеке игрок может брать карты из колоды до тех пор, пока сумма его карт не превосходит 21 или пока он не скажет «DOSTA» («Стоп» по-хорватски).

В начале игры в колоде есть по 13 карт каждой масти, 9 из которых имеют числовые значения 2, 3, ..., 10 ; так же «Валет», «Дама» и «Король» имеют числовые значения 10 ; а «Туз» — 11 .

Цезарь уже сделал n ходов и уже достал из колоды некоторые карты с суммой менее 21 . Теперь он хочет понять, стоит ли брать ещё одну карту, или остановиться. Пусть X — разница межу 21 и суммой карт. Как известно, новую карту не стоит брать, если число карт со значением больше X превышает число карт со значением не более X .

Цезарь испытывает некоторые проблемы с арифметикой, поэтому он просит вас сообщить ему, стоит ли брать новую карту.

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

В первой строке водится n — число карт, которые уже взяты. Далее написаны n числовых значений уже взятых карт — по одному в каждой строке.

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

Если Цезарю надо взять ещё одну карту, в единственной строке выведите « VUCI » («Дальше» по-хорватски), иначе выведите « DOSTA » («Стоп» по-хорватски).

Примечание

В первом примере сумма карт уже 15 , соответственно X = 6 . В колоде осталось 32 карты со значением больше 6 ( 4 «Туза», 4 «Короля», 4 «Дамы», 4 «Валета», 4 «Десятки», 4 «Девятки», 4 «Восьмёрки» и 4 «Семёрки») и 14 карт со значением не более 6 ( 1 «Двойка», 1 «Тройка», 4 «Четвёрки», 4 «Пятёрки», 4 «Шестёрки»). Поэтому новую карту брать не надо.

Примеры
Входные данные
6
2
3
2
3
2
3
Выходные данные
DOSTA
Входные данные
1
10
Выходные данные
VUCI
Входные данные
2
5
6
Выходные данные
VUCI
#113805
Тетрис
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Ивица — страстный компьютерщик. Недавно он начал работать над своей первой компьютерной игрой — клоном популярного тетриса. Хотя игра далека от завершения, его программа уже поддерживает размещение в матрице N × M пяти разных фигур Тетриса (показанных на изображении ниже) в матрице. Перед тем, как поместить фигуру в матрицу, её можно поворачивать на 90 градусов произвольное число раз и можно окрашивать. Кроме того, текущая версия игры не поддерживает размещение фигуры, если она при этом выходит за границы матрицы или перекрывается с другими существующими фигурами в матрице.

Пока Ивица учился в школе, его сестра Марика начала игру и случайным образом повернула, покрасила и поместила фигуры, но таким образом, что соседние фигуры окрашены по-разному. Две фигуры смежны, если они имеют общую сторону или общий угол.

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

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

Первая строка ввода содержит положительные целые числа N и M ( 1 ≤ N , M ≤ 10 ), которые представляют количество строк и столбцов матрицы Тетриса. Каждая из следующих N строк содержит M символов, которые представляют матрицу. Каждый символ может быть « . », что означает пустую клетку или строчной буквой английского алфавита, которая представляет часть фигуры. Различные буквы представляют разные цвета, а клетки одной фигуры имеют одинаковый цвет.

Гарантируется, что вводная матрица могла быть получена последовательным добавлением фигур Тетриса в изначально пустую матрицу.

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

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

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

Примеры
Входные данные
4 5
aaaa.
.bb..
.bbxx
...xx
Выходные данные
2
1
0
0
0
Входные данные
4 5
.aab.
aabb.
.cbaa
cccaa
Выходные данные
1
0
1
1
1
Входные данные
5 7
.c.....
ccdddd.
caabbcc
aabbacc
...aaa.
Выходные данные
1
1
2
1
1
#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
Страница: << 513 514 515 516 517 518 519 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест