Batyr Sardarbekov

Есеп №1.

Есеп B. Айбай және Абар

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

1 second

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

256 megabytes

Айбай Абарға сыйлық ретінде $n$ балық сыйлағысы келді. Сыйлық әдемі болуы үшін оларды топтарға бөлу керек. Бірақ, Айбай екі топта бірдей балық саны болғанын қаламайды. Айбай $n$ балықты максимал қанша топқа бөле алады?

Оқу форматы

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

Жазу форматы

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

Мысалдар:

Оқу

Жауап

Оқу

Жауап

Оқу

Жауап

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

Есеп №2.

Есеп D. Жан достар

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

1 second

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

256 megabytes

Айбай мен Абар ойын ойнап отыр. Оларда $a$ және $b$ оң бүтін сандардың екі массиві бар. Айбай $a$ массивіндегі екі көршілес сандарды алып, оларды сол екі санның қосындысымен ауыстыра алады. Мысалы: $[2, 4, 1, 7]$ -> $[2, 5, 7]$. Абар сондай операцияны $b$ массивімен жасай алады. Олар жақсы достар болғандықтан, нәтижесінде алынған массивтер бірдей болуын қалайды. Бірақ, олар үлкен массивтерді өте жақсы көреді, сондықтан алынған массивтердің ұзын болуын қалайды. Алынған массивтердің барынша мүмкін ұзындығын табыңыз.

Оқу форматы

Бірінші жолда $n$ бүтін саны бар $(1 \ le n <= 300000)$ — бірінші массивтің ұзындығы. Екінші жолда $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$ массивінің элементтері.

Жазу форматы

Бір санды — нәтижеcінде алынған массивтердің максималды ұзындығын шығарыңыз. Егер массивтерді бірдей жасау мүмкін болмаса, $-1$ шығарыңыз.

Мысалдар:

Оқу

Жауап

Оқу

Жауап

-1

Оқу

Жауап

( Batyr Sardarbekov )
комментарий/решение(3) олимпиада

Есеп №3.

Есеп I. Контесттер

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

1 second

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

256 megabytes

Тиманың $ 1 $-ден $n$-ға дейін нөмірленген $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

( Batyr Sardarbekov )
комментарий/решение(3) олимпиада

Есеп №4.

Есеп I. Контесттер

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

1 second

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

256 megabytes

Оқу форматы

Жазу форматы

Мысалдар:

Оқу

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

( Batyr Sardarbekov )
комментарий/решение(3) олимпиада

Есеп №5.

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

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

1 second

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

256 megabytes

Ара тәрізді бір циклдан тұратын 1ден $n$-ге дейін сандардың орын ауыстыруы болатып $p$ массивын табыңыз. Орын ауыстыру бір циклдан тұрады деп саналады, егер $i$ - $p_i$ деген қырлармен граф құрсақ, ол графта бір ғана компонента болса. $p$ ара тәрізді орын ауыстыру, егер оның элементтері кезекпен өсіп, түсіп отырса.($p_1 < p_2 > p_3 < p_4 ...$ немесе $p_1 > p_2 < p_3 > p_4 ...$)

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

Бір бүтін сан $n$ берілген.

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

Есеп шартына келетін кез келген сандарды шығарыңыз.

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

Есеп $10$ тесттен тұрады, әр тест $10$ ұпайға бағаланады.

$n = 4$
$n = 5$
$n = 10$
$n = 11$
$n = 20$
$n = 21$
$n = 2019$
$n = 2020$
$n = 12345$
$n = 123456$

Пример:

Вход

Ответ

3 1 4 2

( Batyr Sardarbekov )
комментарий/решение(15) олимпиада

Есеп №6.

Задача E. Есмахан және стартап

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

1 second

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

256 megabytes

Есмахан - морж өсіру бойынша стартап бастады. Ол $n-1$ қызметкеріді жалдады. Есмахан - нөмірі $1$ қызметкер, қалғандар $2$-ден $n$-ге дейін нөмірленген. Әр қызметкерде бір тікелей жетекші $p_i$ бар. Есмаханның бастығы жоқ. $p_i$ мәндері данақ құрайды. Енді Есмахан оларға төлеуі керек. $i$ қызметкері $a_i$ теңге алғысы келеді. $i$ қызметкері $b_i$ теңге берілсін, сонда оның наразылығы $|a_i - b_i|$ болады. Есмаханның қағидасы бар - \textbf {әр қызметкер өзінің бағыныштыларына қарағанда көбірек алуы керек}. Жалақыны қызметкерлердің жалпы наразылық минималды болатындай етіп бөлу керек.

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

Бірінші жолда бір бүтін сан $n$ $(1 <= n <= 200000)$. Екінші жолда $n - 1$ бүтін сан $p_2, p_3, ... p_n$ $(1 <= p_i <= i - 1)$ - бұл бастықтардың нөмірлері. Үшінші жолда $n$ бүтін сан $a_1, a_2, ... a_n$ $(1 <= a_i <= 10^9)$ - жұмысшылардың күтуі.

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

Бір бүтін санды басып шығарыңыз - қызметкерлердің жалпы наразылығы.

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

Есеп $25$ тесттен тұрады, әр тест $4$ ұпайға бағаланады.

Берілген тест.
$1 <= n <= 1000$, $1 <= a_i <= 1000$ әр $1 <= i <= n$, әр қызметкерде бағыныштылар саны бірден көп емес| 2 тест.
$1 <= n <= 1000$, $1 <= a_i <= 1000$ әр $1 <= i <= n$ | 2 тест.
$1 <= n <= 1000$, әр қызметкерде бағыныштылар саны бірден көп емес | 2 тест.
$1 <= n <= 1000$ | 3 тест.
$1 <= n <= 200000$, әр қызметкерде бағыныштылар саны бірден көп емес | 5 тест.
$1 <= n <= 200000$ | 10 тест.

Пример:

Вход

7
1 2 1 1 5 6
1 2 3 1 4 3 3

Ответ

Замечание

Мысалда $b={5, 4, 3, 1, 4, 3, 2}$ ( Batyr Sardarbekov )
комментарий/решение(3) олимпиада

Есеп №7.

Задача C. ICPC

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

1 second

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

256 megabytes

Бағдарламаудан ICPC әлем чемпионатында жаңа ереже: енді әр команда 3 компьютермен қолдана алады. Осы ереже Қазақстанның үздік командаларының біріне қалай әсер еткенің көрейік. Кирилл, Айбар және Сұлтан жарысты бастады. Жарыста $n$ есеп, ұзақтылығы 5 сағат. Олар әр есепті орындауға кететін уақытты алдын-ала есептеді. Кирилл $i$-ші нөмердегі есепті $a_i$ минутта шығарады. Ал Айбар $b_i$, Сұлтан $c_i$ минутта шығарады. Жарыста барынша көп есепті, аз айыпқұлмен шығару қажет. Айыпкұл есептердің шығарылған уақыттарының қосындысы ретінде саналады. Мысалы, егер команда бірінші есепті $5$ші минутта, ал екінші есепті $10$шы минутта шығарса айыпқұл $5 + 10 = 15$ болады. Сізге команда ең көп неше есеп шығара алады, және сонша есеп шығару үшін ең аз дегенде қанша айыпқұл кететінің табу қажет.

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

Бірінші жолда бір бүтін сан $n$ ($1 <= n <= 10$) - жарыстағы есептердің саны. Келесі $n$ жолда үш бүтін саннан $a_i$, $b_i$ және $c_i$ $(1 <= a_i, b_i, c_i <= 500)$ - Кирилл, Айбар және Сұлтанға есепті шығаруға кететін уақыт .

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

Екі сан шығарыңыз -- ең көп есеп және ең аз айыпқұл.

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

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

Берілген мысал.
$n = 1$.
$n = 2$.
Барлық $i$ үшін $a_i = b_i = c_i$ орындалады.
Барлық $i$ үшін $a_i = b_i = c_i$ орындалады.
$n = 6$.
$n = 7$.
$n = 8$.
$n = 9$.
$n = 10$.

Пример:

Вход

2
1 123 345
300 301 301

Ответ

2 423

( Batyr Sardarbekov )
комментарий/решение(10) олимпиада

Есеп №8.

Задача A. Топтық ойын

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

1 second

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

256 megabytes

Бір күні $n$ адам ойын ойнамақшы болып шешті. Ойынды бастау үшін олар екі топқа бөлінулері керек. Әр $i$-інші ойыншының ойнау қабілеті $a_i$. Топтың күші сол топтағы ойыншылардың қабілеттерінің қосындысы. Сізге ойнайтын $2 * k$ адамды таңдау керек. Олар өзара екі топқа бөлінеді. Бірінші топта қатардың басына жақын $k$ ойыншы болады. Екінші топта қатардың соңына жақын $k$ ойыншы болады. Бірінші топтың күшін $A$, ал екінші топтың күшін $B$ деп алайық. Ең үлкен $A - B$ нәтижесін табыңыз. Мысалы, ойнау қабілеттері $[3, 1, 7, 2, 1, 2]$ болатын $6$ адам бар. Позициялары $1, 3, 5 ,6$ болатын адамдарды ойнайды деп шешсек, бірінші топта $1$-ші және $3$-ші ойыншылардан тұрады, бірінші топтың күші $A = 3 + 7 = 10$ болады. Екінші топта $5$-ші және $6$-шы ойыншылардан тұрады, екінші топтың күші $B = 1 + 2 = 3$ болады. $A - B = 10 - 3 = 7$.

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

Бірінші жолда $n$, $k$ екі саны берілген ($1 <= n <= 10^5$, $1 <= k <= \frac{n}{2}$) - ойыншылар саны және топтың мөлшері. Екінші жолда $n$ ойыншының ойнай қабілеттері берілген $a_1, a_2 \ldots a_n$ ($1 <= a_i <= 10^5$).

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

Ең үлкен $A - B$ мәнін табыңыз.

Примеры:

Вход

6 2
3 1 7 2 1 2

Ответ

Вход

5 1
3 4 6 8 9

Ответ

-1

Түсініктеме

Бұл есеп $7$ бөліктен тұрады, әр бөліктің шектеулері төменде берілген:

$n <= 15$. $12$ балл береді.
$a_i \geq a_{i+1}$ әр $1 <= i <= n - 1$. $11$ балл береді.
$a_i <= a_{i+1}$ әр $1 <= i <= n - 1$. $11$ балл береді.
$k = 1$. $16$ балл береді.
$k <= 100$. $19$ балл береді. Бұл бөліктен балл алу үшін: 4-ші бөлік шығарылған болуы керек.
Есептің негізгі шектеулері. $31$ балл береді. Бұл бөліктен балл алу үшін: барлық 1,2,3,4,5 бөліктері шығарылған болу керек.

( Batyr Sardarbekov )
комментарий/решение олимпиада

Есеп №9.

Есеп С. Үштік

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

1 second

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

256 megabytes

Сізге ұзындығы $n$ болатын $a$ атаулы сандар тізбегі және $q$ сұраулар беріледі. Әрбір сұрау $l$ және $r$ екі санынан тұрады. Әрбір сұрау үшін келесі мәнді табыңыз: $$ \sum_{i=l}^{r} \sum_{j=l}^{r} \sum_{k=l}^{r} max(a_i, a_j, a_k) - min(a_i, a_j, a_k) $$ Жауап үлкен болуы мүмкін болғандықтан, оның $10^9 + 7$ санына бөлгендегі қалдығын шығарыңыз.

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

Бірінші жолда $n$ және $q$ $(1 <= n, q <= 10^5)$ екі бүтін сандары бар. Келесі жолда $n$ бүтін сандар $a_1, a_2, \ldots a_n$ $(1 <= a_i <= 10^9)$ — сандар тізбегі бар. Келесі $q$ жолдарында екі бүтін сан $l_i, r_i$ $(1 <= l_i <= r_i <= n)$ — $i$-шы сұраудың сипаттамасы бар.

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

$q$ бүтін сан шығарыңыз — барлық сұрауларға жауаптар.

Примеры:

Вход

Ответ

Вход

6 1
999370245 75 860 26427 218288294 917
1 6

Ответ

731295209

( Batyr Sardarbekov )
комментарий/решение олимпиада