A. Count

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga \(N\) va \(M\) butun sonlari berilgan. Uzunligi \(N\) ga teng bo'lgan \(A1\) massiv, uzunligi \(M\) ga teng bo'lgan \(A2\) massiv berilgan. \(A1\) massivda qatnashgan manfiy elementlar sonidan, \(A2\) massivda qatnashgan musbat elementlar sonini ayrishingiz kerak bo'ladi. Agar natija manfiy bo'lsa, \(-1\) sonini chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(2\) ta natural son. \(N,M(1≤N,M≤10^6).\)

Ikkinchi qatorda uzunligi \(N\) ga teng bo'lgan \(A1\) massiv elementlari bitta probel bilan ajratgan holda kiritiladi. \(A1[i](-10^6≤A1[i]≤10^6).\)

Uchinchi qatorda uzunligi \(M\) ga teng bo'lgan \(A2\) massiv elementlari bitta probel bilan ajratgan holda kiritiladi. \(A2[i](-10^5≤A2[i]≤10^5).\)

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT

B. Bo'luvchilar soni

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga \(N\) natural soni berilgan. Sizning vazifangiz uning natural bo’luvchilarining sonini topishdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) soni berilgan. \(N(1≤N≤10^9).\)

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6	4
2	94	4

C. Noyob sonlar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga bir o’lchamli sonli massiv berilgan. Massivdagi sonlar takrorlanib kelishi mumkin. Massivda bir marta qatnashgan (takrorlanmaydigan) sonlar – Noyob sonlar deyiladi. Sizdan massivdagi Noyob sonlar sonini hisoblab topuvchi dastur tuzish talab etiladi.

Kiruvchi ma'lumotlar:

Birinchi satrda \(n (1 ≤ n ≤ 10^6)\). Ikkinchi satrda \(n\) ta butun son \((-10^5 ≤ a[i] ≤ 10^5)\).

Chiquvchi ma'lumotlar:

Yagona satrda Noyob sonlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 6 3 -3 -7 -5 -4 7	7
2	4 -4 -3 3 -2	4

D. Do'stona juftliklar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Yo'ldosh, Shavkat va G'iyos topib olingan massivdagi do’stona juftliklarni aniqlashga qaror qilishdi. \(a\) massiv indekslari \(1\) dan \(n\) gacha nomerlangan. \(a[i]\) va \(a[j] \)juftliklar do’stona bo’lish uchun Yo’ldosh \(a[i] \) \(mod \) \(a[j]=0\)(\(mod\) qoldiq olish amali), G'iyos \(i\) \( mod \) \(j=0\), Shavkat esa \(i > j\) bo’lishi kerak dedi. Ularga uchalasining shartini qanoatlantiradigan juftliklar sonini topishda yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) massiv elementlari soni berilgan\((1≤n ≤10^5).\) Ikkinchi qatorda \(n\) ta butun son massiv elementlari bitta probel bilan ajratilgan holda berilgan. Massiv elementlari qiymatlari \(1\) dan \(10^5+1\) gacha bo’ladi.

Chiquvchi ma'lumotlar:

Do’stona juftliklar sonini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 76 67 82 1 75	0
2	3 51 9 12	0
3	6 2 3 5 6 10 6	5

E. Minimal yig'indi

Xotira: 128 MB, Vaqt: 1000 ms

Masala

To'rtburchak \(NxM\) jadval(har bir katakchada ma'lum bir son yozilgan) berilgan. O'yin boshida o'yinchi \((1,1)\) katakchada joylashgan. Bir harakatda unga qo'shni katakchaga o'ngga yoki pastga o'tishga ruxsat beriladi (chapga va yuqoriga o'tish ta'qiqlanadi). Katakchadan o'tayotganda o'yinchi ushbu katakchada yozilgan miqdorda pul to'laydi (u yo'lining birinchi va oxirgi kataklarida ham pul to'laydi). O'yinchi minimal qancha xarajat bilan \((N,M)\) katakchaga bora oladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(M,N\) butun sonlari \(N,M(1≤M,N≤5*10^3)\).

Keyingi \(M\) ta qatorda har birida \(N\) tadan son bo'lgan \(A[]\) matritsa berilgan \(A[i][j] (0<A[i][j]<10^5).\).

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 5 4 4 3 5 4 1 2 1 5 5 4 4 4 4 5 4 6 1 1 2 4 4 5 6 4 1 1 2 3 1	21
2	3 10 3 1 2 3 1 2 3 2 3 2 3 2 3 3 1 1 1 1 3 1 2 3 2 1 1 3 1 1 1 1	17

F. Qiziqarli topshiriq

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Mening do'stim Shohruh tub sonlarni topishda turli xil algoritmlar o`rgandi. U endi juda katta tub sonlarni ham tezda topa oladi. Endi u o`z bilimiga ishongan holda do`sti Qudrat uchun topshiriq tayorlashga kirishdi va uzoq hisob – kitoblardan so`ng topshiriqni tayorladi. U Hasanboyga qiymati juda katta bo`lgan \(p\) tub son aytadi. Hasanboy esa shunday \(k\) son aytishi kerakki quyidagi ifodadan butun musbat son chiqishi kerak.\(\sqrt{k^2 - pk}\). Shohruh shunga ishonadiki bu ifodani yagona qiymat qanoatlantiradi. Javob yetarlicha katta bo`lishi mumkin. Shuning uchun javobni \(10^9+7\) ga bo`lgandagi qoldiqi so`raladi.

Hasanboyga ifodani qiymatini topishda yordam bering

Kiruvchi ma'lumotlar:

Yagona qatorda \(p\) –> tub soni. \(p(3 ≤ p ≤10^{18})\).

Chiquvchi ma'lumotlar:

Yagona qatorda shartni qanoatlantiruvchi bitta butun \(k\) sonini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3	4

G. Ketma-ketlik

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Talaba elementlari \(1\) dan \(n\) gacha bo’lgan har xil sonlardan tashkil topgan \(A\) ketma – ketlikni topib oldi. Oldiniga hamma elementlari o’z o’rnida turgandi (ya’ni \(A[i] = i\)). U elementlarini o’rnini almashtirib tashladi. Sizni vazifangiz ketma – ketlikni lekrikogarfik jihatdan nechanchi ekanligini aniqlab berish. Javob juda kata bo’lishi mumkin, shuning uchun \(10^9+7\) ga bo’lgandagi qoldig’ini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) soni. \((1 ≤ n ≤ 10^5);\) Keyingi qatorda \(1\) dan \(n\) gacha sonlardan iborat ketma – ketlik.

Chiquvchi ma'lumotlar:

Yagona qatorda javobni \(10^9+7\) ga bo’lgandagi qoldig’ini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 1 4 2	14
2	3 3 2 1	6