Задача A. Қояндар

Айбарда $K$ бөлімнен тұратын бақша бар. Бақшада $n$ қояндар тұрады. Әрбір қоян бақшаның бір бөлімінде орналасқан. Кейде қояндар көршілес бөлімдерге өтуі мүмкін. Сондай-ақ, кейде Айбар оларды тамақтандыру үшін кейбір бөлімдердегі қояндардың санын білу керек. Айбарға $q$ сұраныстар берілген. Олар келесі түрде болады:

• $x$-шi нөмірдегі қоян $(1 <= x <= n)$ бір бөлімге солға немесе оңға көшті. Бұл жағдайда қоян бақшадан тыс шықпайтынына кепілдік беріледі
• $l$-ден $r$-ге дейінгі $(1 <= l <= r <= K)$ бөлімдердегі қояндардың санын табу керек.

Бірінші жолда екі сан берілген - $n$ және $K$. \\ Екінші жолда $n$ сандар - әрбір қоянның бастапқыда орналасқан бөлімнің нөмірі көрсетілген.\\ Содан кейін жеке жолда сұраныстардың санын сипаттайтын $q$ саны берілген. Келесі $q$ жолдарда сұраныстардың сипаттаулары берілген. Сұраулар келесі түрде беріледі:

• $\texttt{L } x$ - $x$-ші қоян сол жақта орналасқан бөлімге көшті
• $\texttt{R } x$ - $x$-ші қоян оң жақта орналасқан бөлімге көшті
• $\texttt{G } l\; r$ - $l$-ден бастап $r$-ге дейінгі аралықтағы қояндардың санын санап, шығару.

Үшінші типтегі әрбір сұранысқа бөлек жолда бір сан — сұраныстың жауабын шығарыңыз. Бұл есеп $3$ бөлімнен тұрады:

1. $1 <= n, K, q <= 1000$. $20$ баллға бағаланады.
2. $1 <= n, K, q <= 5 * 10^5$. Қояндардың көшу сұраулары жоқ. $20$ баллға бағаланады.
3. $1 <= n, K, q <= 5 * 10^5$. $60$ баллға бағаланады.

Вход

3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7

Ответ

1
3

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

Ара тәрізді бір циклдан тұратын 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$ ұпайға бағаланады.

1. $n = 4$
2. $n = 5$
3. $n = 10$
4. $n = 11$
5. $n = 20$
6. $n = 21$
7. $n = 2019$
8. $n = 2020$
9. $n = 12345$
10. $n = 123456$

Вход

4

Ответ

3 1 4 2 

Задача C. From And with love

Абай массивтерді өте жақсы көреді. Әсіресе массивтің тізбекшелерімен ойнағанды ұнатады. Тізбекше — ол массивтен бірнеше(мүмкін 0) элементтің өшіру арқылы алынатын сандар тізбегі. Сізге $N$ саннан тұратын $A$ массивы беріледі. Массивтің кез-келген бір тізбегін қарастырайық. Олардың биттік AND $X$-қа тең болсын. Тізбекше жақсы деп аталады, егер тізбекте $X$-ке тең сан болмаса. Массивтегі жақсы тізбекшелердің саның табыңыз. Бірінші жолда бір бүтін сан $N$ — $A$ массивының размері берілген. Келесі жолда $N$ бүтін теріс емес сандар берілген — $A$ массивының элементтері. Жалғыз бүтін сан шығарыңыз — жақсы тізбекшелердің саның. Жауап өте үлкен болуы мүмкін, сол себептен оның $10^9 + 7$ге бөлгендегі қалдығын шығарыңыз. Есеп 25 тесстен тұрады, әр тест 4 баллға бағаланады:

1. $1 <= N <= 15$, $0 <= A_i < 2^{20}$. Тест 1 -- 3
2. $1 <= N <= 10^5$, $0 <= A_i < 2^4$. Тест 4 -- 7
3. $1 <= N <= 10^5$, $0 <= A_i < 2^{10}$. Тест 8 -- 12
4. $1 <= N <= 10^5$, $0 <= A_i < 2^{15}$. Тест 13 -- 18
5. $1 <= N <= 10^6$, $0 <= A_i < 2^{20}$. Тест 19 -- 25

Вход

5
0 2 5 3 7

Ответ

6

жақсы тізбекшелердің бірі: 2, 5, 7. Оның биттік AND 0ге тең, және 0 осы тізбекте жоқ . Биттік AND операциясы барлық заманауи бағдарламалау тілдерінде бар, С++ және Java тілінде <<$\string&$>>, ал Pascal тілінде <>. Биттік AND операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $and$ 1 = 1, 1 $and$ 0 = 0\\ 0 $and$ 1 = 0, 0 $and$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі.

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

Тиманың үш інісі бар: Батыр, Димаш және Есмахан. Тима оларға көңіл көтеру үшін размеры $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 баллға бағаланады:

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

Вход

7
4 1 2 3 1 3 2

Ответ

1

Үлгідегі бөліністердің бір түрі: 4 1 | 2 3 1 | 3 2 Және 4 1 | 2 3 | 1 3 2 бөлінісі дұрыс

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

Есмахан - морж өсіру бойынша стартап бастады. Ол $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. Берілген тест.
2. $1 <= n <= 1000$, $1 <= a_i <= 1000$ әр $1 <= i <= n$, әр қызметкерде бағыныштылар саны бірден көп емес| 2 тест.
3. $1 <= n <= 1000$, $1 <= a_i <= 1000$ әр $1 <= i <= n$ | 2 тест.
4. $1 <= n <= 1000$, әр қызметкерде бағыныштылар саны бірден көп емес | 2 тест.
5. $1 <= n <= 1000$ | 3 тест.
6. $1 <= n <= 200000$, әр қызметкерде бағыныштылар саны бірден көп емес | 5 тест.
7. $1 <= n <= 200000$ | 10 тест.

Вход

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

Ответ

7

Мысалда $b={5, 4, 3, 1, 4, 3, 2}$

Задача F. K-sort

Есмаханда $N$ саннан тұратын $A$ массиві берілген $A_0,A_1,..,A_{N-1}$. Массив $k$-сортталатын деп аталады, егер келесі операцияны бірнеше(мүмкін 0) рет жасап, массивты кемімейтін қылдырып жасауға болса: $i(0 <= i < N)$ индексін таңдап, массивтегі $i$-ші және $((i + k)$ mod $N$)-ші элементтердің орның ауыстыру. Мұндағы $a$ mod $b$ дегеніміз $a$-ның $b$-ға бөлгендегі қалдығы. Мысалы, $7$ mod $3$ = 1, $8$ mod $4$ = 0, $5$ mod $11$ = 5. Массив кемімейтін деп саналады, егер бірінші элементтен басқа барлық элемент алдыңдағы элементтен кіші болмаса. Сізге $Q$ сұрау беріледі, әр сұрауда бір бүтін $k$ саны беріледі. Әр сұрау үшін $A$ массивы $k$-сортталатынба екенің аңықтау қажет. Бірінші жолда екі бүтін сан $N,Q(1 <= N,Q <= 300000)$. Екінші жолда $N$ бүтін сан $A_0,A_1, ..., A_{N - 1}(1 <= A_i <= 10^9)$. Келесі $q$ жолда бір бүтін саннан $k_i(1 <= k_i <= N)$. $q$ жолда бір саннан шығарыңыз — $i$-ші жолда $1$ шығарыңыз, егер $A$ массивы $k_i$-сортталатын болса, болмаса 0 шығарыңыз. Есеп 25 тесстен тұрады, әр тест 4 ұпайға бағаланады:

1. $1 <= N,Q <= 100$. Тест 1 -- 4
2. $1 <= N <= 100000, Q = 1$, $k_1 = N$. Тест 5 -- 7
3. $1 <= N,Q <= 2000$. Тест 8 -- 11
4. $1 <= N,Q <= 50000$. Тест 12 -- 15
5. $1 <= N,Q <= 300000$. Тест 16 -- 25

Вход

4 4
3 2 2 4
1
3
2
4

Ответ

1
1
1
0

$A={3,2,2,4}$, басқаша айтқанда $A_0 = 3, A_1 = 2, A_2 = 2, A_3 = 4$. Массив $3$-сортталатын, себебі келесі операциялармен сорттауға болады:

1. $i = 1$ таңдаймыз, сонда $(i + 3)$ mod $N = (1 + 3)$ mod $4 = 0$. Онда біз $A_1$ және $A_0$ орның ауыстырамыз. Содан кейін $A = {2,3,2,4}$ болады.
2. $i = 2$ таңдаймыз, сонда $(i + 3)$ mod $N = (2 + 3)$ mod $4 = 1$. Онда біз $A_2$ және $A_1$ орның ауыстырамыз. Содан кейін $A = {2,2,3,4}$ болады.