ГЖО 7-8 класс 2019 год


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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Имаш подарил Димашу торт с изюмом. Торт можно представить в виде квадратной таблицы где в каждой ячейке либо есть изюм либо его нет. Проблема в том что Димаш не любит изюм поэтому он вырезает квадратные куски торта без изюма. Во время планировки он посчитал для каждой ячейки таблицы максимальный квадратный кусок без изюма в котором он лежит и записал эти значение в таблицу $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

комментарий/решение(8) Проверить мое решение

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

"Что умеют восьмиклассники? Ну наверное решать уравнения…" Дано целое положительное число $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

комментарий/решение(5) Проверить мое решение

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

Ограничение по времени:
3 секунды
Ограничение по памяти:
512 мегабайт

Дан массив $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

комментарий/решение(6) Проверить мое решение

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Айбай и Абар играют игру. У них есть два массива целых положительных чисел $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

комментарий/решение(1) Проверить мое решение

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Айбар придумал новый бизнес план - продавать трубочки для соков отдельно от упаковки. Поскольку он считает свой план супер гениальным, он начал представлять как будет очень богатым. Он даже придумал меру своей богатости - гуглионер. Но Айбар сильно испугался, а вдруг есть такая целая сумма которую он не способен оплатить используя банкноты своей страны. В стране Айбара есть $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

комментарий/решение(5) Проверить мое решение

Задача F. UCL Fantasy

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Недавно Данияр начал увлекаться футболом. И сразу начал играть 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 будет капитаном и состав будет таким:


комментарий/решение(2) Проверить мое решение

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

$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

комментарий/решение(1) Проверить мое решение

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Абая есть натуральное число $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 операции.

комментарий/решение(6) Проверить мое решение

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

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

У Тимы есть $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

комментарий/решение(3) Проверить мое решение