A. Jahonali va tangalar

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Jahonalida n ta tanga bo'r. Har bir tanganing bahosi 1 yoki 2 sum. Jahonalida nechta turli boylikga ega bolishi mumkin?

Kiruvchi ma'lumotlar:

Yagona qatorda n soni (1≤n≤100)(1 \le n \le 100)

Chiquvchi ma'lumotlar:

Jahonalida nechta turli boylikga ega bolishini chop eting.

Izoh:

Birinchi testda n=1n=1 uchun, ikkita holat bo'r, 1 yoki 2 bahoda tangalar.

Ikkinchi testda, 3 turli holat bo'r, 1+1=21 + 1 = 2, 1+2=31 + 2 = 3, 2+2=42 + 2 = 4

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

B. JahORnali (Easy)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Ikki masalaning yagona farqi, n ga chegara bolib hisoblanadi (bunda n ≤ 200)

 

Jahonali zerikganidan quydagicha masala tuzdi:

Sizga uzunligi nn bolgan aa massivi va kk soni berilgan. Siz shunaqa eng uzun segment topishingiz kerak, uning bitwise OR i kk dan oshmaydigandek.

Bo'shqacha aytganda, shunaqa 1≤l≤r≤n1\le l \le r \le n  tanglashingiz kerak, al∣al+1∣...∣ar−1∣ar≤ka_l | a_{l+1} |... | a_{r-1}|a_r \le k va r−l+1r - l + 1 ning qiymati eng maximum bo'lishi kerak. Agar javob yo'q bolsa, 0 ni chop eting.

Kiruvchi ma'lumotlar:

Birinchi qatorda n va k sonlari (1≤n≤200,1≤k≤216)(1 \le n \le 200, 1 \le k \le 2^{16})

Ikkinchi qatorda n ta son (1≤Ai≤216)(1 \le A_i \le 2^{16})

Chiquvchi ma'lumotlar:

Shartni o'rinlaydigan eng uzun segmentni uzunligi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
14 45
56 47 97 87 10 79 7 33 48 7 77 30 3 5
 
3

C. JaXORnali

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga uzunligi nn bolgan AA massivi berilgan. Yana bir BB massivi bo'r. U quydagicha yaratiladi: har bir 1≤i≤n1\le i \le n uchun Bi=2AiB_i = 2^{A_i}.

Sizning maqsadingiz BB massivini XORini 0 ga tenglashtirish. Uning uchun siz bir amalda BB massivini hohlagan elementini 2 ga kopaytira olasiz.

Kiruvchi ma'lumotlar:

Birinchi qatorda n soni (1≤n≤2⋅105)(1\le n \le 2 \cdot10^5)

Keyingi qatorda A massivi (0≤Ai≤60)(0\le A_i \le 60)

Chiquvchi ma'lumotlar:

BB massivni XORini 0 ga tenglashtirish uchun kerak bolgan amallar soni. Agar ishlab bolmasa, -1 ni chop eting.

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

D. JahORnali (Hard)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Ikki masalaning yagona farqi, n ga chegara bolib hisoblanadi (bunda n ≤ 200000)

 

Jahonali zerikganidan quydagicha masala tuzdi:

Sizga uzunligi nn bolgan aa massivi va kk soni berilgan. Siz shunaqa eng uzun segment topishingiz kerak, uning bitwise OR i kk dan oshmaydigandek.

Bo'shqacha aytganda, shunaqa 1≤l≤r≤n1\le l \le r \le n  tanglashingiz kerak, al∣al+1∣...∣ar−1∣ar≤ka_l | a_{l+1} |... | a_{r-1}|a_r \le k va r−l+1r - l + 1 ning qiymati eng maximum bo'lishi kerak. Agar javob yo'q bolsa, 0 ni chop eting.

Kiruvchi ma'lumotlar:

Birinchi qatorda n va k sonlari (1≤n≤2⋅105,1≤k≤216)(1 \le n \le 2\cdot10^5, 1 \le k \le 2^{16})

Ikkinchi qatorda n ta son (1≤Ai≤216)(1 \le A_i \le 2^{16})

Chiquvchi ma'lumotlar:

Shartni o'rinlaydigan eng uzun segmentni uzunligi.

Misollar:
# INPUT.TXT OUTPUT.TXT

E. Jahonali va torburchaklar

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Jahonali o'z yolida NxM tortburchakni uchiratdi. U boshida shu tortburchakning ichida nechta tortburchak bo'r ekanligin to'pmoqchi edi. Agar masala shu bilan tamomlanganda, masala juda oson bo'lar edi, shuning uchun qoshimcha 2 ta qora dog' bo'r.

Sizning maqsadingiz, shu tortburchakning ichiga nechta turli tortburchak qora dog'ni ichiga olmaydiganin topish.

Bo'shqacha aytganda, nechta turli 1≤X1,X2≤N1 \le X_1, X_2 \le N va 1≤Y1,Y2≤M1\le Y_1, Y_2 \le M (X1≤X2,Y1≤Y2)(X_1 \le X_2, Y_1 \le Y_2) tanglasa boladi, hech qanaqa X1≤i≤X2X_1 \le i \le X_2 va Y1≤j≤Y2Y_1 \le j \le Y_2 uchun (i,j)(i, j) qora dog' bolmaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va M sonlari (2≤N,M≤100)(2\le N, M \le 100)

Keyingi ikki qatorda X va Y, qora dog'lar koordinatalari (1≤X≤N,1≤Y≤M)(1\le X \le N, 1 \le Y \le M)

Ikki turli koordinata berilishi kafolatlanadi.

Chiquvchi ma'lumotlar:

NxM torburchakning ichida qora dog'ni ichiga olmaydigan to'rtburchaklar soni.

Izoh:

Birinchi testda, 2 ta tortburchak bo'r, [(1, 1), (1, 1)] va [(2, 2), (2, 2)]

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 2
1 2
2 1
 
2

F. Sanash o'tmaydi

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Jahonali o'z yolida NxM tortburchakni uchiratdi. U boshida shu tortburchakning ichida nechta tortburchak bo'r ekanligin to'pmoqchi edi. Agar masala shu bilan tamomlanganda, masala juda oson bo'lar edi, shuning uchun qoshimcha 2 ta qora dog' bo'r.

Sizning maqsadingiz, shu tortburchakning ichiga nechta turli tortburchak qora dog'ni ichiga olmaydiganin topish.

Bo'shqacha aytganda, nechta turli 1≤X1,X2≤N1 \le X_1, X_2 \le N va 1≤Y1,Y2≤M1\le Y_1, Y_2 \le M (X1≤X2,Y1≤Y2)(X_1 \le X_2, Y_1 \le Y_2) tanglasa boladi, hech qanaqa X1≤i≤X2X_1 \le i \le X_2 va Y1≤j≤Y2Y_1 \le j \le Y_2 uchun (i,j)(i, j) qora dog' bolmaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va M sonlari (2≤N,M≤1000)(2\le N, M \le 1000)

Keyingi ikki qatorda X va Y, qora dog'lar koordinatalari (1≤X≤N,1≤Y≤M)(1\le X \le N, 1 \le Y \le M)

Ikki turli koordinata berilishi kafolatlanadi.

Chiquvchi ma'lumotlar:

NxM torburchakning ichida qora dog'ni ichiga olmaydigan to'rtburchaklar soni.
javobni 109+710^9+7 ga bo'lgandagi qoldiqni chop eting

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 2
1 2
2 1
 
2
Kitob yaratilingan sana: 20-Jul-25 09:00