A. Kasrga almashtir

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga haqiqiy son beriladi, va uni eng oddiy (ya'ni, qisqarmas kasr) kasr shaklida ifodalashingiz kerak. 

Kiruvchi ma'lumotlar:

Haqiqiy son A beriladi, bu sonni o'nlik son (floating-point number) sifatida tasavvur qiling. \((1.0≤A≤10^6.0)\)

Chiquvchi ma'lumotlar:

Masala javobini kasr ko'rinishda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
0.5
 
1/2
2 
5
 
5/1
3 
1.3
 
13/10

B. Juftliklar soni #2

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga ikkita butun son A va B beriladi. Quyidagi shartlarni bajaruvchi ikki butun son x va y juftliklarining umumiy sonini toping:

  1. \(|x+y|\le A\)
  2. \(|x-y| \leq B\)

 

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1\le T \le 10^5)\)

Keyingi T ta qatorda A va B beriladi. \((0≤A,B≤10^{18})\)

Chiquvchi ma'lumotlar:

Topilgan qiymat juda katta bo'lishi mumkin, shuning uchun natijani \(10^9+7\) bo'lgandagi qoldiqni alohida qatorlarda chop eting.

Izoh:

1-testda
\((x,y)=(-1,0), (0,-1), (0,0), (0,1), (1,0)\) 5 ta qiymatda shartni qanoatlantiradi.

2-testda
\((x,y)=(-1,-1), (0,0), (1,1)\) 3 ta qiymatda shartni qanoatlantiradi.
 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
1 1
3 0
 
5
3

C. Kuchlarni tenglashtirish

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizga N ta o‘quvchi va ularning har birining bilim darajalari mavjud. Siz ushbu o‘quvchilarni 3 ta sinfga (A, B, C) ajratishingiz kerak. Ajratish shunday amalga oshirilishi kerakki:

A sinf bilim darajasi = B sinf bilim darajasi = C sinf bilim darajasi.

Kiruvchi ma'lumotlar:

Birinchi qatorda N — o‘quvchilar soni beriladi. \((2≤N≤100)\)

Ikkinchi qatorda N ta \(a_1, a_2, … ,a_N​\) — har bir o‘quvchining bilim darajasi beriladi. \((1≤a_i≤10^7)\).

Chiquvchi ma'lumotlar:

Agar o‘quvchilarni 3 ta sinfga teng bilim darajasi bilan bo‘lish mumkin bo‘lsa, "Ha", aks holda "Yo'q" so'zini chop eting.

Izoh:

1-testda

  • A sinf: 1 va 4
  • B sinf: 2 va 3
  • C sinf: 5

Shunda barcha sinf bilim darajasi teng bo'ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
1 2 3 4 5
 
Yes
2 
7
3 1 4 1 5 9 2
 
No
3 
9
729 756 767 778 792 804 816 831 855
 
Yes

D. Oltin

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizda N xil turdagi rudalar mavjud. Har bir turdagi rudaning miqdori \(A_1, A_2, ..., A_N\) bo'lib, siz ushbu rudalarni ishlatib maksimal miqdorda oltin quymasi ishlab chiqarishingiz kerak. Sizga quyidagi operatsiyalarni cheksiz miqdorda bajarish ruxsat etiladi:

  1. Rudani bir turdan ikkinchisiga o'tkazish:
    Istalgan ikki xil turdagi rudalar i va j uchun (1 ≤ i < j ≤ N), i turdagi rudadan 1 dona olib tashlanib, j turdagi rudaga 1 dona qo'shiladi.
  2. Oltin quymasi yaratish:
    Har bir turdagi rudalardan M dona olib, 1 dona oltin quymasi yaratish mumkin.

Oltin hosil qilgandan so'ng biror ruda qolib ketishi mumkin emas.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikki butun son N (rudalar turlari soni) va M (oltin quymasi uchun kerak bo'lgan minimal ruda miqdori) beriladi. \((1≤N≤2*10^5)\), \((1≤M≤10^9)\)

Ikkinchi qator N ta\( A_1, A_2, ..., A_N \)butun sonlar ketma-ketligi (har bir turdagi rudaning sonini ifodalaydi). \(0≤A _i  ≤10^ 9 \), \(1 ≤i≤ N\)

Chiquvchi ma'lumotlar:

Maksimal miqdorda hosil qilish mumkin bo'lgan oltin quymalarning sonini chop eting.

Izoh:

1-testda. 
1 va 5 ni olib 1 ga 5 dagi rudani qo'shsak 4, 3, 2, 3 hosil bo'ladi. Yana shuni davom ettrirsak 3, 3, 3, 3 hosil bo'ladi. Har biridan 3 tadan olib 1 dona oltin hosil qilish mumkin.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 3
5 3 1 3
 
1
2 
10 2
9 8 7 6 5 4 3 2 1 0
 
2

E. O'quvchi va shkaf

Xotira: 128 MB, Vaqt: 2500 ms
Masala

Maktabda N ta o'quvchi bor va har bir o'quvchiga 1 dan N gacha bo'lgan raqamlar berilgan. Maktabda N ta shkaf mavjud va har bir shkafning raqami 1 dan N gacha. Dastlab barcha shkaflar yopiq. O'quvchilar har biri o'z raqamiga mos keladigan qoidaga ko'ra shkaflarni ochib yoki yopib borishadi.

Qoidalar:

  • i-o'quvchi, i ning barcha bo'linuvchilari bo'lgan shkaflarni ochadi yoki yopadi. Agar shkaf yopiq bo'lsa, ochadi; agar ochiq bo'lsa, yopadi.
  • Har bir o'quvchi faqat o'z raqamiga mos bo'lgan shkaflar bilan ishlaydi. Masalan:
    • 1-o'quvchi barcha shkaflarni ochadi yoki yopadi.
    • 2-o'quvchi esa 2 ning bo'linuvchilariga (ya'ni 2, 4, 6, 8, ...) ishlaydi.

Biroq, ba'zi o'quvchilar operatsiyalarini bajarmagan bo'lishi mumkin. N ta o'quvchi operatsiyalarini amalga oshiradi, ammo M ta shkaf ochiq qolgan va ularning raqamlari \(A_1, A_2, ..., A_M\) berilgan.

Sizdan so'ralgan: M ta ochiq qolgan shkaflar asosida, qaysi o'quvchilar operatsiyalarini bajarmaganligini aniqlash. Bu o'quvchilarning sonini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^3)\)

Keyingi T ta qatorda:

     Birinchi qatorda ikkita butun son N va M beriladi.

          N Maktabdagi o'quvchilar va shkaflar soni. \((1 ≤ N ≤ 10^5)\)

          M Ochiq qolgan shkaflar soni. \((0 ≤ M ≤ N)\)

     Ikkinchi qatorda M ta butun sonlar \(A_1, A_2, ..., A_M\) beriladi. Bu raqamlar ochiq qolgan shkaflar raqamlaridir. \((1 ≤ Ai ≤ N\) va \(A_1 < A_2 < ... < A_M)\)

Chiquvchi ma'lumotlar:

Qaysi o'quvchilarning bajarmaganini aniqlang va ularning sonini chop eting.

Izoh:

Shkaflar: Barcha shkaflar yopiq. 0, 0, 0, 0 

2-o‘quvchi:

  • 2 ning bo‘linuvchilari: 2, 4 raqamli shkaflarni o‘zgartiradi.
  • Shkaflar: 0, 1, 0, 1 

4-o‘quvchi:

  • 4 ning bo‘linuvchilari: 4 raqamli shkafni o‘zgartiradi.
  • Shkaflar: 0, 1, 0, 0

Demak faqat 2-shkaf ochiq qoldi. 1 va 3 raqamli o'quvchilar ish bajarmadi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
4 1
2
10 5
2 4 5 8 9
 
2
6

F. Ketma-ketlik 2

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga quyidagicha ketma-ketlik betilgan:

\(a_1=1\)

\(a_2=3\)

\(...\)

\(a_n=4a_{n-1}-4a_{n-2}+2^n\)

Sizga \(n\) butun soni berilgan. Siz \(a_n\) ning qiymatini \(10^9+7\) ga bo'lgandagi qoldiqni chop etishingiz kerak bo'ladi.

Kiruvchi ma'lumotlar:

Yagona qatorda \(n\) natural soni \(n(1≤n≤10^{18}).\)

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimi \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
 
3
2 
4
 
68

G. O'rin almashtirishlar soni

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan tashkil topgan \(A\) massiv berilgan. Siz quyidagi amalni istalgancha bajarishingiz mumkin. 

  • Istalgan elementni qo'shni element bilan almashtira olasiz.

Siz bu amalni minimal marta bajarib turib massivdagi hamma bir xil elementlarni yonma-yon joylashtirishingiz kerak. 

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(N(3≤N≤10^6).\)

Keyingi qatorda \(N\) ta butun son \(A_i(1≤A_i≤16).\)

Chiquvchi ma'lumotlar:

Ekranga minimal amallar sonini chop eting.

Izoh:

Birinchi test uchun izoh:

[1,2,1,4,4,3,4] massivi berilgan.

  1. [2,1,1,4,4,3,4] shu holatga keladi.
  2. [2,1,1,4,4,4,3] keyin shu holatga keladi.

Natijada minimal amallar soni 2 bo'ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
7
1 2 1 4 4 3 4
 
2
2 
6
5 4 2 4 3 2
 
2
Kitob yaratilingan sana: 22-Feb-25 21:36