Zharaskhan Aman


Есеп №1. (Такси) Елібай есімді кәсіпкер Алматы қаласында құрылыс компаниясын басқарады. Қазір оның компаниясы $N$ құрылыс объектісінде жұмыс атқарып жатыр. Оның күнделікті жұмысы — бас кеңседен шығып өз көлігімен құрылыс объектілерін аралап шығу. Қағаз жұмыстарына байланысты, ол бір құрылыс объектісіне барған соң, бас кеңсеге қайтадан оралуы кажет. Бүгін оның жолы болмай, көлігі істен шығып қалды. Кешігіп қалмас үшін, Елібай ZhureBER және Zhett деген такси сервистерінің көмегіне жүгінді. Тариф құны арзан болмай шықты: жүрген $d$ шақырым үшін ол $d^2$ теңге төлеу керек. Оның досы Айсұлтан — жоғарыда айтылған такси сервистерін басқарады. Айсұлтан досына $N$ промо-код сатып алуды ұсынды. Промо-кодтың бағасы $X$ теңгені құрайды. Промо-код қолданарда егер $X \ge d$ болса, Елібай $X$ теңге төлейді, ал егер $X < d$ болса, $X + (d - X)^2$ теңге төлейді.
Елібай $i$ деген нөмірдегі объектіні қарап келу үшін такси шақырады (бас кеңседен объектіге дейінгі жолдың және кері жолдың ұзындығы бірге $d_i$ шақырымды құрайды). Ол бір рет такси шақырған кезде промо-кодты екі рет қолдана алмайды және келесі объектіге бару үшін қайтадан такси шақырады.
Айсұлтан Елібайдың досы болғандықтан, ол Елібайға $X$ санын таңдауға мүмкіндік берді. Әрине, $X$ теріс емес бүтін сан болуы керек. Сіздің тапсырмаңыз — Елібай ақшасын мейлінше аз жарататындай $X$ санын таңдауға көмектесу.
Кіріс деректер форматы:
Бірінші қатарда бір $N$ саны берілген.
Екінші қатарда бос орын арқылы $d_1, d_2, \ldots d_n$ бүтін сандары берілген — олар бас кеңседен кезекті объектіге дейінгі барып қайтқандағы жолдың ара қашықтығын көрсетеді.
Шығыс деректер форматы:
Бір сан шығарыңыз — егер Елібай $X$ санын оптималды таңдаған болса, ол кем дегенде қанша ақша жаратуы қажет.
Мысалдар:
1.Мысал: 
5
7 7 7 7 7
Жауап: 
35
2.Мысал: 
10
2 1 3 6 7 5 9 2 2 4
Жауап: 
70
3.Мысал: 
2
0 100
Жауап: 
199
Түсініктеме:
Екінші мысал:
Егер X = 6 болса, біз кем дегенде 70 теңге жұмсайтын едік.
Барлығына $ 6 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Егер X = 5 болса, барлық сомма 71 болатын еді. Егерде, X = 7 болып таңдалынса, толық сомма 74 болар еді.
Бағалау:
Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:
( Zharaskhan Aman )
комментарий/решение(5) олимпиада
Есеп №2. (Такси) Елібай есімді кәсіпкер Алматы қаласында құрылыс компаниясын басқарады. Қазір оның компаниясы $N$ құрылыс объектісінде жұмыс атқарып жатыр. Оның күнделікті жұмысы — бас кеңседен шығып өз көлігімен құрылыс объектілерін аралап шығу. Қағаз жұмыстарына байланысты, ол бір құрылыс объектісіне барған соң, бас кеңсеге қайтадан оралуы кажет. Бүгін оның жолы болмай, көлігі істен шығып қалды. Кешігіп қалмас үшін, Елібай ZhureBER және Zhett деген такси сервистерінің көмегіне жүгінді. Тариф құны арзан болмай шықты: жүрген $d$ шақырым үшін ол $d^2$ теңге төлеу керек. Оның досы Айсұлтан — жоғарыда айтылған такси сервистерін басқарады. Айсұлтан досына $N$ промо-код сатып алуды ұсынды. Промо-кодтың бағасы $X$ теңгені құрайды. Промо-код қолданарда егер $X \ge d$ болса, Елібай $X$ теңге төлейді, ал егер $X < d$ болса, $X + (d - X)^2$ теңге төлейді.
Елібай $i$ деген нөмірдегі объектіні қарап келу үшін такси шақырады (бас кеңседен объектіге дейінгі жолдың және кері жолдың ұзындығы бірге $d_i$ шақырымды құрайды). Ол бір рет такси шақырған кезде промо-кодты екі рет қолдана алмайды және келесі объектіге бару үшін қайтадан такси шақырады.
Айсұлтан Елібайдың досы болғандықтан, ол Елібайға $X$ санын таңдауға мүмкіндік берді. Әрине, $X$ теріс емес бүтін сан болуы керек. Сіздің тапсырмаңыз — Елібай ақшасын мейлінше аз жарататындай $X$ санын таңдауға көмектесу.
Кіріс деректер форматы:
Бірінші қатарда бір $N$ саны берілген.
Екінші қатарда бос орын арқылы $d_1, d_2, \ldots d_n$ бүтін сандары берілген — олар бас кеңседен кезекті объектіге дейінгі барып қайтқандағы жолдың ара қашықтығын көрсетеді.
Шығыс деректер форматы:
Бір сан шығарыңыз — егер Елібай $X$ санын оптималды таңдаған болса, ол кем дегенде қанша ақша жаратуы қажет.
Мысалдар:
1.Мысал: 
5
7 7 7 7 7
Жауап: 
35
2.Мысал: 
10
2 1 3 6 7 5 9 2 2 4
Жауап: 
70
3.Мысал: 
2
0 100
Жауап: 
199
Түсініктеме:
Екінші мысал:
Егер X = 6 болса, біз кем дегенде 70 теңге жұмсайтын едік.
Барлығына $ 6 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Егер X = 5 болса, барлық сомма 71 болатын еді. Егерде, X = 7 болып таңдалынса, толық сомма 74 болар еді.
Бағалау:
Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:
( Zharaskhan Aman )
комментарий/решение(5) олимпиада
Есеп №3. (Такси) Елібай есімді кәсіпкер Алматы қаласында құрылыс компаниясын басқарады. Қазір оның компаниясы $N$ құрылыс объектісінде жұмыс атқарып жатыр. Оның күнделікті жұмысы — бас кеңседен шығып өз көлігімен құрылыс объектілерін аралап шығу. Қағаз жұмыстарына байланысты, ол бір құрылыс объектісіне барған соң, бас кеңсеге қайтадан оралуы кажет. Бүгін оның жолы болмай, көлігі істен шығып қалды. Кешігіп қалмас үшін, Елібай ZhureBER және Zhett деген такси сервистерінің көмегіне жүгінді. Тариф құны арзан болмай шықты: жүрген $d$ шақырым үшін ол $d^2$ теңге төлеу керек. Оның досы Айсұлтан — жоғарыда айтылған такси сервистерін басқарады. Айсұлтан досына $N$ промо-код сатып алуды ұсынды. Промо-кодтың бағасы $X$ теңгені құрайды. Промо-код қолданарда егер $X \ge d$ болса, Елібай $X$ теңге төлейді, ал егер $X < d$ болса, $X + (d - X)^2$ теңге төлейді.
Елібай $i$ деген нөмірдегі объектіні қарап келу үшін такси шақырады (бас кеңседен объектіге дейінгі жолдың және кері жолдың ұзындығы бірге $d_i$ шақырымды құрайды). Ол бір рет такси шақырған кезде промо-кодты екі рет қолдана алмайды және келесі объектіге бару үшін қайтадан такси шақырады.
Айсұлтан Елібайдың досы болғандықтан, ол Елібайға $X$ санын таңдауға мүмкіндік берді. Әрине, $X$ теріс емес бүтін сан болуы керек. Сіздің тапсырмаңыз — Елібай ақшасын мейлінше аз жарататындай $X$ санын таңдауға көмектесу.
Кіріс деректер форматы:
Бірінші қатарда бір $N$ саны берілген.
Екінші қатарда бос орын арқылы $d_1, d_2, \ldots d_n$ бүтін сандары берілген — олар бас кеңседен кезекті объектіге дейінгі барып қайтқандағы жолдың ара қашықтығын көрсетеді.
Шығыс деректер форматы:
Бір сан шығарыңыз — егер Елібай $X$ санын оптималды таңдаған болса, ол кем дегенде қанша ақша жаратуы қажет.
Мысалдар:
1.Мысал: 
5
7 7 7 7 7
Жауап: 
35
2.Мысал: 
10
2 1 3 6 7 5 9 2 2 4
Жауап: 
70
3.Мысал: 
2
0 100
Жауап: 
199
Түсініктеме:
Екінші мысал:
Егер X = 6 болса, біз кем дегенде 70 теңге жұмсайтын едік.
Барлығына $ 6 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Егер X = 5 болса, барлық сомма 71 болатын еді. Егерде, X = 7 болып таңдалынса, толық сомма 74 болар еді.
Бағалау:
Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:
( Zharaskhan Aman )
комментарий/решение олимпиада
Есеп №4. 

Есеп E. НурлашКО

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

АланашКО мен НурлашКО графом ойнап жатыр, сол себепті сіздің көмегіңіз қажет. Ойын бағытталған, циклдік емес $G$ графынан басталады. Алғашында граф $n$ шыңнан тұрады және граф қабырғасыз болып келеді. Ойын барысында ойнаушылар $q$ операциялар орындайды. Операциялар түрлері осындай:
  1. $u_i$ шыңынан $v_i$ шыңына бағытталған қабырға жасау.
  2. 1-ші шыңнан $x_i$ шыңына дейін бағытталған қабырғалар арқылы жол табылса, $x_i$ шығарыңыз, табылмаса $0$ шығарыңыз.
Әр операциядан кейін граф циклсыз болатынына кеппілдік беріледі.
Формат входного файла
Бірінші жолда үш бүтін сан $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — шыңдар саны, операциялар саны мен константалық сан енгізіледі. Келесі $q$ жол әр операцияның сипаттамасын береді.
  1. Бірінші түрлі операция осылай сипатталады: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
  2. Екінші түрлі операция осылай сипатталады: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.
Назар аударыңыз, бірінші операцияға арналған $u_i$, $v_i$ шыңдар номерлері мен екінші операцияға арналған $x_i$ шыңының номері кодталған болып келеді, және оларды алу үшін осындай тағы операциялар орындау қажет: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} $lastans$ — соңғы $2$ операциясынан шыққан жауап (алғашында $lastans$ $0$-тең). Мына жерде $\oplus$ аралас немесе операциясын білдіреді. Осы операция заманғы бағдарламалау тілдерінде ба, мысалға, C++ және Java — ^ арқылы белгіленген, Pascal — $xor$ арқылы. $a \mod b$ операциясы $a$-ның $b$-ға бөлгендегі қалдығын береді. Есепте кемінде бір екінші түрлі операция келетініне кепілдік беріледі. Аралас НЕМЕСЕ($xor$) операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. Мысалға, егер $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ сонда: $X$ $xor$ $Y$ = $68_{10}$ = $1000100_{2}$.
Формат выходного файла
Әр екінші түрлі операцияның жауабын бөлек жолға шығарыңыз.
Система оценки
Есеп 5 бөлімнен тұрады:
  1. Шарттағы мысалдар. $0$ ұпайға бағаланады.
  2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. $11$ ұпайға бағаланады.
  3. $n, q <= 10^3$. $18$ ұпайға бағаланады.
  4. $t = 0$. $39$ ұпайға бағаланады.
  5. Есептің толық шарттары. $32$ ұпайға бағаланады.
Примеры:
Вход 
5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3
Ответ
1
0
2
0
4
Вход 
5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3
Ответ
1
0
2
0
4
( Zharaskhan Aman )
комментарий/решение(4) олимпиада
Есеп №5. 

Есеп E. НурлашКО

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

АланашКО мен НурлашКО графом ойнап жатыр, сол себепті сіздің көмегіңіз қажет. Ойын бағытталған, циклдік емес $G$ графынан басталады. Алғашында граф $n$ шыңнан тұрады және граф қабырғасыз болып келеді. Ойын барысында ойнаушылар $q$ операциялар орындайды. Операциялар түрлері осындай:
  1. $u_i$ шыңынан $v_i$ шыңына бағытталған қабырға жасау.
  2. 1-ші шыңнан $x_i$ шыңына дейін бағытталған қабырғалар арқылы жол табылса, $x_i$ шығарыңыз, табылмаса $0$ шығарыңыз.
Әр операциядан кейін граф циклсыз болатынына кеппілдік беріледі.
Формат входного файла
Бірінші жолда үш бүтін сан $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — шыңдар саны, операциялар саны мен константалық сан енгізіледі. Келесі $q$ жол әр операцияның сипаттамасын береді.
  1. Бірінші түрлі операция осылай сипатталады: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
  2. Екінші түрлі операция осылай сипатталады: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.
Назар аударыңыз, бірінші операцияға арналған $u_i$, $v_i$ шыңдар номерлері мен екінші операцияға арналған $x_i$ шыңының номері кодталған болып келеді, және оларды алу үшін осындай тағы операциялар орындау қажет: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} $lastans$ — соңғы $2$ операциясынан шыққан жауап (алғашында $lastans$ $0$-тең). Мына жерде $\oplus$ аралас немесе операциясын білдіреді. Осы операция заманғы бағдарламалау тілдерінде ба, мысалға, C++ және Java — ^ арқылы белгіленген, Pascal — $xor$ арқылы. $a \mod b$ операциясы $a$-ның $b$-ға бөлгендегі қалдығын береді. Есепте кемінде бір екінші түрлі операция келетініне кепілдік беріледі. Аралас НЕМЕСЕ($xor$) операциясы төмендегі ақиқаттық кестесіне сәйкес операндтардың (сандардың) қосындысын анықтайды.\\ 1 $xor$ 1 = 1, 1 $xor$ 0 = 1\\ 0 $xor$ 1 = 1, 0 $xor$ 0 = 0\\ Операндтар ондық түрде жазылады, бірақ орындалғанда олар екілік түрге түрлендіріледі. Нәтижесі ондық түрде көрсетіледі. Мысалға, егер $X$ = $109_{10}$ = $1101101_{2}$, $Y$ = $41_{10}$ = $101001_{2}$ сонда: $X$ $xor$ $Y$ = $68_{10}$ = $1000100_{2}$.
Формат выходного файла
Әр екінші түрлі операцияның жауабын бөлек жолға шығарыңыз.
Система оценки
Есеп 5 бөлімнен тұрады:
  1. Шарттағы мысалдар. $0$ ұпайға бағаланады.
  2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. $11$ ұпайға бағаланады.
  3. $n, q <= 10^3$. $18$ ұпайға бағаланады.
  4. $t = 0$. $39$ ұпайға бағаланады.
  5. Есептің толық шарттары. $32$ ұпайға бағаланады.
Примеры:
Вход 
5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3
Ответ
1
0
2
0
4
Вход 
5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3
Ответ
1
0
2
0
4
( Zharaskhan Aman )
комментарий/решение(4) олимпиада