Daniyar Zakarin

Задача №1.

Задача 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

Вход

Ответ

( Daniyar Zakarin )
комментарий/решение(13) олимпиада

Задача №2.

Задача 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

Вход

Ответ

( Daniyar Zakarin )
комментарий/решение(13) олимпиада

Задача №3.

Задача 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$ ).

Пример:

Вход

Ответ

5 4 6 1 2

( Daniyar Zakarin )
комментарий/решение(6) олимпиада

Задача №4.

Задача 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

( Daniyar Zakarin )
комментарий/решение(8) олимпиада

Задача №5.

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

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

$n$ видов купюр

Формат входного файла

В первой строке записано одно целое число

$n$ (

$1 <= n <= 100$ ). Во второй строке массив

$a$ - типы купюр в возрастающем порядке(

$1 <= a_i <= 10^6$ ).

Формат выходного файла

$1 <= x <= 10^6$ ).

Примеры:

Вход

4
1 2 3 4

Ответ

Good!

Вход

3
2 4 5

Ответ

Sorry Aibar 3

( Daniyar Zakarin )
комментарий/решение(8) олимпиада

Задача №6.

Задача A. Геологическое исследование

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Компания <<КазЖелУгЗол>> готовит крупномаштабный-план по добыче полезных ископаемых. Компания наняла геолога Асем для исследования

$n$ месторождений. Для

$i$ -го месторождения из списка компании Асем определила оценку

$c_i$ -- ожидаемый объем добычи. Поскольку необходимо построить склад возле месторождений, было решено что работа по добыче будет проходить в последовательных месторождениях из списка. Тем временем отдел финансовой аналитики компании разработал оценку плана

$f_k(l, r)$ равную

$k$ -му по убыванию значению среди чисел

$c_l, c_{l + 1}, ..., c_r$ . Если в отрезке от

$l$ до

$r$ менее

$k$ чисел, значение

$f_k(l, r)$ равно нулю. Директору компании стало интересно, чему равно значение

$S = \sum_{1 <= l <= r <= n}f_k(l, r)$ для какого то

$k$ (суммарное значение

$f_k(l, r)$ по всем отрезкам

$(l, r)$ ). Асем уверенна в корректности значений

$c_i$ . Помогите написать программу для эффективного подсчета значения

$S$ .

Формат входного файла

В первой строке даны два числа

$n$ и

$k$ (

$1 <= n <= 10^5, 1 <= k <= min(n, 500)$ ). Во второй строке даны

$n$ чисел

$c_1, c_2, ..., c_n$ -- оценки месторождений(

$1 <= c_i <= 10^7$ ).

Формат выходного файла

Выведите одно число

$S$ .

Система оценки

Данная задача содержит

$9$ подзадач, в которых выполняются следующие ограничения:

Тесты из условия. Оценивается в $0$ баллов.
$n <= 100$ . Оценивается в $11$ баллов.
$n <= 5000$ , $k = 1$ . Оценивается в $11$ баллов.
$n <= 5000$ . Оценивается в $12$ баллов.
$n <= 10^5$ , $k = 1$ . Оценивается в $15$ балла.
$n <= 10^5$ , $k = 2$ . Оценивается в $10$ баллов.
$n <= 10^5$ , $a_i <= 2$ . Оценивается в $9$ баллов.
$n <= 10^5$ , $a_i <= 500$ . Оценивается в $14$ баллов.
Исходные условия задачи. Оценивается в $18$ баллов.

Примеры:

Вход

5 3
1 2 3 2 1

Ответ

Вход

7 4
1 1 1 1 1 1 1

Ответ

Замечание

В первом примере

$f_3(1, 3) = f_3(3, 5)= 1, f_3(1, 4) = f_3(1, 5) = f_3(2, 4) = f_3(2, 5) = 2$ . ( Daniyar Zakarin )
комментарий/решение олимпиада