Aibar Kuanyshbay

Есеп №1.

Есеп D. Айбардың таңдауы

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

1 секунда

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

256 мегабайт

Айбардың ұзындықтары $n$ болатын $A$ және $B$ массивтары бар. Әр бір $i$ үшін, $(1 <= i <= n)$, Айбар не $A_i$, не $B_i$ таңдамақшы. Ол таңдалған $A_i$-лардың саммасы мен, барлық таңдалған $B_j$ үшін соммаларының көбейтіндісін ұлғайтпақшы. Айбарға ең үлкен мәнді табуға көмектесіңіз. Ең үлкен мән $10^9$ санынан аспайтынына кепілдік беріледі.

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

Ең бірінші жолда $n$ $(2 <= n <= 1000)$ саны еңгізілген. Екінші жолда $n$ бүтін сан $A_1, A_2, A_3,...A_n$ $(1 <= A_i <= 10^9)$ еңгізілген. Үшінші жолда $n$ бүтін сан $B_1, B_2, B_3,...B_n$ $(1 <= B_i <= 10^9)$ еңгізілген.

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

Есептің жауабын шығарыңыз.

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

Есеп алты бөлімнен тұрады:

$2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 1$. $8$ ұпайға есептеледі.
$2 <=q n <=q 15, 1 <=q A_i, B_i <=q 10^9$. $9$ ұпайға есептеледі.
$2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 10^9$ и $A_1 <= A_2 <= ... <= A_n$, $B_1 \ge B_2 \ge ... \ge B_n$ . $10$ ұпайға есептеледі.
$2 <=q n <=q 1000$, $A_i=B_i$ барлық $i$ үшін, барлық $A_i$ соммасы $10^5$ аспайды. $18$ ұпайға есептеледі.
$2 <=q n <=q 100$, барлық $A_i$ соммасы 300 аспайды, барлық $B_i$ соммасы $300$ аспайды. $25$ ұпайға есептеледі.
$2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 10^9$. $30$ ұпайға есептеледі.

Примеры:

Вход

5
1 4 3 2 5
5 2 2 4 1

Ответ

Вход

2
5 7
3 5

Ответ

Вход

7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Ответ

Замечание

Бірінші мысалда Айбар $A$ массивынен $2, 3, 5$ орнынағы элементтерді алып, $B$ массивынан $1, 4$ орындарындағы элементтерді алса, жауап осындай болады: $(4 + 3 + 5) * (5 + 4)=108$. ( Aibar Kuanyshbay )
комментарий/решение(1) олимпиада

Есеп №2.

Есеп C. Жұп сан

Уақытка қойылған шектеу:

1 second

Жадқа қойылған шектеу:

256 megabytes

Айбарда $n$ бүтін сан бар. Ол суммасы максимал және жұп болатындай, кейбір сандарды таңдағысы келеді. Максимал сумманы табыңыз. Айбар бірде-бір санды таңдамаса, суммасы $0$-ге тең болады.

Оқу форматы

Бірінші жолда $n$ саны берілген. Келесі жолда $n$ бүтін сан жазылған. Олар абсолют мәні бойынша $10^9$-дан аспайды.

Жазу форматы

Есептің жауабын шығарыңыз.

Примеры:

Оқу

3
1 2 3

Жауап

Оқу

4
1 3 5 -3

Жауап

( Aibar Kuanyshbay )
комментарий/решение(2) олимпиада

Есеп №3.

Задача B. Жұп сандар

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

1 second

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

256 megabytes

Сізге $L$ және $R$ сандары беріледі. $L$-дан $R$-ға дейін барлық цифралары ондық санау жүйесінде жұп болатын сандардың санын табу керек. Есептің жауабын табыңыз.

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

Бірінші жолда екі натурал $L$ және $R$ $(1 <= L <= R <= 10^{10})$ сандары берілген.

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

Бірінші жолда есептің жауабын — бір бүтін санды шығарыңыз.

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

Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

$1 <= L <= R <= 10^2$. 1-2 нөмердегі тесттер.
$1 <= L <= R <= 10^6$. 3-4 нөмердегі тесттер.
$1 <= L <= R <= 10^{10}$. 5-10 нөмердегі тесттер

Пример:

Вход

3 10

Ответ

( Aibar Kuanyshbay )
комментарий/решение(7) олимпиада

Есеп №4.

Задача C. Мейрамхана

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

1 second

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

256 megabytes

Мейрамханада $n$ даяршы бар. Олар $1$-ден $n$-ға дейін нөмірленген. Үстелде $m$ стақан тұр. Олар $1$-ден $m$-ге дейін нөмірленген. Бастапқыда барлық стақан бос. Әр даяршы бірнеше стақанға сусын құюы керек. $i$-ші даяршы $l_i$-ден $r_i$-ге дейінгі стақандарға $x_i$ миллилитр сусын құюы керек. Бір даяршы ұйықтап қалып, стақандарға сусын құюды ұмытып кетті. Одан басқа барлық даяршылар тапсырмаларын орындады. Сізге әр стақандағы сусын мөлшері берілген. Сізге ұйықтап қалу мүмкін даяршылардың тізімін табу керек.

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

Бірінші жолда $n$ және $m$ $(1 <= n, m <= 10^5)$ — даяршылар саны және стақандар саны берілген. Келесі $n$ жолдарда $l_i$, $r_i$ және $x_i$ $(1 <= l_i <= r_i <= m$, $1 <= x_i <= 10^3)$ үш сандар берілген. Келесі жолда $m$ бүтін сандар берілген, $a_1$, $a_2$, $\dots$, $a_m$, мұнда $a_i$ $i$-ші стақандағы сусынның миллилитр санын көрсетеді.

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

Ұйықтап қалу мүмкін даяршылардың нөмірлерін өсу ретінде шығарыңыз.

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

Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

$1 <= n, m <= 100$. 1-2 нөмердегі тесттер.
$1 <= n, m <= 3000$. 3-5 нөмердегі тесттер.
$1 <= n, m <= 10^5$. 6-10 нөмердегі тесттер

Пример:

Вход

Ответ

1 3

( Aibar Kuanyshbay )
комментарий/решение(7) олимпиада

Есеп №5.

Задача D. Бөлгіштер

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

1 second

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

256 megabytes

Сізге $n$ бүтін саны берілген. $1$-ден $n$-ге дейін бөлгіштердің саны жұп болатын сандардың санын табыңыз.

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

Бірінші жолда бүтін $n$ $(1 <= n <= 10^9)$ саны берілген.

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

Есептің жауабын шығарыңыз.

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

Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

$1 <= n <= 1000$. 1-6 нөмердегі тесттер.
$1 <= n <= 10^5$. 7-8 нөмердегі тесттер.
$1 <= n <= 10^9$. 9-10 нөмердегі тесттер

Пример:

Вход

Ответ

Замечание

Мысалды:

$1$ санының бөлгіштері: $1$. Бөлгіштерінің саны $1$ - тақ.
$2$ санының бөлгіштері: $1, 2$. Бөлгіштерінің саны $2$ - жұп.
$3$ санының бөлгіштері: $1, 3$. Бөлгіштерінің саны $2$ - жұп.
$4$ санының бөлгіштері: $1, 2, 4$. Бөлгіштерінің саны $3$ - тақ.
$5$ санының бөлгіштері: $1, 5$. Бөлгіштерінің саны $2$ - жұп.
$6$ санының бөлгіштері: $1, 2, 3, 6$. Бөлгіштерінің саны $4$ - жұп.
$7$ санының бөлгіштері: $1, 7$. Бөлгіштерінің саны $2$ - жұп.
$8$ санының бөлгіштері: $1, 2, 4, 8$. Бөлгіштерінің саны $4$ - жұп.
$9$ санының бөлгіштері: $1, 3, 9$. Бөлгіштерінің саны $3$ - тақ.
$10$ санының бөлгіштері: $1, 2, 5, 10$. Бөлгіштерінің саны $4$ - жұп.

( Aibar Kuanyshbay )
комментарий/решение(11) олимпиада

Есеп №6.

Задача E. Екінші максимум

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

1 second

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

256 megabytes

Сізге $a_1$, $a_2$,..., $a_n$ $n$ саны беріледі. $2$-ден $n$-ге дейін әрбір $k$ үшін $a$ массивінің алғашқы $k$ санының ішіндегі екінші максимумды табыңыз.

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

Бірінші жолда $n$ $(1 <= n <= 10^5)$ саны берілген. Екінші жолда $a_1$, $a_2$,..., $a_n$ $n$ бүтін саны берілген $(1 <= a_i <= 10^9)$.

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

$2$-ден $n$-ге дейін әрбір $k$ үшін есептің жауабын шығарыңыз.

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

Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

$1 <= n <= 100$. 1-3 нөмердегі тесттер.
$1 <= n <= 5000$. 4-6 нөмердегі тесттер.
$1 <= n <= 10^5$. 7-10 нөмердегі тесттер

Пример:

Вход

7
1 2 3 3 7 5 6

Ответ

1 2 3 3 5 6

Замечание

Мысалда:

$k=2$. Алғашқы $k$ сан $\underline{1}, 2$. Жауабы - $1$
$k=3$. Алғашқы $k$ сан $1, \underline{2}, 3$. Жауабы - $2$
$k=4$. Алғашқы $k$ сан $1, 2, \underline{3}, 3$. Жауабы - $3$
$k=5$. Алғашқы $k$ сан $1, 2, \underline{3}, 3, 7$. Жауабы - $3$
$k=6$. Алғашқы $k$ сан $1, 2, 3, 3, 7, \underline{5}$. Жауабы - $5$
$k=7$. Алғашқы $k$ сан $1, 2, 3, 3, 7, 5, \underline{6}$. Жауабы - $6$

( Aibar Kuanyshbay )
комментарий/решение(11) олимпиада

Есеп №7.

Задача F. Үштіктер

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

1 second

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

256 megabytes

Сізге ұзындығы $n$ болатын, бүтін сандардан тұратын $a$ массиві берілген. Массивтегі барлық сандар әртүрлі. Сізге $i \ne j$, $i \ne k$, $j \ne k$ және $a_i*a_j=a_k^2$ орындалатын $i$, $j$, $k$ үштіктер санын табу керек.

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

Бірінші жолда $n$ $(3 <= n <= 10^5)$ бүтін саны берілген. Келесі жолда $a_1$, $a_2$, $\dots$, $a_n$ $(1 <= a_i <= 3 * 10^5)$ болатын $a$ массиві берілген.

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

Есептің жауабын шығарыңыз.

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

Бұл есеп $10$ тесттан тұрады. Әр тест $10$ баллға бағаланады:

$n <= 100$, $1 <= a_i <= 500$. 1-3 нөмердегі тесттер.
$n <= 5000$, $1 <= a_i <= 10000$. 4-6 нөмердегі тесттер.
$n <= 10^5$, $1 <= a_i <= 300000$. 7-10 нөмердегі тесттер

Пример:

Вход

6
6 3 9 4 12 27

Ответ

( Aibar Kuanyshbay )
комментарий/решение(2) олимпиада

Есеп №8.

Задача D. Массивті бөлу

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

1 second

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

256 megabytes

Тиманың үш інісі бар: Батыр, Димаш және Есмахан. Тима оларға көңіл көтеру үшін размеры $n$ болатын $a$ массивін беруге шешті. Әрбір сан бір бөлікте болатындай, Тима массивті үш бөлікке бөліп, інілеріне таратпақшы. Бөліктер бос болмау керек. Бір бөліктің барлық сандары массивте қатар тұруы керек. $A$ - бірінші бөліктегі сандар сомасы, $B$ - екінші бөліктегі сандар сомасы, $C$ - үшінші бөліктегі сандар сомасы болсын. Інілері төбелеспеуі үшін, Тима max(A, B, C) - мин(A, B, C) мәні аз болғанын қалайды. Ең аз max(A, B, C) - min(A, B, C) мәнін табыңыз.

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

Бірінші жолда бір бүтін $n$ $(3 <= n <= 3 * 10^5)$ саны берілген. Екінші жолда $n$ бүтін сан $a_1$, $a_2$, $\dots$, $a_n$ $(0 <= a_i <= 10^5)$ сандары берілген.

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

Есептің жауабын — ең аз max(A, B, C) - min(A, B, C) мәнін шығарыңыз.

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

Есеп 20 тесттен тұрады, әр тест 5 баллға бағаланады:

$n <= 10^2$. Тесты 1 -- 4
$n <= 5 * 10^3$. Тесты 5 -- 8
$a_i <= 1$. Тесты 9 -- 12
$n <= 3 * 10^5$. Тесты 13 -- 20

Пример:

Вход

7
4 1 2 3 1 3 2

Ответ

Замечание

Үлгідегі бөліністердің бір түрі: 4 1 | 2 3 1 | 3 2 Және 4 1 | 2 3 | 1 3 2 бөлінісі дұрыс ( Aibar Kuanyshbay )
комментарий/решение(4) олимпиада

Есеп №9.

Задача B. Қуанышты сандар

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

1 second

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

256 megabytes

Натурал сан $25$-ке аяқталса және толық квадрат болса, қуанышты деп саналады. Егер сан басқа бүтін санның квадраты болса, онда ол сан толық квадрат болып саналады. Мысалы, 25, 225, 625 қуанышты, ал 125,49,325 - жоқ. Сізге $k$ саны берілген. $k$-ші қуанышты санды табыңыз.

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

Жалғыз жолда бір бүтін сан $k$ ($1 <= k <= 10^8$) берілген.

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

Жалғыз бүтін сан — $k$-ші қуанышты санды шығарыңыз.

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

Есеп 4 бөлімнен және 10 тесттен тұрады, әр тест 10 баллға бағаланады:

$1 <= k <= 10$. Тест 1 -- 4
$1 <= k <= 100$. Тест 5 -- 6
$1 <= k <= 5000$. Тест 7 -- 8
$1 <= k <= 10^8$. Тест 9 -- 10

Пример:

Вход

Ответ

( Aibar Kuanyshbay )
комментарий/решение(14) олимпиада

Есеп №10.

Есеп B. AB

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

1 second

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

256 megabytes

Сізге 'a' және 'b' әріптерінен тұратын $s$ және $t$ екі сөзі берілген. \textbf {$s$ сөзінде көрші бірдей әріптер жоқ}. Сіз $s$-ке тең $t$-ның ең көп қиылыспайтын ішкі тізбектерін таңдағыңыз келеді. Ішкі тізбек - - - бұл сөзден бірнеше (мүмкін нөл) элементтерін алып тастау арқылы алуға болатын сөз тізбегі. Таңдауға болатын ең көп ішкі тізбектердің санын табыңыз.

Оқу форматы

Бірінші жолда $s$ сөзі берілген ($1 <= |s| <= 4$). $s$ cөзінде көрші бірдей әріптер жоқ екеніне кепілдік беріледі. Екінші жолда $t$ сөзі берілген ($1 <= |t| <= 10^5$).

Жазу форматы

Бір бүтін санды — сіз таңдай алатын ішкі тізбектердің ең көп санын шығарыңыз.

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

Есеп $7$ бөлімнен тұрады:

Есептің шартында берілген тесттер. $0$ ұпайға бағаланады.
$|s| = 1$. $11$ ұпайға бағаланады.
$|s| = 2$. $14$ ұпайға бағаланады.
$|s| = 3$. $20$ ұпайға бағаланады.
$|s| = 4$, $|t| <= 50$. $18$ ұпайға бағаланады.
$|s| = 4$, $|t| <= 300$. $12$ ұпайға бағаланады.
$|s| = 4$, $|t| <= 10^5$. $25$ ұпайға бағаланады.

Примеры:

Вход

ab
abbaba

Ответ

Вход

  
aba
ababaa

Ответ

Түсініктеме

Екінші мысалда {1, 2, 5} және {3, 4, 6} индекстерімен қиылыспайтын екі тізбекті таңдауға болады. ( Aibar Kuanyshbay )
комментарий/решение(1) олимпиада