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
Вход 
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
( 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
Вход 
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
( 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$).
Пример:
Вход 
6
Ответ
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$ видов купюр $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) олимпиада
Задача №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$ подзадач, в которых выполняются следующие ограничения:
  1. Тесты из условия. Оценивается в $0$ баллов.
  2. $n <= 100$. Оценивается в $11$ баллов.
  3. $n <= 5000$, $k = 1$. Оценивается в $11$ баллов.
  4. $n <= 5000$. Оценивается в $12$ баллов.
  5. $n <= 10^5$, $k = 1$. Оценивается в $15$ балла.
  6. $n <= 10^5$, $k = 2$. Оценивается в $10$ баллов.
  7. $n <= 10^5$, $a_i <= 2$. Оценивается в $9$ баллов.
  8. $n <= 10^5$, $a_i <= 500$. Оценивается в $14$ баллов.
  9. Исходные условия задачи. Оценивается в $18$ баллов.
Примеры:
Вход 
5 3
1 2 3 2 1
Ответ
10
Вход 
7 4
1 1 1 1 1 1 1
Ответ
10
Замечание
В первом примере $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 )
комментарий/решение олимпиада