A. Sumka yoki knapsack

Xotira: 25 MB, Vaqt: 1000 ms

Masala

Sizga $n$ va $c$ summa beriladi. $n$ ta elementdan iborat $v$ , $w$ to'plam beriladi. $i$ uchun $(0 \le i \le n-1)$ $v[i]$ - qiymat , $w[i]$ - og'irlik. Sizning vazifangiz maksimal qiymat tanlashingiz kerak bo'ladiki, ularga mos og'irliklar yig'indisi summadan oshmasin.

Kiruvchi ma'lumotlar:

Birinchi qatorda $n(1 \le n \le 10^3)$ va $c(0 \le c \le 2*10^6)$ beriladi.
Ikkinchi qatorda $n$ ta son $v_0 , v_1, \dots, v_{n-1}$ $(0 \le v_i \le 50)$ .
Uchinchi qatorda $n$ ta son $w_0, w_1, \dots , w_{n-1}$ $(0 \le w_i \le 50)$ .

Chiquvchi ma'lumotlar:

Chiqishda bir qatorda siz tanlashingiz mumkin bo'lgan maksimal qiymat.

Izoh:

Birinchi test uchun biz tanlashimiz mumkin maximal qiymat 25ga teng.
(10+15) ularga mos og'irliklar yig'indis (10+5) u 20 dan katta emas.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 20 10 15 6 4 10 5 10 10	25

B. Eng katta ko'paytma

Xotira: 24 MB, Vaqt: 1500 ms

Masala

Sizga doskada $N$ soni berilgan sizning vazifangiz quyidagi amallarni bajargan holda eng katta ko'paytmaga erishish.

$N$ sonini o'chirib uni o'rniga ;
Agar $N$ juft bo'lsa $[ \cfrac{N}{2}]$ $[ \cfrac{N}{2}]$ ni yozamiz.

Agar $N$ toq bo'lsa $[ \cfrac{N+1}{2}]$ $[ \cfrac{N}{2}]$ ni yozamiz.

Bu ammallarni doskadagi har bir son uchun bir necha marotaba qilishimiz mumkin.

Kiruvchi ma'lumotlar:

Bir qatorda $N$ soni $(1 \le N < 10^{18}).$

Chiquvchi ma'lumotlar:

Doskadagi hosil bo'lishi mumkin bo'lgan sonlarning ko'paytmasini $99824353$ ga bo'lgandagi qoldiq.

Izoh:

$N=15$ bo'lganda.

$N=15$ ni o'rnga $7$ va $8$ ni yozamiz . $[7,8]$

$7$ ni o'rniga $3$ va $4$ ni yozamiz. $[3,4,8]$

$4$ ni o'rniga $2$ va $2$ ni yozamiz $[3,4,8]$

$8$ ni o'rniga $4$ va $4$ ni yozamiz $[3,2,2,4,4]$

Doskada 3 2 2 4 4 hosil bo'ldi . Bu sonlarnig ko'paytmasi $(192)$ maksimal.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	15	192

C. O'yin

Xotira: 20 MB, Vaqt: 1000 ms

Masala

Shahzod va Sardor o'yin o'ynashmoqda. Bu o'yinni Sardor $n$ ta elementdan iborat $A$ to'plam bilan boshlaydi.

Har bir urinishda ishtirokchilar $0$ ga teng bo'lmagan bir xil massiv elementlarini tanlab o'chiradi.

Kimni navbatida $A$ to'plam bo'sh bo'lsa o'sha odam yutadi.

Shahzood aqlli bo'lgani uchun u o'yinga yangi shart kiritmoqchi edi. U shart quyidagidan iborat. Shahzod to'plam ichidan istalgancha sonni olib tashlashi $(0 ta$ ham $)$ mumkin.

Bu o'yinda Shahzod yutushi kerak. U necha xil xolatda o'yinda yutib chiqadi.

Kiruvchi ma'lumotlar:

1-qatorda $t (1 \le t \le 10)$ testlar soni.

Har bir test uchun 1-qatorda $n(1 \le n \le 2*10^5)$ 2-qatorda $a$ to'plam elementlari bo'sh joy bilan ajratilgan holda kiritiladi $(1 \le a_i \le 10^{18}).$

Chiquvchi ma'lumotlar:

Har bir test uchun Shahzod yutishi mumkin bo'lgan holatlar sonini $10^9+7$ ga bo'lgandagi qoldiq.

Izoh:

1-test uchun.

1 1 2 2 3 bu massiv uchun 2 xil holat bor.

1. Hech qanday son o'chirmaymiz.

2. 1 2 ni o'chiramiz.

Misollar:

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

D. Labirintdagi yo'llar soni.

Xotira: 20 MB, Vaqt: 1000 ms

Masala

Sizga $N*M$ 0 va 1 lardan iborat labirint beriladi. labirintda eshigi ochiq(0) va yopiq(1) xonalar mavjud.

Bu labirintda siz quyidagi amallarni bajarishngiz mumkin.

1.Labirintning satrdagi keyingi eshigi ochiq bo'lgan xonaga o'tishingiz mumkin.

2.Labirintning ustunidagi keyingi eshigi ochiq bo'lgan xonaga o'tishingiz mumkin.

Ushbu amallarni bajargan holda labirintning $(1,1)$ xonasidan $(N,M)$ xonasiga borishning usullar soni hisoblang.

Kiruvchi ma'lumotlar:

1-qatorda $N$ va $M$ $(1 \le N,M \le 1000)$ .

$N$ ta ustunda xonalardan iborat uzunligi $M$ ga teng satrlar.

Chiquvchi ma'lumotlar:

$(N,M)$ xonaga borish usullar sonini $10^9+7$ ga bo'lgandagi qoldiq.

Izoh:

000
011
000 bu labirint uchun yo'llar soni.

$1. (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)$

$2. (1,1) -> (1,2) -> (3,2) -> (3,3)$

$3. (1,1) -> (1,2) -> (1,3) -> (3,3)$

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 000 011 000	3

E. Ajoyib juftliklar soni.

Xotira: 20 MB, Vaqt: 1000 ms

Masala

Siz ga $n$ ta qatorda binar satrlar berilgan. $2$ ta satrda kamida bitta belgi ummumiy bo'lsa u satrlar ajoyib juftlik hisoblanadi.

Sizning vazifangiz $n$ ta satr ichidan ajoyib juftliklar sonini topish.

Kiruvchi ma'lumotlar:

1-qatorda $T(1 \le T \le 10000)$ testlar soni.

Har bir test uchun bir qatorda $N(1 \le N \le 100000)$ va keyingi $N$ ta qatorda binar satrlar $(1 \le |satr| \le 5).$

Chiquvchi ma'lumotlar:

Har bir test uchun ajoyib juftliklar soni.

Izoh:

01
1111
0001
11
01

har bir satrda 1 umumiy. juftliklar soni esa $(5-1)*5/2=10$ ta

11
00
00000

2 - va 3- satrlar umumiy 0 ga ega demak 1 ta.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 3 11 00 00000	1

F. Subsequense

Xotira: 24 MB, Vaqt: 1000 ms

Masala

Satrning subsequense deb satr istalgancha belgi o'chirib yoki o'chirmasdan hosil bo'ladigan satr. Masalan "abcd" satrning subsequencelari "abcd","abc","abd","ab","acd","ac","ad","a","bcd","bc","bd","b","cd","c","d" shular.

Murrakkab son deb barcha subsequencelari yig'indisi toq bo'lgan songa aytiladi.

Sizning vazifangiz shunday $l$ va $r$ oraliqda topishingiz kerakki bu oraliqdagi murakkab sonlar $k$ ta bo'lsin. Bunaqa oralig'lar bir nechta bo'lsa $l$ minimal bo'lganini chiqaring.

Kiruvchi ma'lumotlar:

1-qatorda $T(1 \le T \le 10^5)$ testlar soni.

Har bir test uchun bir qatorda $k (1 \le k \le 10^5)$ soni beriladi.

Chiquvchi ma'lumotlar:

Har bir test uchun $l$ va $r$ ni probel bilan ajratgan holda chiqaring, bunaqa oraliq mavjud bo'lmasa -1 -1 ni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 5	1 1 1 9

G. Rangli kataklar.

Xotira: 24 MB, Vaqt: 1000 ms

Masala

Mironshoh $N*N$ to'rga va qizil bo'yoqga ega. U to'r chiroyli bo'lishi uchun $(i,j)$ katakni bo'yashi kerak agar $i+j$ tub bo'lsa $(0 \le i,j \le n-1)$ . U shunaqa tartibda kataklarni bo'yab chiqdi.

U bo'yagandan keyin nechta rangli kataklar bo'lganini topish.

Kiruvchi ma'lumotlar:

Bir qatorda $N(1 \le N \le 1000000)$ soni.

Chiquvchi ma'lumotlar:

Bo'yalgan kataklar sonini $10^9+7$ ga bo'lgandagi qoldiq.

Izoh:

n=3 bo'lganda

0-bo'sh kataklar 1-bo'yalgan kataklar.

000 001

000 011

000 110

$(0,2) (1,1) (1,2) (2,0) (2,1)$ shu kataklar bo'yaladi chunki i+j larni yig'indisi tub.

Misollar:

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

H. Massivlar soni.

Xotira: 240 MB, Vaqt: 1000 ms

Masala

Sizga n , n ta son $a_1,a_2,a_3...a_n$ va p tub son beriladi. Sizning vazifangiz $y ( y_1 , y_2 , y_3...y_n)$ to'plamlar sonini topingki ular quyidagi shartlarni bajarsin

1. $(1 \le i \le n) 0 \le y_i \le a_i.$

2. $\begin{pmatrix} y_1 + y_2 + \dots + y_n \\ y_1, y_2, y_3, \dots, y_n \end{pmatrix} mod \ p = 0$ (bu yerda mod qoldiq degani). Agar bu narsaga tushunmagan bo'lsangiz bu linkni bosing.

Bu son juda katta bo'lishi shuning uchun uni $10^9+7$ ga bo'lgandagi qoldiqqa tenglang.

Kiruvchi ma'lumotlar:

Birinchi qatorda $n(1 \le n \le 11)$ va $p(1 \le p \le 10^6)$ beriladi.

Keyingi qatorda n ta son $a_1,a_2,a_3...a_n$ $(1 \le a_i\le10^9)$ .

Chiquvchi ma'lumotlar:

$y$ to'plamlar sonini $10^9+7$ ga bo'lgandagi qoldiqni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 1 3 2 4	76

I. Qism satrlar soni

Xotira: 24 MB, Vaqt: 1000 ms

Masala

Sizga $s$ satr beriladi. Sizning vazifangiz bu massivni qismsatrlar sonini toping.

Kiruvchi ma'lumotlar:

Bir qatorda $s(1 \le |s| \le 10^5)$ .

Chiquvchi ma'lumotlar:

Bir qatorda qism satrlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	a	1

J. Function

Xotira: 24 MB, Vaqt: 1000 ms

Masala

Sizga ushbu psevdo kod berilgan.

Sizning vazifangiz $function(p,q,r)$ ni hisoblash.

Kiruvchi ma'lumotlar:

Birinchi qatorda $t(1 \le t \le 10)$ testlar soni .

$t$ ta qatorning har birida $p,q (1 \le p,q \le 10000)$ , $r(2 \le r \le 5)$ .

Chiquvchi ma'lumotlar:

$function(p,q,r)$ ni qandaydir $\cfrac {n} {m}$ deb olsak , siz $(n*m^{-1}) \%(10^9+7)$ (bu inverse mod) shu qiymatni chiqaring.

Izoh:

Bizning natijamiz $\cfrac{15}{46}$ bo'lsa undan inverse mod olsak 543478265 ga teng.

Misollar:

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

K. ASCII

Xotira: 2 MB, Vaqt: 1000 ms

Masala

Sizga ASCII jadvalidan bitta belgi beriladi siz uning u jadvaldan nechanchi o'rinda turishini yoping.

Kiruvchi ma'lumotlar:

ASCII dagi belgilardan biri.

Chiquvchi ma'lumotlar:

Berilgan belgining nechanchi o'rinda turganligi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	a	97