Задача A. Торт с изюмом

Имаш подарил Димашу торт с изюмом. Торт можно представить в виде квадратной таблицы где в каждой ячейке либо есть изюм либо его нет. Проблема в том что Димаш не любит изюм поэтому он вырезает квадратные куски торта без изюма. Во время планировки он посчитал для каждой ячейки таблицы максимальный квадратный кусок без изюма в котором он лежит и записал эти значение в таблицу $a$. К сожалению во время разрезания он слишком увлекся и испортил торт. Помогите ему восстановить его. В первой строке записано одно целое число $n$ ($1 <= n <= 100$) - размер квадратной таблицы. Далее следуют $n$ строк по $n$ чисел. В $j$-тое число $i + 1$ строке это - $a_{i, j}$. Гарантируется, что таблица $a$ корректна и ей соответствует хотя бы один торт. Выведите $n$ строк по $n$ чисел через пробел - описание торта. В $i$-той строке $j$-тым числом выведите 1 если там есть изюм, в противном случае выведите 0. Вход

2
0 1
1 0

Ответ

1 0 
0 1

Вход

4
2 2 1 1
2 2 0 1
1 0 1 0
0 1 1 1

Ответ

0 0 0 0 
0 0 1 0 
0 1 0 1 
1 0 0 0

Задача B. Уравнение

"Что умеют восьмиклассники? Ну наверное решать уравнения…" Дано целое положительное число $n$. Требуется найти любое решение уравнения $a + b - c * d / e = n$, где $a$, $b$, $c$, $d$, $e$ - различные целые положительные числа. В входных данных записано одно целое положительное число $n$($1 <= n <= 10^9$). Если решений нет выведите $-1$, иначе выведите пять чисел $a$, $b$, $c$, $d$, $e$ - решения уравнения($1 <= a, b, c, d, e <= 10^9$). Вход

6

Ответ

5 4 6 1 2

Задача D. Оптимизировать!

Дан массив $a$ длины $n$ ($a_1, a_2, ..., a_n$). И заданы $q$ запросов. Для каждого запроса задано $l, r$ ($1 <= l <= r <= n$). Вам дан псевдокод его решения, где число $c$ ответ на запрос:

int c = 0

for(int i = l...r)

  c = (c + a[i] + abs(c - a[i])) / 2

print(c).

Это слишком медленно. Так что оптимизируйте это! В первой строке записано одно целое число $n$ ($1 <= n <= 10^6$) — длина массива. Во второй строке записано n целых чисел $a_1, a_2, ..., a_n$ ($1 <= |a_i| <= 10^9$) — сам массив. В третьей строке записано одно число $q$ ($1 <= q <= 10^6$) — количество запросов. В каждой из следующих $q$ строк записано по два целых числа $l$ и $r$ ($1 <= l <= r <= n$), описывающих один запрос. Найди $c$ для каждого запроса. Вход

10
1 6 3 88 2 9 45 78 23 6
5
1 3
4 5
6 10
5 7
2 7

Ответ

6
88
78
45
88

Задача D. Лучшие друзья

Айбай и Абар играют игру. У них есть два массива целых положительных чисел $a$ и $b$. Айбай может взять два соседних числа из массива $a$ и заменить их суммой этих двух чисел. Например : $[2, 4, 1, 7]$ -> $[2, 5, 7]$. Абар может делать то же самое с массивом $b$. Так как они лучшие друзья, то они хотят, чтобы получившиеся массивы были одинаковыми. Но они очень любят большие массивы, поэтому они хотят, чтобы получившиеся массивы были еще и максимальной длины. Найдите максимальную возможную длину получившихся массивов. В первой строке задано целое число $n$ $(1 <= n <= 300000)$ - длина первого массива. Во второй строке задано $n$ целых чисел $a_{1},a_{2},...,a_{n}$ $(0 <= a_{i} <= 10^9)$ - элементы массива $a$. В третьей строке задано целое число $m$ $(1 <= m <= 300000)$ - длина второго массива. В четвертой строке задано $m$ целых чисел $b_{1},b_{2},...,b_{m}$ $(0 <= b_{i} <= 10^9)$ - элементы массива $b$. Выведите одно число — максимальную длину полученных массивов после применения операций к массивам $a$ и $b$ таким образом, что они становятся одинаковыми. Если же не существует способа сделать массивы одинаковыми, выведите -1. Вход

5
11 2 3 5 7
4
11 7 3 7

Ответ

3

Вход

2
1 2
1
100

Ответ

-1

Вход

3
1 2 3
3
1 2 3

Ответ

3

Задача E. Богатый Айбар

Айбар придумал новый бизнес план - продавать трубочки для соков отдельно от упаковки. Поскольку он считает свой план супер гениальным, он начал представлять как будет очень богатым. Он даже придумал меру своей богатости - гуглионер. Но Айбар сильно испугался, а вдруг есть такая целая сумма которую он не способен оплатить используя банкноты своей страны. В стране Айбара есть $n$ видов купюр $a_1, a_2, ..., a_n$. Вам даны виды купюр скажите можно ли получить любую сумму используя купюры этих видов или скажите что это не возможно и выведите любую сумму которую Айбар не способен оплатить. В первой строке записано одно целое число $n$($1 <= n <= 100$). Во второй строке массив $a$ - типы купюр в возрастающем порядке($1 <= a_i <= 10^6$). Если Айбар может собрать любую целую положительную сумму используя эти купюры выведите "Good!"(без кавычек), иначе "Sorry Aibar x"(без кавычек, вместо x - число которое нельзя собрать)($1 <= x <= 10^6$). Вход

4
1 2 3 4

Ответ

Good!

Вход

3
2 4 5

Ответ

Sorry Aibar 3

Задача F. UCL Fantasy

Недавно Данияр начал увлекаться футболом. И сразу начал играть UCL Fantasy. Правила простые, каждый игрок собирает себе команду из 15 игроков(2 вратаря, 5 защитников, 5 полузащитников, 3 нападающих) играющих в Лиге чемпионов УЕФА. Каждый игрок за тур получает какие-то баллы в зависимости как он сыграл. Баллы можно получить за гол, за голевой пас, вратарю за сухую игру, отрицательный балл за удаления и т.д. Перед каждым туром Данияр выбирает состав на тур, состоящий из 11 игроков и среди них выбирает капитана. В составе всегда должен быть ровно один вратарь, и возможны следующие схемы: 5(защитника)-4(полузащитника)-1(нападающий), 5-3-2,5-2-3,4-5-1,4-4-2,4-3-3,3-5-2,3-4-3. Тогда очки Данияра, это будет сумма баллов его состава(11 игроков) + баллы его капитана(т.е баллы капитана удваиваются). Данияр знает баллы всех своих игроков, помогите ему выбрать состав на тур, чтобы максимизировать количество его очков. В 15 строках находятся информация о игроках: $name_i(1 <= |name_i| <= 20)$,$position_i$ и $p_i(-10 <= p_i <= 100)$ — имя или фамилия игрока, позиция в которой он играет и его баллы за тур. Гарантируется, что 2 вратаря, 5 защитников, 5 полузащитников, 3 нападающих. $position_i$ может быть одной из : GK — вратарь, DF — защитник, MF — полузащитник, FW — нападающий. Выведите, максимальное количество очков, которые может получить Данияр. Вход

Messi FW 10
Pique DF 6
Tadic FW 2
Coutinho MF 3
Stegen GK 7
Salah MF 2
Ziyech MF 6
Onana GK 6
Beek MF 8
Son MF 0
Alba DF 8
Suarez FW 8
Blind DF 6
Ligt DF 6
Roberto DF 6

Ответ

84

Messi будет капитаном и состав будет таким:

Задача G. Камень… Ножницы… Бумага...

$N + 1$ роботов будут участвовать в турнире по камень-ножницы-бумага и один из роботов ваш. В этом турнире каждый робот использует программу, представляющую собой серию ходов, каждый из которых должен быть одним из следующих: 'R'(камень), 'P'(бумага) или 'S'(ножницы). Бумага побеждает камень, камень побеждает ножницы, ножницы побеждает бумагу. Когда играет два робота, побеждает тот, кто первым сделал выигрышный ход. В начале каждый робот делает первый ход своей программы. Если ходы у них различны, один из них побеждает по правилам игры. Если ходы одинаковые, каждый робот выполняет следующий ход своей программы и т.д. Когда робот сделал последний ход своей программы и ему необходимо сделать следующий ход, то он делает первый ход своей программы. Если игра идет бесконечно долго, объявляется ничья. Вы случайном образом узнали программы своих $N$ соперников. Сделайте программу для своего робота, чтобы ваш робот мог победить любого другого робота. В первой строке находится одно целое число $N(1 <= N <= 100)$ — количество ваших соперников. В следующих $N$ строках находятся по одной строке $C_i(1 <= |C_i| <= 100)$ — программы ваших соперников. $C_i$ состоит из букв 'R', 'P', 'S'. Если не существует победной программы для вашего робота, выведите "IMPOSSIBLE". Иначе, выведите победную программу для своего робота. Длина вашей программы не должна превосходить $10^4$. Гарантируется, что если ответ существует, то существует ответ длиной не более $10^4$. Если существует несколько ответов, выведите любой из них. Вход

3
R
S
P

Ответ

IMPOSSIBLE

Вход

1
RP

Ответ

P

Вход

2
RP
S

Ответ

RPP

Задача H. Легкая математика

У Абая есть натуральное число $n$. Он может делать с этим числом 2 вида операций: 1) Умножить $n$ на $x$ ($x$ — любое натуральное число) 2) Заменить $n$ на $\sqrt{n}$ (в этом случае $\sqrt{n}$ должно быть целым числом) Обе операции можно делать любое количество раз. Помогите Абаю узнать, какое минимальное число можно получить, выполняя данные операции. Также Абая интересует, какое минимальное количество операций нужно проделать, чтобы получить минимальное число. В единственной строке дано натуральное число $n$ ($1 <= n <= 10^6$). Выведите два числа: минимальное число, которое можно получить, затем минимальное количество операций для получения этого числа. Вход

20

Ответ

10 2

Вход

5184

Ответ

6 4

Ответ для первого примера: 20 --> $20 \times 5 = 100$ --> $\sqrt{100} = 10$ — в итоге 2 операции. Ответ для второго примера: 5184 --> $\sqrt{5184} = 72$ --> $72 \times 18 = 1296$ --> $\sqrt{1296} = 36$ --> $\sqrt{36} = 6$ — в итоге 4 операции.

Задача I. Контесты

У Тимы есть $n$ задач пронумерованных от $1$ до $n$. Сложность задачи с номером $i$ равна $a_i$. Однажды он решил сделать несколько контестов. Один контест состоит из 4 задач разной сложности. Разумеется одну задачу можно использовать только на одном контесте. Помогите ему составить максимальное количество контестов. В первой строке одно число $n$ $(1 <= n <= 300000)$ - количество задач. Во второй строке $n$ целых чисел $a_1, a_2,... a_n$ $(1 <= a_i <= 300000)$ - сложность задач. В первой строке одно число $k$ $(0 <= k <= n / 4)$- максимальное количество контестов. В следующих $k$ строках по $4$ числа $i_1,\ i_2,\ i_3,\ i_4$ - номера задач контеста. Если возможных ответов несколько, выведите любой из них. Вход

5
1 1 2 3 4

Ответ

1
2 3 4 5

Вход

10
3 1 4 5 3 2 4 3 5 1

Ответ

2
8 10 7 9
5 2 6 3