Daniyar Zakarin


Есеп №1. 

Есеп А. Мейіз торт

Уақытка қойылған шектеу:
1 second
Жадқа қойылған шектеу:
256 megabytes

Имаш Димашқа мейіз тортын сыйлады. Тортты әрбір ұяшығында мейізі бар немесе жоқ квадрат тор ретінде көрсетуге болады. Димаш мейізді жақсы көрмейді және мейізі бар ұяшықты кесіп тастап отырды. Осыдан кейін ол әрбір ұяшыққа ол өзі жататындай және мейізі жоқ ең үлкен квадрат бөлігінің өлшемін $a$ массивіне жазып қойды. Бірақ ол тортты кесіп отырып ол басында қандай болғанын ұмытып кетті. Димашқа $a$ массиві бойынша торттың қандай болғанын тауып беріңіз.
Оқу форматы
Бірінші жолда $n$ натурал саны — торттың өлшемі берілген $(1 <= n <= 100)$. Келесі $n$ жолда $n$ саннан — $a$ массиві берілген. $a$ массиві дұрыс және әрбір тестке жауап бар екеніне кепіл беріледі.
Жазу форматы
Торттың сипаттамасы ретінде $n$x$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 )
комментарий/решение(12) олимпиада
Есеп №2. 

Есеп А. Мейіз торт

Уақытка қойылған шектеу:
1 second
Жадқа қойылған шектеу:
256 megabytes

Имаш Димашқа мейіз тортын сыйлады. Тортты әрбір ұяшығында мейізі бар немесе жоқ квадрат тор ретінде көрсетуге болады. Димаш мейізді жақсы көрмейді және мейізі бар ұяшықты кесіп тастап отырды. Осыдан кейін ол әрбір ұяшыққа ол өзі жататындай және мейізі жоқ ең үлкен квадрат бөлігінің өлшемін $a$ массивіне жазып қойды. Бірақ ол тортты кесіп отырып ол басында қандай болғанын ұмытып кетті. Димашқа $a$ массиві бойынша торттың қандай болғанын тауып беріңіз.
Оқу форматы
Бірінші жолда $n$ натурал саны — торттың өлшемі берілген $(1 <= n <= 100)$. Келесі $n$ жолда $n$ саннан — $a$ массиві берілген. $a$ массиві дұрыс және әрбір тестке жауап бар екеніне кепіл беріледі.
Жазу форматы
Торттың сипаттамасы ретінде $n$x$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 )
комментарий/решение(12) олимпиада
Есеп №3. 

Есеп B. Теңдеу

Уақытка қойылған шектеу:
1 second
Жадқа қойылған шектеу:
256 megabytes

$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. Aibar

Ограничение по времени:
1 second
Ограничение по памяти:
256 megabytes

Айбар жаңа бизнес-жоспарды ойлап тапты - құбырларды шырынға ораудан бөлек сату. Ол өзінің жоспарын өте жарқын деп есептегендіктен, ол өте бай болатынын елестете бастады. Ол тіпті байлығының өлшемін ойлап тапты - гуглионер. Бірақ Айбар өз елінің ақшаларын қолданып төлей алмайтын сомма бар болу мүмкіндігінен қатты қорқып кетті. Айбардың елінде ақшаның $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. Aibar

Ограничение по времени:
1 second
Ограничение по памяти:
256 megabytes

Айбар жаңа бизнес-жоспарды ойлап тапты - құбырларды шырынға ораудан бөлек сату. Ол өзінің жоспарын өте жарқын деп есептегендіктен, ол өте бай болатынын елестете бастады. Ол тіпті байлығының өлшемін ойлап тапты - гуглионер. Бірақ Айбар өз елінің ақшаларын қолданып төлей алмайтын сомма бар болу мүмкіндігінен қатты қорқып кетті. Айбардың елінде ақшаның $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 second
Ограничение по памяти:
256 megabytes

<<КазЖелУгЗол>> компаниясы пайдалы қазбаларды өндіру бойынша ірі ауқымды жоспар дайындауда. Компания $n$ кен орындарын зерттеу үшін геолог Асемді жалдады. Компания тізіміндегі $i$-ші кен орнының күтілетін өндіру көлемін Асем $c_i$-ға бағалады. Кен орындарының жанында қойма салу қажет болғандықтан, өндіру жұмыстары тізімде қатар орналасқан кен орындарында өтеді деп шешілді. Сонымен бірге, компанияның қаржылық талдау бөлімі $f_k(l, r)$-ді $c_l, c_{l + 1}, ..., c_r$ сандары арасындағы мәнінің кемуі бойынша $k$-ші санға тең деп шешті. Егер $l$-дан $r$-ға дейінгі кесіндіде $k$-дан кем сан болса, $f_k(l, r)$ мәні нөлге тең болады. Компания директоры қандай да бір $k$ үшін $S = \sum_{1 <= l <= r <= n}f_k(l, r)$ мәнін білгісі келді (барлық $(l, r)$ кесінділері үшін $f_k(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 )
комментарий/решение олимпиада