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 \le n \le 100)\)

Chiquvchi ma'lumotlar:

Jahonalida nechta turli boylikga ega bolishini chop eting.

Izoh:

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

Ikkinchi testda, 3 turli holat bo'r, \(1 + 1 = 2\), \(1 + 2 = 3\), \(2 + 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 \(n\) bolgan \(a\) massivi va \(k\) soni berilgan. Siz shunaqa eng uzun segment topishingiz kerak, uning bitwise OR i \(k\) dan oshmaydigandek.

Bo'shqacha aytganda, shunaqa \(1\le l \le r \le n\) tanglashingiz kerak, \(a_l | a_{l+1} |... | a_{r-1}|a_r \le k\) va \(r - 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 \le n \le 200, 1 \le k \le 2^{16})\)

Ikkinchi qatorda n ta son \((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 \(n\) bolgan \(A\) massivi berilgan. Yana bir \(B\) massivi bo'r. U quydagicha yaratiladi: har bir \(1\le i \le n\) uchun \(B_i = 2^{A_i}\).

Sizning maqsadingiz \(B\) massivini XORini 0 ga tenglashtirish. Uning uchun siz bir amalda \(B\) massivini hohlagan elementini 2 ga kopaytira olasiz.

Kiruvchi ma'lumotlar:

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

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

Chiquvchi ma'lumotlar:

\(B\) 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: 1024 MB, Vaqt: 1000 ms

Masala

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

Jahonali zerikganidan quydagicha masala tuzdi:

Sizga uzunligi \(n\) bolgan \(a\) massivi va \(k\) soni berilgan. Siz shunaqa eng uzun segment topishingiz kerak, uning bitwise OR i \(k\) dan oshmaydigandek.

Bo'shqacha aytganda, shunaqa \(1\le l \le r \le n\) tanglashingiz kerak, \(a_l | a_{l+1} |... | a_{r-1}|a_r \le k\) va \(r - 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 \le n \le 2\cdot10^5, 1 \le k \le 2^{16})\)

Ikkinchi qatorda n ta son \((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 \le X_1, X_2 \le N\) va \(1\le Y_1, Y_2 \le M\) \((X_1 \le X_2, Y_1 \le Y_2)\) tanglasa boladi, hech qanaqa \(X_1 \le i \le X_2\) va \(Y_1 \le j \le Y_2\) uchun \((i, j)\) qora dog' bolmaydi.

Kiruvchi ma'lumotlar:

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

Keyingi ikki qatorda X va Y, qora dog'lar koordinatalari \((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 \le X_1, X_2 \le N\) va \(1\le Y_1, Y_2 \le M\) \((X_1 \le X_2, Y_1 \le Y_2)\) tanglasa boladi, hech qanaqa \(X_1 \le i \le X_2\) va \(Y_1 \le j \le Y_2\) uchun \((i, j)\) qora dog' bolmaydi.

Kiruvchi ma'lumotlar:

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

Keyingi ikki qatorda X va Y, qora dog'lar koordinatalari \((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 \(10^9+7\) ga bo'lgandagi qoldiqni chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2 1 2 2 1	2