Задача A. Азиатские страхи ≡

Условие

Некоторое число, являющееся результатом вычисления факториала из n, назовем числом x. Число x считается счастливым, если в его разложении на простые множители простое число k встречается не кратное 4 количество раз, а также более двух раз.

Разложение на простые множители - это представление числа в виде произведение простых множителей, из которых оно состоит. Например, число 120 раскладывается на 2  * 2 * 2  * 3 * 5.

Вам необходимо узнать, является ли x счастливым.

Формат входных данных

В первой строке находится целое число t - количество наборов входных данных. (1 ≤ t ≤ 10⁴)

Далее для каждого набора входных данных в одной строке располагается два целых числа n и k. (2 ≤ n ≤ 10⁶, 2 ≤ k ≤ n)

Формат выходных данных

Для каждого набора входных данных в отдельной строке выведите “Yes”, если число оказалось счастливым, или “No” в противном случае.

Примеры тестов

5
5 2
6 2
7 2
8 2
9 3

Yes
No
No
Yes
No

Задача B. Большая IT компания ≡

Условие

В большой IT компании сейчас ведется проект, который нужно закрыть в кратчайшие сроки. Для этого собрали большую команду IT специалистов, а именно:

• m₁ - разработчиков;
• m₂ - тестировщиков;
• m₃ - инженеров по развертыванию.

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

Нужно помнить, что каждый специалист может работать только с одним сервисов в один момент времени. А также, специалист не может перейти к работе над следующим сервисом, не закончив работу с текущим.

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

Напишите программу, которая поможет большой IT компании, а именно найдет оптимальный порядок обработки сервисов и выведет минимальное для этого время.

Формат входных данных

В первой строке записано целое число N (1 ≤ N ≤ 10⁵) - количество сервисов.

Во второй строке записано три целых числа m₁, m₂, m₃ (1 ≤ m₁,m₂, m₃ ≤ 1000) - количество разработчиков, тестировщиков и инженеров по развёртыванию.

В третьей строке записано три целых числа t₁, t₂, t₃ (1 ≤ m₁,m₂, m₃ ≤ 1000) - время, которое требуется на разработку, тестирование и развёртывание соответственно.

Формат выходных данных

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

Примеры тестов

3
3 1 1
1 1 1

5

Задача C. CODE ровка ≡

Условие

Отдыхая в баре с бесконечным числом математиков, у Вани родилась идея кодировки cwc7, не имеющей аналогов. В порыве вдохновения Ваня срочно закодировал все свои важные числа и довольным лёг спать. Однако на утро он обнаружил, что не может декодировать их обратно, поэтому очень ждёт вашей помощи!

Закодированный ряд представляет собой одно большое число x, не содержащее нолей. Чтобы вернуть исходный ряд нужно:

1. Разделить x на ряд чисел так, чтобы выполнялось условие x_i − 1 < x_i и x_i было минимально возможным.

159→ 1, 5, 9

1555→ 1, 5, 55

Если в конце осталось число, меньше или равное, чем последнее добавленное, то это явно информационный шум и его нужно выбросить.

1232→ 1, 2, 3

2. К каждому числу x_i из получившегося ряда применить формулу:

x_i = a^x_i mod 7,где a - это двузначное число, первая цифра которого - это первая цифра x_i, а вторая цифра - последняя цифра x_i.

Формат входных данных

В первой строке записано единственное положительное число x, которое не содержит нолей.

Формат выходных данных

Через пробел выведите получившийся ряд чисел.

Ограничения

1 ≤ len(x) ≤ 170

Пояснение к примеру

Во втором примере число разделится как 6 41 53:

66⁶ mod 7  = 1

41⁴¹ mod 7  = 6

53⁵³ mod 7  = 2

Примеры тестов

1555

4 6 6 

641539

1 6 2 

Задача D. Детский утренник ≡

Условие

В некоторой школе для одаренных детей у ребят появился новый тренд - вставать в ряд по неубыванию роста, т.е так, чтобы рост следующего школьника в ряду был не меньше роста текущего. Однако быть самым низким не нравится никому, поэтому каждый из школьников говорит вам, что он не хочет стоять в последних a_i местах (некоторые школьники не капризные вовсе и могут стоять на последнем месте).

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

Формат входных данных

В первой строке входных данных находится целое число n. (1 ≤ n ≤ 10⁵)

В следующих n строках располагается пара из вещественного и целого чисел h_i и a_i - рост школьника в сантиметрах и количество последних мест, на которые он не будет вставать. Рост имеет 6 знаков после точки. (130 ≤ h_i ≤ 190, 0 ≤ a_i < n)

Формат выходных данных

Вам требуется вывести n целых чисел: в i-ой строке максимальную длину ряда, который можно составить из первых i школьников. (1 ≤ i ≤ n)

Примеры тестов

5
174.500000 0
175.000000 1
173.000000 1
171.000000 0
180.000000 5

1
2
2
4
4

5
150.000000 1
150.000000 2
150.000000 0
150.000000 3
150.000000 4

0
0
3
4
5

Задача E. Ежеминутные указания ≡

Условие

На выставке виртуальной реальности всем желающим дается возможность поиграть в VR-очках. Но так как участнику для игры нужно свободное пространство, то их расстановкой занимаются менеджеры. А также участник не может играть вечно, поэтому на игру ему отводится определенное время. Все хотят поиграть подольше, поэтому каждый участник будет стоять именно свои t_i минут.

Другими словами, i-ый участник встает в точку (x_i, y_i), в которой он будет находиться t_i минут. Менеджеры ответственно выполняют свою работу, поэтому они не отправят человека в занятую точку.

Вы, как администратор площадки, обязаны отчитываться сколько человек находится в некотором прямоугольнике. Вы не занимаетесь общением с людьми, поэтому вам приходят указания от менеджеров вида:

• Поставить человека в точку (x_i, y_i)
• Сказать сколько человек находится на прямоугольнике, ограниченном точками (x₁, y₁), (x₂, y₁), (x₁, y₂), (x₂, y₂).

Прямоугольник описывается двумя точками (x₁, y₁) и (x₂, y₂), где x₁ ≤ x₂ и y₁ ≤ x₂. Точка (x, y) лежит на прямоугольнике, если (x₁ ≤ x ≤ x₂ и y₁ ≤ y ≤ y₂)

На выполнение каждого указания вы тратите T минут. Когда вам приходит указание посчитать людей, вы распечатываете для себя расстановку в текущий момент времени и считаете людей по ней. А время игры участника начинается сразу после того, как вы поставите его в точку.

Формат входных данных

В первой строке содержится два целых числа N и T - количество указаний и время, которое вы тратите на выполнение указания. (1 ≤ N, T ≤ 2 * 10⁵)

В следующих N строках описываются указания, первое число строки говорит о том, какое указание в этой строке:

1 - поставить человека в точку. Далее в этой следует 3 целых числа x_i, y_i, t_i. (1 ≤ x_i, y_i ≤ 500, 1 ≤ t ≤ 10⁴)

2 - сказать сколько человек в прямоугольнике. Далее следует 4 целых числа: x₁, y₁, x₂, y₂. (1 ≤ x1, x2, y1, y2 ≤ 500)

Всего K запросов вида 2.

Формат выходных данных

Вы должны вывести K натуральных чисел - ответы на запросы вида 2.

Примеры тестов

7 5
1 1 1 10
2 1 1 5 5
2 1 1 5 5
1 2 2 10
1 2 1 5
2 1 1 5 5
2 1 1 5 5

1
1
2
0

13 1
1 1 1 100
1 2 1 100
1 3 1 100
1 4 1 100
1 5 1 100
1 1 5 100
1 2 2 100
1 3 3 100
2 1 1 5 5
2 1 2 5 5
2 1 3 3 5
2 1 5 1 5
2 5 5 5 5

8
3
2
1
0

Задача F. Фантастическое чёрно-красное дерево ≡

Условие

Существует фантастическое черное-красное дерево - граф, который представляет из себя дерево (связный граф без циклов), в котором каждая вершина покрашена в один из двух цветов - красный или черный.

У вас есть не менее замечательная строка s, состоящая из K символов ‘r' и 'b’. Ваша задача - выяснить сколько существует путей по дереву, таких, что если выписать цвета вершин, по которым вы прошлись, то получится строка s.

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

Формат входных данных

В первой строке целое число N- количество вершин в графе.

Далее строка g состоящая из N символов ‘r' и 'b’, описывающая цвета вершин дерева.

Далее строка s, состоящая из K символов ‘r' и 'b’.

В следующих строках два целых числа - a_i и b_i - начало и конец ребра.

Формат выходных данных

Ограничения

2 ≤ K ≤ N ≤ 10⁴

Примеры тестов

5
brbrr
rbr
1 3
4 3
3 5
2 3

6

5
brrbr
rb
1 2
1 5
3 4
5 4

4

Задача G. Говорят программисты много зарабатывают ≡

Условие

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

Красивой зарплатой он называл ту, которая была задана простым числом и являлась палиндромом. Теперь Алексей хочет посчитать только такие зарплаты за последнее время. Помогите ему справится с этим.

Формат входных данных

Первая строка входных данных содержит целое число n - количество зарплат Алексея.

Следующие n строк содержат целое число k зарплату Алексея за месяц в пуплях.

Формат выходных данных

Выведите единственное число - сумму только красивой зарплаты Алексея за n месяцев. Гарантируется, что сумма всех зарплат Алексея не превышает 10⁹ пуплей.

Ограничения

1 ≤ n ≤ 1000

1 ≤ k ≤ 10⁶

Примечание

Палиндром - число, одинаково читающееся в обоих направлениях.

Простое число - натуральное число, имеющее ровно два различных натуральных делителя.

Пример:

• 7 - простое число
• 101 - палиндром

Примеры тестов

3
1
7
11

18

2
191
8

191

Задача H. Нерассудительность ≡

Условие

У вас есть друг Петя, которому вы дали k рублей и отправили его в магазин купить круп, чтобы приготовить ужин. Вы сказали ему сколько и чего купить, но у него, конечно же, сразу всё вылетело из головы. Однако Петя - человек гордый, поэтому звонить и переспрашивать не будет. Он поступит нерассудительно - купит крупы наугад.

В магазине все крупы продаются только пакетами по 1кг и стоят одинаково.

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

Две покупки являются различными, если существует такая крупа, что ее количество в первой покупке отличается от количества во второй покупке.

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

Петя может как купить на все деньги крупы одного вида, так и не купить круп вовсе (прийти в магазин просто так).

Формат входных данных

Во входной строке три целый числа: n, k и m - количество видов круп, количество денег у Пети и стоимость одного килограмма. (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ k ≤ 10⁵)

Формат выходных данных

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

Так как ответ может оказаться слишком большим, выведете его по модулю 10⁹ + 7

Примеры тестов

1 2 1

3

2 4 2

6

Задача I. Игра в слова ≡

Условие

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

Слова состоят из строчных латинских букв.

“Непохожесть“ слова а на слово b определяется по следующей формуле:

oversetn∑i = 1((a_i − b_i) ⋅ 100^i − 1, если a_i ≥ b_i)

oversetn∑i = 1((b_i − a_i + 50) ⋅ 100^i − 1, если a_i < b_i)

Где i - индекс буквы, a_i, b_i - алфавитные номера букв в словах на i-ом месте.

В нашем случае a - одно из раннее сказанных слов, b - только что сказанное слово.

В первый раунд Паше отвечать не нужно.

Пояснение

Непохожесть слова code на слово work вычисляется следующим образом:

порядок букв в алфавите:

с − 3, o − 15, d − 4, e − 5

w − 23, o − 15, r − 18, k − 11

(23 − 3 + 50)100⁰ + (15 − 15)100¹ + (18 − 4 + 50)100² + (11 − 5 + 50)100³ = 56640070

Формат входных данных

В первой строке располагается два целых числа n и k - длина слова и количество ходов в игре.

В следующих k строках располагаются строки длины n - слова, которые говорит Миша.

Формат выходных данных

Вам необходимо вывести k − 1 слов - ответы Паши.

Ограничения

1 ≤ n ≤ 6000 1 ≤ k ≤ 300

Примеры тестов

3 5
abd
cdc
zdd
ccd
zxc

abd
cdc
cdc
abd

4 4
code
work
tthe
best

code
work
code

Задача J. Jade portal ≡

Условие

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

Вы попали в странный мир, и у вас на руках оказалось n рун со странным знаками на них. Вы видите перед собой неработающий нефритовый портал, в котором есть k ячеек.

Немножко поигравшись, вы заметили, что у рун есть своя энергия, и если попытаться засунуть руну в ячейку, то появится вспышка разных цветов:

• Белая, если в этой ячейке нет других рун.
• Синяя, если руна, которую вы пытаетесь положить имеет меньшую энергию, чем руны, которые уже лежат в этой ячейке.
• Зеленая, если руна, которую вы пытаетесь положить имеет такую же энергию, как руны, которые уже лежат в этой ячейке.
• Красная, если руна, которую вы пытаетесь положить имеет большую энергию, чем руны, которые уже лежат в этой ячейке.

Вы догадываетесь, что вам надо расположить руны по ячейкам в соответствии с их энергией. То есть в одной ячейке должны быть только руны одинаковой энергии.

Чтобы в ячейках не было рун разной энергии, когда вы видите синюю или красную вспышку, вы кладете только что добавленную руну обратно (К себе в карман или в ее прежнюю ячейку, в зависимости от того, где она была до этого). Неправильное расставление и возврат руны назад считаются за одну попытку.

Вам необходимо все руны раскидать по ячейкам. Гарантируется, что такое расположение рун существует. Времени у вас мало, поэтому вы можете сделать не более 15 * n попыток расставления.

Формат входных данных

При запуске решения на вход в первой строке подаются два целых числа k и n - количество ячеек в портале и количество рун.

Формат выходных данных

Вы можете делать запросы посредством вывода «? i j», где i,j - номер руны и номер ячейки, в которую вы собираетесь положить эту руну соответственно.

Ответом будет выведена одна из строчек «White», «Blue», «Green» или «Red» в зависимости от рун в ячейке.

Вы можете сделать не более 15 * n запросов. Вывод ответа не считается за запрос.

Вы можете вывести ответ, выведя «!», если считаете, что расположили все руны по их энергии.

Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n, а также необходимо выполнить сброс буфера:

Ограничения

1 ≤ k < n ≤ 1000

Пояснение к примеру

Энергия рун в данном примере была следующая: a₃ a₂ a₂ a₁, где a₃ > a₂ > a₁

Примеры тестов

3 4

White

Blue

White

Blue

Green

Blue

White

? 1 1

? 2 1

? 2 2

? 3 1

? 3 2

? 4 2

? 4 3

!

Задача K. Кучка матриц ≡

Условие

У вас есть квадратная матрица A размера n × n.

Также у вас есть k матриц B_k тоже размера n × n.

От вас требуется найти такие две матрицы, произведение которых даст матрицу A (если таких матриц не существует, выведите -1). Эти матрицы должны иметь различные индексы.

Перемножение матриц:

Матрицы перемножаются по принципу строка на столбец. Результат кладётся в клетку их пересечения.

Рассмотрим это на примере матриц: A_2 × 2 = [a₁₁ a₁₂a₂₁ a₂₂] и B_2 × 2 = [b₁₁ b₁₂b₂₁ b₂₂]. A × B = C.

C_2 × 2 = [a₁₁ * b₁₁ + a₁₂ * b₂₁ a₁₁ * b₂₁ + a₁₂ * b₂₂a₂₁ * b₁₁ + a₂₂ * b₂₁ a₂₁ * b₂₁ + a₂₂ * b₂₂].

Общая формула выглядит так: c_ij = a_i1 b_1j + ... + a_in b_nj.

Формат входных данных

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

В следующих строках описываются матрицы B_k. Матрицы разделены пустыми строкам. Каждая строка матрицы располагается в новой строке. Элементы матрицы в строке разделены пробелами.

Далее описывается матрица A.

Элементы матриц - целые числа.

Формат выходных данных

Выведите -1, если не нашлась подходящая пара матриц.

Или два различных индекса найденных матриц в порядке возрастания в ином случае.

Ограничения

2 ≤ k ≤ 30

2 ≤ n ≤ 100

 − 10³ ≤ b_k ≤ 10³

 − 10⁹ ≤ a_k ≤ 10⁹

Примеры тестов

3 2
1 1
1 1

2 2
2 2

3 3
3 3

6 6
6 6

1 3

3 2
1 2
3 4

4 3
2 1

1 0
0 1

0 0
0 0

-1

Задача L. Лабиринт токсиков ≡

Условие

Денис посетил вечеринку спортивных программистов в Точке кипения, где участники обсуждали различные алгоритмы. В ходе обсуждения возник спор о задачах на BFS. Одни считали их интересными, другие - душными. Через какой-то время спор почти дошел до драки между участниками, после чего любители задач на BFS назвали своих противников “токсиками” и решили закрыть их в Точке кипения. В свою очередь Точка кипения представляет собой лабиринт.

Точка кипения представлена матрицей размерностью n×m. Она может содержать следующие символы:

• ‘.’ - пустая клетка;
• ‘#’ - стена;
• ‘S’ - любитель BFS;
• ‘T’ -токсик.

Любители BFS хотят заблокировать противников, а именно заменить некоторые пустые клетки на стены так, чтобы все любители BFS смогли добраться до выхода, а все токсики остались заперты в Точке кипения.

Клетки, которые изначально содержат символы 'S' или 'T', не могут быть заблокированы, но через них можно проходить.

Помогите Денису определить, можно ли заблокировать некоторые пустые клетки в Точке кипения так, чтобы ВСЕ любители BFS смогли выйти, но при этом токсики бы не смогли. Люди могут передвигаться на соседние клетки в Точке кипения по вертикали и по горизонтали. Учтите, что разрешается не блокировать клетки вовсе и блокировать выход из точки кипения. Гарантируется, что выход из лабиринта всегда представляет собой пустую клетку.

Формат входных данных

Первая строка содержит одно целое число t (1 ≤ t ≤ 1000) - количество наборов входных данных.

Для каждого набора входных данных:

• первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 100) - размерность лабиринта;
• в каждой из следующих n строк записано m символов. Символ '.' обозначает пустую клетку, '#' - стену, 'S' - любителя BFS, а 'T' - токсика.

Формат выходных данных

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

Примеры тестов

2
3 3
S..
...
T..
2 2
ST
T.

YES
NO