«Тинькофф» проводит ребрендинг! В силу последних трендов логотипов компаний, было решено, что новый логотип будет в шахматной раскраске. Это значит, что логотип будет являться фигурой, состоящей из квадратов $$$1 \times 1$$$, причем любые два квадрата, соседних по стороне, имеют разные цвета, один из них черный, а другой — белый. Логотип также должен быть связным: от любого квадрата до любого другого можно дойти, переходя на соседний по стороне квадрат.
Брендбук предписывает, что в логотипе должно быть $$$w$$$ белых клеток и $$$b$$$ черных. Чтобы логотип не выглядел слишком темным (а также для упрощения вашей работы), верно, что $$$b \le w \le 3b + 1$$$.
Для того, чтобы создать новые логотипы «Тинькофф», были закуплены листы в шахматной раскраске, каждый размером $$$4n$$$ строк на $$$4m$$$ столбцов, из которых вы будете вырезать логотипы. Левая верхняя клетка каждого листа раскрашена в черный цвет. На всякий случай, размеры листов выбрали с запасом, чтобы логотип наверняка влез: число черных клеток $$$b$$$ не превосходит $$$nm$$$.
Ваша задача в том, чтобы разработать связный логотип из $$$b$$$ черных и $$$w$$$ белых клеток так, чтобы он помещался на заготовку размера $$$4n \times 4m$$$. Аналитики компании доказали вам, что в таких ограничениях всегда возможно сделать логотип, подходящий под условия $$$b \le w \le 3b + 1$$$ и $$$b \le nm$$$.
Входные данные содержат несколько тестов.
В первой строке задано целое число $$$t$$$ — число тестов во входных данных ($$$1 \le t \le 2\,000$$$). Далее идут $$$t$$$ тестов, каждый в отдельной строке.
Каждая строка содержит четыре целых числа $$$n$$$, $$$m$$$, $$$b$$$, $$$w$$$ ($$$1 \le n, m \le 50$$$; $$$0 \le b \le n \cdot m$$$; $$$b \le w \le 3b + 1$$$).
Сумма $$$4n \cdot 4m$$$ по всем тестам не превосходит $$$2 \cdot 10^5$$$.
Для каждого теста выведите матрицу размером $$$4n \times 4m$$$, на которой изображен черно-белый логотип. Символом «W» обозначьте белые клетки фигуры, символом «B» — чёрные клетки фигуры, а символом «.» — клетки листа, не принадлежащие логотипу.
Если существует несколько возможных решений, выведите любое.
| Подзадача | Баллы | Ограничения |
| 1 | 20 | $$$b = w$$$ |
| 2 | 25 | $$$b \le 2m - 1$$$ |
| 3 | 25 | $$$b \le 2(n + m) - 3$$$ |
| 4 | 30 | Без дополнительных ограничений |
2 2 3 5 7 2 2 4 8
............ ..WBWBWBW... .....W...... .....B...... .....W...... .....B...... .....W...... ............ ........ ........ ...W.W.. ..WBWB.. ...W.W.. ..WBWB.. ........ ........
Это интерактивная задача.
Жюри загадало пятизначное простое число (без ведущих нулей). Ваша задача состоит в том, чтобы отгадать это число. Для вашей каждой догадки программа жюри вернет вам информацию о том, какие цифры уже стоят на своем месте, а какие цифры есть в этом числе, но находятся в другом разряде.
Например, если жюри загадало число 19937, а ваша догадка — 31357, то ответом жюри будет ??-{}-+: последняя цифра 7 стоит на своем месте, а первые две цифры присутствуют в числе, но не стоят на своих местах. Обратите внимание, что второе вхождение цифры $$$3$$$ помечено, как -, потому что в загаданном числе $$$3$$$ встречается только один раз.
Более формально: пусть жюри загадало число $$$S = s_1 s_2 s_3 s_4 s_5$$$, а ваша догадка это $$$T = t_1 t_2 t_3 t_4 t_5$$$. Во всех позициях $$$i$$$, где $$$s_i = t_i$$$, вам вернется +. Все такие позиции будем считать использованными. Для оставшихся позиций, слева направо, выполняется следующая проверка: если цифра $$$t_i$$$ присутствует среди еще не использованных цифр в $$$S$$$, то в $$$i$$$-й позиции ответа будет стоять ?, а соответствующая цифра в $$$S$$$ помечается, как использованная. Во всех остальных позициях в ответе жюри будет стоять -.
В этой игре есть два режима: простой и сложный. В простом режиме вашей догадкой может быть любая строка из пяти цифр (ведущие нули разрешены). В сложном режиме вы можете спрашивать только про пятизначные простые числа без ведущих нулей. Для каждой подзадачи есть определенный лимит запросов, в который нужно уложиться.
В каждом тесте будет $$$T$$$ раундов, в каждом из которых вам нужно будет отгадать число. Набор загаданных чисел для каждого теста фиксирован до начала олимпиады.
В самом начале взаимодействия вы должны считать строку, сообщающую, в каком режиме проходит игра — простом или сложном, а также максимальное число догадок $$$L$$$, которые вы можете использовать для каждого числа. Простой режим обозначается строкой «easy», а сложный режим — строкой «hard».
Затем, в следующей строке вы должны считать число $$$T$$$ ($$$1 \le T \le 10$$$) — количество раундов, в которых вам предстоить отгадать простое число.
Каждый раунд состоит из того, что вы отправляете строку из пяти цифр. В простом режиме на эту строку нет ограничений, а в сложном режиме эта строка должна задавать пятизначное простое число без ведущих нулей. В ответ от программы жюри вы получите строку из пяти символов -, ?, или +. Если же вы нарушили формат взаимодействия, либо на $$$L$$$-м запросе раунда вы не угадали число, вы получите в ответ строку !!!!!. После получения этого ответа вам необходимо завершить исполнение программы.
После того, как вы получили ответ +++++, начинается следующий раунд. После окончания последнего раунда вам необходимо завершить исполнение программы. Не забывайте выводить перевод строки после каждой догадки.
| Подзадача | Баллы | Сложный режим? | Ограничения | Необх. подзадачи |
| 1 | 7 | $$$-$$$ | $$$L = 100$$$ | – |
| 2 | 11 | $$$+$$$ | $$$L = 100$$$ | 1 |
| 3 | 8 | $$$-$$$ | $$$L = 10$$$ | 1 |
| 4 | 15 | $$$+$$$ | $$$L = 10$$$ | 1,2,3 |
| 5 | 12 | $$$-$$$ | $$$L = 7$$$ | 1,3 |
| 6 | 16 | $$$+$$$ | $$$L = 7$$$ | 1,2,3,4,5 |
| 7 | 14 | $$$-$$$ | $$$L = 5$$$ | 1,3,5 |
| 8 | 17 | $$$+$$$ | $$$L = 5$$$ | 1,2,3,4,5,6,7 |
easy 10 1 -??+- -+--? +++++
12345 78778 28843
hard 5 1 ??--+ ?+--? +++++
31357 99083 19937
Даны два массива целых чисел $$$a$$$ и $$$b$$$ размера $$$n$$$. Найдите такой массив целых неотрицательных чисел $$$c$$$ длины $$$n$$$, что если прибавить его поэлементно к $$$a$$$ и $$$b$$$, то произведения чисел в новых массивах будут равны, либо скажите, что это невозможно.
Более формально, вам нужно найти целые неотрицательные числа $$$c_1, c_2, \ldots, c_n$$$, такие что $$$(a_1 + c_1) \cdot (a_2 + c_2) \cdot \ldots \cdot (a_n + c_n) = (b_1 + c_1) \cdot (b_2 + c_2) \cdot \ldots \cdot (b_n + c_n)$$$.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество чисел в массивах $$$a$$$ и $$$b$$$.
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$).
В третьей строке находятся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 1000$$$).
Если ответа не существует, выведите «NO». Иначе, в первой строке выведите «YES», а в следующей строке — $$$n$$$ целых чисел $$$c_1, c_2 \ldots c_n$$$ ($$$0 \le c_i \le 10^{18}$$$) — решение задачи. Если решений несколько — выведите любое. Гарантируется, что если решение существует, то существует и решение, подходящее под ограничения.
| Подзадача | Баллы | Ограничения |
| 1 | 9 | $$$n \le 2; a_i, b_i \le 10$$$ |
| 2 | 25 | $$$n \le 2$$$ |
| 3 | 19 | $$$n \le 3$$$ |
| 4 | 18 | $$$a_i, b_i \le 2$$$ |
| 5 | 29 | Без дополнительных ограничений |
4 1 2 5 4 6 1 6 2
YES 6 4 1 1
Мечта Юлии наконец-то сбылась: она стала руководителем Отдела Общего Управления Иннополиса (ООУИ)! В её отделе всё устроено наиболее современным образом: документы разрабатываются на компьютерах с использованием программного обеспечения последнего поколения.
В Отделе имеется $$$n$$$ рабочих компьютеров, к каждому из которых прикреплён уникальный номер от $$$1$$$ до $$$n$$$ и опытный сотрудник, работающий только на нём. Некоторые пары компьютеров соединены кабелем, позволяющим передавать данные между этими компьютерами в обе стороны. При этом, между любыми двумя компьютерами существует ровно один способ передать данные по кабелям, не используя никакой кабель дважды. Иными словами, сеть компьютеров и кабелей образует дерево.
В настоящий момент в отделе разрабатывается $$$k$$$ законопроектов. Юлии нужно составить план на завтра: она должна для каждого компьютера определить, какой из $$$k$$$ законопроектов будет править сотрудник за этим компьютером. Каждый сотрудник должен работать ровно над одним законопроектом в течение дня, но, при этом, один законопроект может одновременно редактироваться на нескольких компьютерах (или даже ни на одном). Некоторые сотрудники имеют свой любимый законопроект, и они согласны редактировать только его. Кроме того, в соответствии с законодательством, нельзя допустить, чтобы на двух компьютерах, соединённых кабелем, редактировался один и тот же законопроект.
Юля очень взволнована перед своим первым рабочим днем, и ей интересно, сколько у неё есть способов составить план на завтра, удовлетворив все пожелания сотрудников и требования законодательства. Помогите ей найти это число способов! Так как искомое число может быть большим, найдите его по модулю $$$10^9+7$$$.
Первая строка содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — число компьютеров в Отделе Общего Управления Иннополиса и число разрабатываемых законопроектов соответственно.
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$), где $$$a_i$$$ — номер любимого законопроекта сотрудника за компьютером $$$i$$$, или $$$0$$$, если он согласен редактировать любой законопроект.
В каждой из следующих $$$n - 1$$$ строк дано по два целых числа $$$u_j$$$ и $$$v_j$$$ — номера компьютеров, соединенных кабелем ($$$1 \le u_j, v_j \le n$$$; $$$u_j \neq v_j$$$). Гарантируется, что сеть компьютеров и кабелей образует дерево.
В единственной строке выведите одно целое число — количество способов составить план на завтра, удовлетворяющий всем требованиям, взятое по модулю $$$10^9+7$$$.
| |} Подзадача | Баллы | Ограничения |
| 1 | 5 | $$$n, k \le 8$$$ |
| 2 | 5 | $$$k = 2$$$ |
| 3 | 5 | все $$$a_i$$$ равны $$$0$$$ |
| 4 | 10 | $$$n, k \le 300$$$ |
| 5 | 15 | $$$n, k \le 3000$$$ |
| 6 | 20 | $$$n \le 3000$$$ |
| 7 | 10 | Каждый компьютер соединён кабелем с не более, чем двумя другими компьютерами |
| 8 | 20 | $$$n \le 10^5$$$ |
| 9 | 10 | Без дополнительных ограничений |
4 3 0 0 1 2 1 2 2 3 2 4
2
4 3 1 0 0 0 1 2 2 3 2 4
8
4 1000000000 0 2 2 0 1 2 2 3 3 4
0
В первом примере на компьютерах $$$3$$$ и $$$4$$$ уже определены законопроекты $$$1$$$ и $$$2$$$, поэтому для компьютера $$$2$$$ есть только один возможный законопроект: $$$3$$$. А для компьютера $$$1$$$ можно выбрать два законопроекта ($$$1$$$ и $$$2$$$), поэтому общее число способов равно $$$2$$$.
В третьем примере на двух соседних компьютерах $$$2$$$ и $$$3$$$ уже определен один и тот же законопроект $$$2$$$. Следовательно, никакой план заведомо не может удовлетворять всем ограничениям.