Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 317 318 319 320 321 322 323 >> Отображать по:
#113710
Маша и Маша.
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Маша и Маша - лучшие подруги. Однажды Маша и Маша пошли по магазинам. Оказалось, что Маша не хочет заходить в каждый a -ый магазин, а Маша в каждый b -ый. Но так как Маша любит Машу как подругу, а Маша как подругу любит Машу, Маша и Маша не заходят в магазин, если в него не хочет заходить ни Маша, ни Маша. В сколько магазинов зайдут Маша и Маша, если на их пути было n магазинов.

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

Единственная строка содержит три целых числа — a , b , n ( 1 ≤ a , b , n ≤ 10 9 )

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

Выведите единственное число — количество посещённых магазинов

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

Программы, работающие корректно для n ≤ 1000 получат 40 баллов.

Программы, работающие корректно для n ≤ 10000 получат 70 баллов.

Примеры
Входные данные
1 1 10
Выходные данные
0
Входные данные
1 2 5
Выходные данные
3
Входные данные
2 3 9
Выходные данные
8
#113774
Фурье?
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
512 megabytes

Жюри не гарантирует существование решения, выполняющегося на всех тестах с двукратным запасом времени работы.

Для числа k рассмотрим все такие различные мультимножества положительных чисел, что их сумма в точности k . Например для k = 3 эти множества {1, 1, 1} , {1, 2} , {3} .

Интересностью числа назовем сумму кубов размеров всех различных мультимножеств. Например интересность числа k = 3 равна 3 3 + 2 3 + 1 3 = 27 + 8 + 1 = 36 .

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

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

В единственной строке входных данных задаются два числа n и MOD ( 1 ≤ n ≤ 10 5 , 1 ≤ MOD ≤ 10 9 + 7 ) — максимальное число, для которого надо посчитать интересность, и модуль.

Модуль не обязательно простой.

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

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

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

Данная задача содержит 8 групп тестов, баллы за группу выставляются только при прохождении всех тестов группы.

  1. 1 ≤ n ≤ 5 , 5 баллов.
  2. 1 ≤ n ≤ 10 , 5 баллов.
  3. 1 ≤ n ≤ 20 , 10 баллов.
  4. 1 ≤ n ≤ 100 , 10 баллов.
  5. 1 ≤ n ≤ 1000 , 10 баллов.
  6. 1 ≤ n ≤ 5000 , 10 баллов.
  7. 1 ≤ n ≤ 50 000 , 25 баллов.
  8. 1 ≤ n ≤ 100 000 , 25 баллов.

Примеры
Входные данные
3 998244353
Выходные данные
1
9
36
Входные данные
10 3
Выходные данные
1
0
0
0
2
2
0
2
2
0
#113776
Лес
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes

Рассмотрим следующую игру об удалении вершин из графа, представляющего лес (то есть объединение нескольких деревьев). Изначально граф состоит из одного дерева из n вершин, а количество очков равно 0 .

Игра задаётся перестановкой вершин и происходит следующим образом:

  1. Если граф опустел, то игра заканчивается.
  2. Иначе выбирается первая ещё не удалённая вершина в перестановке, после чего
  3. Количество очков увеличивается на размер дерева из которого была выбрана вершина, а затем выбранная вершина и все связанные с ней рёбра удаляются, и тот же процесс продолжается на оставшемся графе.

Просуммируем число очков по всем возможным n ! играм. Выведите это число по модулю 10 9 + 7 .

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

В первой строке входного файла дано число N ( 2 ≤ n ≤ 10 5 ) — количество вершин в исходном дереве.

Каждая из последующих N - 1 строк содержит два числа — x i , y i задающих концы соответствующего ребра дерева ( 1 ≤ x i , y i ≤ n ).

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

Выведите одно число — суммарное количество очков по модулю 10 9 + 7 .

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

Тесты к данной задаче состоят из 3 групп:

  1. (20 баллов) n ≤ 10 .
  2. (40 баллов) n ≤ 5000
  3. (40 баллов) n ≤ 10 5

Примеры
Входные данные
2
1 2
Выходные данные
6
Входные данные
3
1 2
2 3
Выходные данные
34
#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
Страница: << 317 318 319 320 321 322 323 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест