A. Tangalar o'yini

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Durdona yaqinda sport dasturlashdan Campda qatnashdi. Campdagi mavzularni yaxshi tushunmaganligi sababli u juda zerikib qoldi va bitta o'yin o'ylab topdi (yaxshiyamki u o'zi bilan 3 ta tanga olib kelgan). Dastlab u 3 ta tangasini sonlar o'qiga joylashtiradi. O'yinning qoidasi shunday : u bitta harakatda eng chapdagi yoki eng o'ngdagi tangani olib qolgan ikkita tanga orasidagi ixtiyoriy butun nuqtaga joylashtira oladi. Endi u optimal harakat qilsa, uning o'yini eng ko'pi bilan nechta harakatgacha davom etishini bilmoqchi.

Durdonaga buni aniqlashda yordam bering.

Kiruvchi ma'lumotlar:

Yagona qatorda 3 ta butun son \(a, b, c\) - Durdona dastlab tangalarini joylashtirgan nuqtalar kiritiladi.

\((0 < a < b < c < 100)\)

Chiquvchi ma'lumotlar:

Durdona optimal o'ynasa eng ko'pi bilan nechta harakatni amalga oshira olishini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 3 6	2

B. Sirli xabar va “tez-tez uchraydigan sonlar” qoidasi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Anvar– mohir kod buzuvchi. U har qanday shifrlangan xabarni sonlarning tez-tez uchrashini topish orqali yechish mumkin deb o‘ylaydi. Haqiqiy texnika bu emas, lekin Anvar uchun yetarli.

U dushman xabarini qo‘lga kiritdi. Xabar \(N\) ta butun sondan iborat, va har bir son \(C\) dan kichik yoki teng.

Anvarning fikricha, xabarni “frequency analysis” qilish degani – sonlarni ko'p uchraydiganidan kam uchraydiganiga qarab tartiblash.

Aniqroq qilib aytganda:

Xabarni shunday tartiblangki, har qanday ikkita son \(X\) va \(Y\) uchun:
1. Agar \(X\) soni original xabarda \(Y\) sonidan ko‘proq uchragan bo‘lsa, \(X\) soni oldin keladi
2. Agar \(X\) va \(Y\) sonlari bir xil marta uchragan bo‘lsa, qaysi biri original xabarda dastlab kelsa, shunisi oldin turadi

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(N, C\) , mos ravishda xabarning uzunligi va sonlarning maksimal qiymati kiritiladi. \((1\le N \le 1000, 1\le C\le 10^9)\)

Ikkinchi qatorda \(N\) butun son kiritiladi.

Chiquvchi ma'lumotlar:

Xabarni Anvar uslubida tartiblab chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 5 5 3 5 2 3 5 2 4 2 3	5 5 5 3 3 3 2 2 2 4

C. Xor sequence

Xotira: 64 MB, Vaqt: 1000 ms

Masala

\(A_1=1\)

\(A_2=1\)

\(A_i=|A_{i-1}-A_{i-2}| \oplus(A_{i-1}+A_{i-2})\) agar \(i>2\)

Bu yerda \(\oplus\) bitwise xor amalini anglatadi.

Shu shartlar asosida qurilgan \(A\) ketma-ketlik mavjud.

Sizning vazifangiz berilgan \(L\), \(R\) va \(M\) sonlari uchun \((A_L+A_{L+1}+A_{L+2}+...+A_R) \ \ mod \ \ M\) ning qiymatini, ya'ni ketma-ketlikning \(L\) - tartibdan \(R\) - tartibgacha bo'lgan elementlari yig'indisini \(M\) ga bo'lgandagi qoldiqni aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 2 \times 10^5)\) testlar soni kiritiladi.

Keyingi \(T\) ta satrda uchtadan butun son, \(L(1 \le L \le 10^9)\), \(R(L \le R \le 10^9)\) va \(M(1\le M \le 10^9)\) sonlari kiritiladi.

Kiritilgan \(M\) tub son ekanligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda bitta butun son, masala shartida so'ralgan qiymatni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2 4 998244353 92345678 998244353 998244353	5 367684397

D. Eng kichik qiymat

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Sizga \(a\) soni berilgan,shunday natural \(b\) soni borki \(k = \frac{a * b}{a + b}\) bu qiymat ham naturaldir. Sizning vazifangiz \(b\) ning eng kichik qiymatini topish.

Kiruvchi ma'lumotlar:

\(T(1 \le T \le 10 ^ 4 )\) testlar soni beriladi. Har bir test uchun \(a(1 < a \le 2*10 ^ 9)\) soni beriladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda masala javobini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 2 3 4 5 6	2 6 4 20 3

E. Sirli o‘rmon va xavfsiz yo‘l

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Bir sirli qahramon o‘rmon bo‘ylab xavfli hududdan qochmoqda. O‘rmonning ba’zi katakchalarida daraxtlar bor. Qahramonimiz biladiki ba'zi daraxtlar ortida sirli tuzoqlar bor ammo aynan qaysi daraxtlar ortida tuzoq borligini bilmaydi, shu sababli daraxtlardan iloji boricha uzoqroq yurishi kerak. Qahramonning maqsadi o'zining xavfsiz uyi joylashgan katakchaga yetib borish, shu bilan birga daraxtlardan iloji boricha uzoq yo‘l tanlash.

O‘rmonni\(N\times M\) katakchali panjara bilan ifodalash mumkin:

Bo‘sh katakchalar: .
Daraxtlar: +
Qahramonning hozirgi joyi: S
Uy: U

Qahramon har bir qadamda shimol, janub, sharq yoki g'arbga harakat qilishi mumkin, hatto daraxt ustidan ham o‘tishi mumkin.

Agar qahramon \((R, C)\) katakchada bo‘lsa va daraxt \((A, B)\) katakchada bo‘lsa, ular orasidagi masofa quyidagicha:

\(|R-A| + |C-B|\)

Qahramon uchun eng xavfsiz yo'l deganda, yo‘l davomida daraxtlardan eng yaqin masofa maksimal bo‘ladigan yo‘l nazarda tutiladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(N, M (1\le N, M \le 500)\) – panjaraning o‘lchamlari kiritiladi.
Keyingi \(N\) ta qatorda \(M\) tadan belgi: ., +, S, U
Panjarada aniq bitta S, bitta U va kamida bitta + mavjud

Chiquvchi ma'lumotlar:

Qahramon eng xavfsiz yo‘ldan foydalansa daraxtlargacha bo'lgan eng qisqa masofani chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 4 +... .... .... S..U	3