Nurdaulet Akhanov

Есеп №1.

Есеп B. Бөлінеді ме

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

1 second

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

256 megabytes

ОМА санның 8-ге бөлінгіштігінің өз қасиетін ойлап табуды ұйғарды. Егер берілген санның цифрларының орындарын ауыстрығанда, бастаушы нөлдерсіз және 8-ге бөлінетін сандар тізбегі табылатын болса, ОМА бұл санды 8-ге бөлінеді деп атайды.

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

Бірінші жолда бүтін $n$ саны берілген $(1 \leq n \leq 10^3) $ - санның ұзындығы. $\\$ Екінші жолда цифрлардан тұратын $s$ жолы берілген - тексеру қажет сан.

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

Егер берілген сан 8-ге бөлінетін болса YES, бөлінбесе NO жазуларын шығарыңыз.

Примеры:

Вход

2
23

Ответ

YES

Вход

3
101

Ответ

NO

Замечание

Сандар тізбегі дегеніміз, берілген жолдағы цифлардың орындарын ауыстыру жолымен алынған тізбек. Мысалы 123 жолынан, цифрларды орын ауыстыру арқылы 321, 312, 213, 231, 132 деген сандар тізбегін алуға болады. Бірінші мысалда 23 санынан 8-ге бөлінетін 32 санын алуға болады жауап YES. Екінші мысалда 101 санынан 8-ге бөлінетін сан алуға болмайды, жауап NO.$\\$ $\\$ Subtask 1: $(n \leq 100)$ $\\$ Subtask 2: $(n \leq 1000)$ ( Nurdaulet Akhanov )
комментарий/решение(10) олимпиада

Есеп №2.

Есеп C. Хан және тізбек

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

2 seconds

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

512 megabytes

Хан туған күніне орай $n$ саннан тұратын сан тізбегін сыйлық ретінде алып, онымен ойнай бастады. Ол тізбектің әр санын алып, оны $m$ рет жазды. Сонымен қатар, Ханның сүйікті жай саны $P$ бар. Оны ендігі қызықтыратыны, осы тізбектің неше тізбекшесінің қосындысы $P$ санына бөлінетіндігі. Ханға осыны анықтауға көмектесіңіз.

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

Бірінші жолда бос орын арқылы үш бүтін сан $n$, $m$, $P$ берілген — сәйкесінше Ханның тізбегінің ұзындығы, әр санды неше рет жазатын мөлшері және жай сан $(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$. Екінші жолда бос орын арқылы $n$ сан $a_1, a_2, ..., a_n$ берілген — Хан сыйлық ретінде алған тізбек $(1 <= a_i <= 10^9)$.

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

Бір сан шығарыңыз — қосындысы $P$-ға бөлінетін тізбекшелердің саны. Бұл сан өте үлкен болуы мүмкін болғандықтан, $1000000007$-ге бөлгендегі қалдығын шығарыңыз.

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

1-бөлім (10 ұпай) — $ n <= 10^5$, $m <= 10^5,$ $P = 2 $. 2-бөлім (10 ұпай) — $ n * m <= 20$, $P <= 1000 $. \par 3-бөлім (10 ұпай) — $ n * m * P <= 10^6, $. \par 4-бөлім (20 ұпай) — $ n * m <= 250000$, $P <= 500 $. \par 5-бөлім (50 ұпай) — $ n <= 10^5$, $m <= 10^9$, $P <= 1000 $.

Пример:

\exmpfile{example.01}{example.01.a}%

Замечание

Хан бастапқы тізбекті былай түрлендіреді. Бастапқы тізбек $a_1, a_2, ..., a_n$ болсын. Және де бос $b$ тізбегі болсын делік. Бір-бірден, солдан оңға қарай $a$ тізбегінен сандарды алып, $a_i$ санын $b$ тізбегінің артына $m$ рет тіркестіріп жазайық. Хан есепті жаңадан пайда болған $b$ тізбегімен шығарады. Тізбекше — бастапқы тізбектің бірнеше, мүмкін нөл, элементін өшіріп тастағаннан кейінгі қалған тізбек. Бірінші мысалда, $b$ тізбегі мынадай болады: $3, 3, 7, 7, 4, 4$. Есептің жауабында көрсетілгендей, $11$ тізбекшенің қосындысы $5$-ке бөлінеді. Олар мыналар: $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 3, 4]$, $[3, 3, 4]$, $[3, 3, 7, 7]$, $[7, 4, 4]$, $[7, 4, 4], $[3, 7, 7, 4, 4], $[3, 7, 7, 4, 4]$. ( Nurdaulet Akhanov )
комментарий/решение(2) олимпиада

Есеп №3.

Есеп C. Хан және тізбек

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

2 seconds

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

512 megabytes

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

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

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

Пример:

\exmpfile{example.01}{example.01.a}%

Замечание

Есеп №4.

Есеп A. Жұптар

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

1 second

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

256 megabytes

Бүтін жай $P$ саны, натурал $n$ мен ұзындығы $n$ болатын $a$-массиві берілген. Егер де сандар жұбының бір-біріне көбейтіндісінің $P$-ға бөлгенінің калдығы мен сол екі санның соммасының $P$-ға бөлгенінің калдығына тең болса, осы жұп жақсы болып саналады. Ресми түрде, $x * y$ $mod$ $P = (x + y)$ $mod$ $P$ шарты орындалған жағдайда $(x, y)$ жұбы жақсы болып саналады. Массивте жақсы жұптар санын табыңыз.

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

Ең бірінші жолда екі бүтін сан берілген $n$ $(1 <= n <= 10^5)$ — массивтің ұзындығы, $P$ $(2 <= P <= 10^9)$ — берілген $P$ саны. Екінші жолда $n$ сан $a_i$ $(0 <= a_i <= 10^9)$ — массивтің $i$-саны берілген.

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

Бір бүтін сан шығарыңыз — жақсы жұптар саны.

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

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

$1 <= n <= 1000, 2 <= p <= 1000$. $20$ ұпайға есептеледі.
$1 <= n <= 1000, p = 2$. $20$ ұпайға есептеледі.
$1 <= n <= 100000, 2 <= p <= 1000$. $20$ ұпайға есептеледі.
$1 <= n <= 100000, 2 <= p <= 10^9$. $40$ ұпайға есептеледі.

Примеры:

Вход

4 3
3 5 12 11

Ответ

Вход

3 5
1 2 7

Ответ

Замечание

Жай сан — бірден үлкен, бірақ бір мен өзінен басқа сандарға бөлінбейтін, бүтін оң сан (мысалы, $2, 3, 5, 7, 11, 13, 17, \dots $). $a$ $mod$ $b$ жазылуы, $a$-ның $b$-ға бөлгендегі қалдығын білдіреді.

Бірінші мысалда 2 ғана жұп жақсы болып есептеледі: $(3, 12), (5, 11)$ себебі $(3 + 12)$ mod $3$ = $(3 * 12)$ mod $3$ және $(5 + 11)$ mod $3$ = $(5 * 11)$ mod $3$
{Екінші мысалда 1 ғана жұп үйлеседі: $(2 + 7)$ mod $5$ = $(2 * 7)$ mod $5$}

( Nurdaulet Akhanov )
комментарий/решение(8) олимпиада

Есеп №5.

Есеп C. Медиана

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

3 seconds

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

512 megabytes

Ұзындығы $n$ болатын $a$ массивы пен $q$ сұратулар бар. Әр сұрату $l$ және $r$ сандарымен сипатталады. Әр сұрату үшін, $l$-ден $r$-ға дейінгі массив элементтерін алып тастағандағы калған массивтың медианасын табу керек.

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

Бірінші жолда екі сан $n, q$ $(1 <= n, q <= 10^6)$ — массивтың ұзындығы мен сұратулар саны беріледі. Екінші жолда $n$ бүтін сан $a_i$ $(1 <= a_i <= 10^9)$ — $a$ массивының $i$-шы саны беріледі. Келесі $q$ жолда екі саннан $l, r$ $(1 <= l <= r <= n)$ — алынатын кесіндінің шеттері беріледі. Қалған массивте ең болмаса бір сан қалатынына кепілдік беріледі.

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

Әр сұрату үшін, бөлек жолдарда, қалған массивтың медианасын шығарыңыз.

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

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

$1 <= n <= 1000, 1 <= q <= 1000, 1 <= a_i <= 10^9$. $8$ ұпайға бағаланады.
$1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= a_{i + 1} <= 10^9$. $9$ ұпайға бағаланады.
$1 <= n <= 100000, 1 <= q <= 10000, 1 <= a_i <= 10^9$. $19$ ұпайға бағаланады.
$1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 100$. $15$ ұпайға бағаланады.
$1 <= n <= 100000, 1 <= q <= 100000, 1 <= a_i <= 10^9$. $31$ ұпайға бағаланады.
$1 <= n <= 500000, 1 <= q <= 1000000, 1 <= a_i <= 10^9$. $18$ ұпайға бағаланады.

Пример:

Вход

Ответ

Замечание

Ұзындығы $n$ болатын массивтың медианасы деп, массивтың сорттаудан кейінгі $\frac{n+1}{2}$ орнында тұратын санды атайды. Бірінші мысалда, бірінші сұратудан кейін, $[2, 1, 4]$ тізбегі жоғалып $[1, 9]$ массивы қалады. Қалған массивтың ұзындығы $2$ болғандықтан, медиананың орны $\frac{3}{2} = 1$ тең. Екінші сұратудан кейін, $[1]$ тізбегі жоғалып $[2, 1, 4, 9]$ массивы қалады. Қалған массивтың ұзындығы $4$ болғандықтан, медиананың орны $\frac{5}{2} = 2$-тең. Қалған массивтың сортталған түріндегі екінші элементі $2$-тең. Үшінщі сұратудан кейін, $[4, 9]$ тізбегі жоғалып $[1, 2, 1]$ массивы қалады. Қалған массивтың ұзындығы $3$ болғандықтан, медиананың орны $\frac{4}{2} = 2$-тең. Қалған массивтың сортталған түріндегі екінші элементі $1$-тең. ( Nurdaulet Akhanov )
комментарий/решение(1) олимпиада