Задача A. Семь простых чисел

Артем будет выступать на танцевальном соревновании. После выступления каждый из 7 членов жюри выставляет положительную оценку. Сумма этих оценок является общим баллом. Артем считает выступление хорошим, если его общий балл будет равен $N$. Он же считает выступление идеальным, если выступление будет хорошим и каждая оценка от жюри будет простым числом. Выведите пример оценок жюри идеального выступления для заданного $N$ или ``-1'', если решение не существует. Если существует несколько решений выведите любое. В первой строке входного файла задается одно положительное целое число $N$ ($5 \le N \le 10^{15}$). Если решение существует, выведите семь простых чисел, разделенных пробелом, в любом порядке. Если решение не существует, выведите ``-1''. Вход

5

Ответ

-1

Вход

14

Ответ

2 2 2 2 2 2 2

Подзадача 1 — 17 баллов ($1 \le N \le 30$) Подзадача 2 — 19 баллов ($1 \le N \le 1000$) Подзадача 3 — 23 балла ($1 \le N \le 10^{9}$) Подзадача 4 — 41 балл ($1 \le N \le 10^{15}$)

Задача B. Мансур побеждает Александра

Задана игра на кучках камней. Ход игрока заключается в том, что он может взять произвольное количество камней из одной кучки, либо поровну из всех. Игроки чередуют ходы. Проигрывает тот, кто не может сделать ход. Мансур играет в эту игру с Александром. На столе лежат две кучки камней, в первой $a$, во второй $b$ камней. Первым ходит Мансур. Мансур понял, что если он может проиграть в заданную игру, он может своим ходом добавить третью кучку камней так, чтобы гарантированно победить. Если Мансур добавляет третью кучку, то ход переходит к Александру и далее игра идет только на трех кучках. Теперь перед ним встала задача, может ли он выиграть в эту игру или ему нужно первым ходом добавить третью кучку, тогда какого она должна быть размера? Помогите Мансуру. Мансур и Александр опытные ACMщики, поэтому можете считать, что они всегда ходят оптимально. В первой строке входных данных задано одно целое число $1 \le T \le 100000$ — количество тестов. В следующих $T$ строках заданы тесты: два целых числа $a$ и $b$, разделенных одним пробелом. Выведите $T$ строк, ``MANSUR''\ если Мансур побеждает в изначальной игре, либо число $x$, если Мансуру нужно добавить кучку из $x$ камней чтобы победить. Если существует несколько ответов выведите любой. Вход

5
1 1
1 2
3 3
3 5
9 24

Ответ

MANSUR
3
MANSUR
6
MANSUR

Подзадача 1 — 21 балл $1 \le a,b \le 100$ Подзадача 2 — 23 балла $1 \le a,b \le 10000$ Подзадача 3 — 27 баллов $1 \le a,b \le 1000000$ Подзадача 4 — 29 баллов $1 \le a,b \le 10000000$

Задача C. Максимальный квадрат

Дана матрица размера $N \times M$ состоящая только из нулей и единиц. Нужно найти наибольшую квадратную подматрицу, в сторонах которой только единицы. Первая строка входного файла содержит два целых числа $N$ и $M$. Следующие $N$ строк содержат по $M$ цифр 0 и 1, разделенных пробелом. Если таких квадратов нет, выведите 0. Выведите одно целое число -- размер максимального квадрата, в сторонах которого только единицы. Вход

4 5
01111
01011
11001
11111

Ответ

4

Вход

2 3
000
000

Ответ

0

Вход

3 3
011
011
010

Ответ

2

Подзадача 1 — 30 баллов ($1 \le N, M \le 100$) Подзадача 2 — 29 баллов ($1 \le N, M \le 300$) Подзадача 3 — 41 баллов ($1 \le N, M \le 1500$)

Задача D. Еще одна задача на XOR

Вам дан массив $A$ из $n$ неотрицательных целых чисел, посчитайте количество пар чисел $1 \le l \le r \le n$, таких что $X \le A[l]\ xor\ A[l + 1]\ xor\ ...\ xor\ A[r]$, для некоторого заданного целого числа $X$. $xor$ — операция побитового сложения (в двоичной системе) по модулю два. Результатом этой операции является единица только в том случае, если биты операндов различны. Пример: $10_{10}\ xor\ 23_{10}\ =\ 29_{10}$, $1010_2\ xor\ 10111_2\ =\ 11101_2$, здесь записано одно и то же равенство в десятичной, а затем в двоичной системе счисления. В первой строке входных данных содержится два целых числа, разделенных пробелом $n$ и $0 \le X \le 10^9$. В следующей строке заданы $n$ целых чисел разделенных пробелами. Каждое из этих чисел не превосходит $10^9$. Единственное число, ответ на задачу. Вход

5 0
1 2 3 4 5

Ответ

15

Вход

3 3
1 2 3

Ответ

2

Подзадача 1 — 31 баллов $1 \le n \le 1000$ Подзадача 2 — 69 балла $1 \le n \le 100000$

Задача E. Сумма в симпатичной таблице

Вам задана прямоугольная таблица $A$ из $n$ строк и $m$ столбцов. В этой таблице ровно $n \times m$ ячеек, пронумерованных последовательно натуральными числами сверху вниз, слева направо. $A[i][j]$ будем обозначать ячейку прямоугольной таблицы $A$ стоящей на пересечений $i$-ой строки и $j$-го столбца. Для конкретно заданного числа $x$ симпатичной таблицей будет являться таблица $A$, для которой значения в ячейках таблицы будут равны $x$ в степени номера соответствующей ячейки. Более формально $A[i][j] = x^{(i - 1) * m + j}$. Даны $q$ запросов границы под прямоугольника $x1,x2,y1,y2$ и модуль $p$, ответом на каждый запрос будет сумма чисел в соответствующем под прямоугольнике по соответствующему модулю. Более формально $\left(\sum\limits_{i=x1}^{x2}{\sum\limits_{j=y1}^{y2}{A[i][j]}}\right) mod\ p$. Напишите программу, отвечающую на заданные запросы. Симпатичная таблица $A$, $3$ на $4$, для числа $x$ будет выглядеть следующим образом:\\ $A = \begin{pmatrix} x^{1} & x^{2} & x^{3} & x^{4}\\ x^{5} & x^{6} & x^{7} & x^{8}\\ x^{9} & x^{10} & x^{11} & x^{12} \end{pmatrix}$ В первой строке входных данных заданы три целых числа, разделенных пробелами $n,m,x$. В следующей строке входных данных задано единственное целое число $q$. В следующих $q$ строках входных данных заданы запросы, каждый запрос задается пятью числами, разделенных пробелами $x1,x2,y1,y2,p$, $1 \le x1 \le x2 \le n$, $1 \le y1 \le y2 \le m$. Выведите q чисел, по одному на каждой строке, ответы на соответствующие запросы. Вход

1 10 2
5
1 1 1 1 1000000007
1 1 1 2 1000000007
1 1 1 5 1000000007
1 1 2 4 1000000007
1 1 2 3 1000000007

Ответ

2
6
62
28
12

Подзадача 1 — 7 баллов $n = 1$, $1 \le m \le 10$, $1 \le x \le 5$, $1 \le q \le 100$, $p = 10^9 + 7$ Подзадача 2 — 9 баллов $1 \le n \le 100$, $1 \le m \le 100$, $1 \le x \le 10^9$, $1 \le q \le 100$, $p = 10^9 + 7$ Подзадача 3 — 11 баллов $1 \le n \le 1000$, $1 \le m \le 1000$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $p = 10^9 + 7$ Подзадача 4 — 21 баллов $1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $p = 10^9 + 7$ Подзадача 5 — 52 баллов $1 \le n \le 10^9$, $1 \le m \le 10^9$, $1 \le x \le 10^9$, $1 \le q \le 10^4$, $1 \le p \le 10^9$

Задача F. Радость информатика

В этом году на олимпиаде по информатике участвуют $N$ учеников. Участники пронумерованы от $1$ до $N$. С новой системой, они видят свои баллы сразу после отправки решения по задаче. От результата проверки, настроение участника может очень сильно измениться. В самом начале олимпиады, настроение всех участников равно единице. Есть история изменений настроения участников. Жюри хочет контролировать настроение всех участников, и просит вас о помощи. У вас есть запросы трех видов: $0$ $L$ $R$ $P$ - Жюри хочет знать произведение настроения всех участников, пронумерованных от $L$ до $R$. Но так как это число может быть слишком большим, надо вывести его по модулю $P$ $1$ $L$ $R$ $X$ - Все участники с номерами от $L$ до $R$ узнали результат проверки и настроение каждого из них умножилось на число $X$ $2$ $L$ $R$ $X$ - Все участники с номерами от $L$ до $R$, узнали результат проверки и настроение каждого из них поделилось на число $X$, гарантируется что настроение каждого участника на этом отрезке делится на число $X$. Во всех запросах $1 \le L \le R \le N$. В первой строке вводится число $N$ и $M$, количество участников и количество запросов. В следующих $M$ строках описываются запросы Для каждого запроса типа 0, вывести ответ на отдельной строке. Вход

5 5
0 1 5 1000000007
1 2 3 6
0 1 5 1000000007
2 2 3 3
0 1 5 1000000007

Ответ

1
36
4

Вход

3 5
1 1 3 100
0 1 2 10
2 1 3 100
1 2 3 4
0 1 3 10

Ответ

0
6

В 10\% тестов, $1 \le X \le 100$, $P = 10^9+7$, $1 \le N \le 5000$, $1 \le M \le 5000$, нет запросов типа 2 (поделить на $x$) В 45\% тестов, $1 \le X \le 100$, $P = 10^9+7$, $1 \le N \le 5000$, $1 \le M \le 5000$ В 100\% тестов, $1 \le X \le 100$, $1 \le P \le 10^9$, $1 \le N \le 50000$, $1 \le M \le 50000$