A. Alohida bo’luvchilar soni

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) to’plam hamda \(K\) soni berilgan, siz nechta natural son \(K\) sonining bo’luvchisi bo’lishi hamda \(A\) to’plamning hech bir elementi bo’luvchisi bo’lmasligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son, \(N (1 \le N \le 10^6)\) va \(K (1 \le K \le 10^{13})\) sonlari kiritiladi.

Ikkinchi satrda \(N\) ta butun son, \(A (1 \le A_i \le 10^{18})\) to’plam elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, masala javobini chop eting

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
8 16
2 5 7 4 3 8 3 18
 
1

B. Ekran klaviaturasi

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Zilola o’z klaviaturasini juda yomon ko’radi. Bunga sabab uning klaviaturasidagi harflar yozilgan tugmalar ishlamaydi. Agar u o’z kompyuterida biror so’z yozmoqchi bo’lsa ekran klaviaturasidan foydalanishga majbur bo’ladi. Albatta ekran klaviaturasidan ko’ra ko’proq oddiy klaviaturani ishlatish ancha qulayroq, shu sababli Zilola biror so’z yozmoqchi bo’lsa quyidagi ikki amallardan foydalanadi:

  • Ekran klaviaturasi yordamida yozilish navbati kelgan belgini kiritishi mumkin, bu amal unga noqulaylik tug’diradi;
  • Yozilgan satrning ixtiyoriy qism satrini belgilan nusxa olishi va satr oxiridan nusxani joylashi mumkin. Bu amal Zilolaga noqulaylik tug’dirmaydi

Zilola kamroq noqulaylik his qilish uchun ekran klaviaturasidan imkon qadar kamroq foydalanadi. Siz Zilola berilgan S satrni yozishi uchun Ekran klaviaturasidan eng kamida necha marta foydalanishi kerakligini aniqlang!

Kiruvchi ma'lumotlar:

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

Keyingi T ta satrda Zilola yozishi kerak bo’lgan so’z, S satr kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda S satrni yozish uchun Zilola ekran klaviaturasidan eng kamida necha marotaba foydalanishi kerakligini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
abcd
abab
 
4
2

C. Permutatsiya interactive

Xotira: 16 MB, Vaqt: 2000 ms
Masala

Kompyuter 1 dan N gacha bo’lgan sonlarning ixtiyoriy permutatsiyasidan A massivni hosil qildi, bu massiv 1 dan boshlab indekslangan. Sizga dastlab N soni beriladi va sizning vazifangiz A to’plam elementlarini ketma-ketligini aniqlashdan iborat. Buning uchun siz kompyuterdan “? u v” shaklda so’rov so’rashingiz mumkin, bunda u va v massiv indekslari bo’lib kompyuter sizga A[u] va A[v] orasidagi ishorani ya’ni ‘>’, ‘<’, ‘=’ belgilardan birini aytadi. Siz bu ko’rinishdagi so’rovdan ko’pi bilan 16*N marotaba foydalanishingiz mumkin, va oxirida ‘!’ belgisidan so’ng massiv elementlar ketma-ketligini chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N (1 \le N \le 10^5)\) soni kiritiladi. Keyingi satrlarda sizning so’rovingizga mos holda ‘>’, ‘<’, ‘=’ belgilari chiqariladi.

Chiquvchi ma'lumotlar:

Masala natijasini chop eting!

ESLATMA: Interaktiv masalada sizning javobingizni hakamlar hay’ati qabul qila olishi uchun siz har bir so’rovingiz oxirida

  • Agar Pascal tilida ishlagan bo’lsangiz: flush(output)
  • Agar C/C++ tilida ishlagan bo’lsangiz fflush(stdout) yoki cout.flush()
  • Agar Java tilida ishlagan bo’lsangiz System.out.flush()
  • Agar pythonda ishlagan bo’lsangiz sys.stdout.flush()
  • Agar C# tilida ishlagan bo’lsangiz Console.Out.Flush()

Buyruqlardan birini yozishingiz kerak bo’ladi!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
=
<
<
<
<
>
=
>
>
>
>
<
=
<
<
>
<
>
=
>
>
<
>
<
=
 
? 1 1
? 1 2
? 1 3
? 1 4
? 1 5
? 2 1
? 2 2
? 2 3
? 2 4
? 2 5
? 3 1
? 3 2
? 3 3
? 3 4
? 3 5
? 4 1?
? 4 2
? 4 3
? 4 4
? 4 5
? 5 1
? 5 2
? 5 3
? 5 4
? 5 5
! 1 5 2 4 3

D. Tic Tac Toe

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Tic Tac Toe qanday o’yin ekanligini barcha biladi. Shunday bo’lishiga qaramay yana bir eslatib o’tamiz:

  • Bu o’yin 3x3 jadvalda o’ylanadi. Dastlab jadval bo’sh bo’ladi;
  • O’yinni birinchi o’yinchi boshlab beradi va o’yin navbatma-navbat o’ynaladi;
  • Birinchi o’yinchi o’z navbati kelganida jadvaldagi bo’sh kataklardan biriga X belgisini qo’yadi;
  • Ikkinchi o’yinchi o’z navbati kelganida jadvaldagi bo’sh kataklardan biriga O belgisini qo’yadi;
  • O’yin bir to’g’ri chiziq bo’ylab (3 ta qator, 3 ta ustun, 2 ta diagonal) 3 ta O yoki 3 ta X bo’lib qolguniga qadar yoki jadvalda bo’sh joy qolmaguncha davom etadi.
  • Jadvalda ketma-ket 3 ta X bo’lsa X lar g’olib, ketma-ket 3 ta O bo’lsa O lar g’olib hisoblanadi.

Sizga o’yinning hozirgi holati berilgan. O’yin shu yerdan davom etganida birinchi o’yinchining yutish variantlar soni va ikkinchi o’yinchining yutish variantlar sonini chop eting. Natijaga erishish qadamlar ketma-ketligi farq qilganida ikkita natija har xil hisoblanadi.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10000)\) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun alohida 3 ta qatorda Tic Tac Toe o’yini jadvalining holati beriladi. Jadvalning bo’sh elementlari nuqta(‘.’) bilan ifodalanadi. Testlar orasi bo’sh qator bilan ajratilgan

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda o’yinnig hozirgi holatidan keyin davom ettirilganda necha xil variantda X lar g’olib bo’lishi va necha xil variantda Y lar g’olib bo’lishini chop eting!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
XX.
.O.
...

X..
.OX
...

OOO
X.X
.X.
 
191 194
232 200
0 1

E. Uchburchakli sonlar 4

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Uchburchakli sonlar teng tomonli uchburchakda joylashtirilgan jismlar sonidir (shu tariqa uchburchakli sonlar figurali sonlar turiga kiradi). N-chi uchburchakli son - bu yon tomonda n ta nuqta bo'lgan uchburchak tartibidagi nuqtalar soni va 1 dan n gacha bo'lgan n ta natural sonning yig'indisiga teng miqdorda nuqtadan iboratdir. Uchburchakli sonlar 1-tartibdan boshlanadi va dastlabki elementlari quyidagilardir:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666...

Quyida 1 dan 6 gacha tartibdagi uchburchakli sonlar ifodalangan:

https://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/First_six_triangular_numbers.svg/1024px-First_six_triangular_numbers.svg.png

Sizning vazifangiz berilgan N sonini aynan 3 ta uchburchakli sonlar yig’indisi shaklida yozish mumkin yoki yo’qligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

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

Keyingi \(T\) ta satrda har bir test uchun bitta butun son \(N (1 \le N \le 10^{18})\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylining yagona satrida N ta butun son (orasida hech qanday ajratgichlarsiz), har bir test uchun agar N soni yuqoridagi shartni qanoatlantirsa 1 aks holda 0 sonini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
10
20
1000
 
101

F. Ikki massiv

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Bizda N ta elementdan iborat ikkita teng uzunlikdagi A va B massiv bor. Ikkala massiv ham natural sonlardan tashkil topgan. A massiv B massivdan leksikografik jihatdan katta ekanligi ma’lum. Biz sizga B massiv elementlarini hamda quyidagi shaklda M ta solishtirish natijasini aytamiz:

  • \(u > v\) – bu \(A_u > A_v\) ni anglatadi
  • \(u < v\) – bu esa \(A_u < A_v\) ni anglatadi

Sizning vazifangiz berilgan shartlarni qanoatlantiradigan leksikografik eng kichik bo’lgan A to’plamni topishdan iborat.
 

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 5)\) testlar soni kiritiladi.
So’ng har bir test uchun quyidagi shaklda ma’lumotlar kiritiladi:
Birinchi satrda \(N(1 \le N \le 10^5)\) va \(M (0 \le M \le 10^5)\) sonlari kiritiladi.
Ikkinchi satrda \(N\) ta butun son, B massiv elementlari kiritiladi.
Keyingi \(M\) ta qatorda \(U (1 \le U \le N)\), ishora (‘>’ yoki ‘<’), \(V (1 \le V \le N, U \ne V)\) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda YES yoki NO, ya’ni A massivni hosil qilib bo’lsa YES aks holda NO so’zini chop eting. Agar javobingiz YES bo’lsa keyingi qatorda A massiv elementlarini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
3 2
1 2 3
1 > 2
1 < 3
3 2
1 2 3
1 > 2
1 < 2
3 0
1 2 3
 
YES
2 1 3
NO
YES
1 2 4

G. So’z o’yini

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Siz uzunligi bir xil bo’lgan (ko’pi bilan 4 uzunlik) faqat ingliz alifbosining kichik harflaridan tashkil topgan N ta so’zni shunday chop etingk, unda hech bir so’z ikki marta qatnashmasin hamda 2 – so’zdan boshlab qolgan barcha so’zlar o’zidan oldingi so’z bilan faqatgina 1 ta harfga farq qilsin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N (1 \le N \le 300000)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida masala shartini qanoatlantiradigan \(N\) ta so’zni har birini alohida qatorda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
 
aka
ata
ota
ona
ong
Kitob yaratilingan sana: 06-May-24 17:38