A. Begona sonlar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, sizda 1 dan \(N\) gacha sonlar bor. \(A\) soniga yoki \(B\) soniga bo'linadigan sonlar "Begona" sonlardir. Sizning vazifangiz: 1 dan \(N\) gacha bo‘lgan sonlarning ichida nechta "Begona" bo'lmagan sonlar borligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda N natural son beriladi. \((1≤N≤10^{18})\)

Ikkinchi qatorda natural A va B sonlar beriladi. \((1≤A≤B≤10^9)\)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	24 3 11	14

B. LED chiroqlar

Xotira: 32 MB, Vaqt: 1111 ms

Masala

N ta yashil LED lampasi bor, ular 1 dan N gacha raqamlangan. Boshlang‘ich holatda barcha LEDlar yashil rangda yonmoqda. Maqsad — ularning barchasini qizil rangga o‘zgartirish.

Har bir LEDda bitta tugma bor. Tugmani bosganingizda quyidagi o‘zgarish sodir bo‘ladi:

Agar LED yashil bo‘lsa, sariq rangga o‘tadi.
Agar LED sariq bo‘lsa, qizil rangga o‘tadi.
Qizil LED da hech qanday amal bajarilmaydi ya'ni qizil holida qoladi..

LEDlarning rangini o‘zgartirish amallari ketma-ketligi quyidagicha bajariladi:

Har bir amalda bittagina LED tanlanib, uning tugmasi bosiladi.
Har bir LED tugmasi ikki marta bosilishi kerak: birinchi bosishda yashildan sariqqa, ikkinchi bosishda sariqdan qizilga o‘tadi.
Tugmani bosish tartibi erkin tanlanadi, ammo har bir LED tugmasi faqat ikki marta bosilishi mumkin (va ketma-ketlikda yashil → sariq → qizil ketma-ketligi saqlanishi shart).
Barcha LEDlar qizil rangga o‘tgan holatni olish uchun barcha amallar bajarilishi lozim.

Barcha mumkin bo‘lgan amallar ketma-ketliklarining sonini topish dasturini tuzing.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son N \((1 ≤ N ≤ 10^8)\) LED chiroqlar soni beriladi.

Chiquvchi ma'lumotlar:

Masala javobini \(10^9+7\) ga bo‘lgandagi qoldiqni chop eting.

Izoh:

1-tesda N=2 bo‘lgandagi amallar tartiblari:

1)「1 ni sariqqa o‘zgartirish」「1 ni qizilga o‘zgartirish」「2 ni sariqqa o‘zgartirish」「2 ni qizilga o‘zgartirish」

2) 「2 ni sariqqa o‘zgartirish」「2 ni qizilga o‘zgartirish」「1 ni sariqqa o‘zgartirish」「1 ni qizilga o‘zgartirish」

3)「1 ni sariqqa o‘zgartirish」「2 ni sariqqa o‘zgartirish」「1 ni qizilga o‘zgartirish」「2 ni qizilga o‘zgartirish」

4)「1 ni sariqqa o‘zgartirish」「2 ni sariqqa o‘zgartirish」「2 ni qizilga o‘zgartirish」「1 ni qizilga o‘zgartirish」

5) 「2 ni sariqqa o‘zgartirish」「1 ni sariqqa o‘zgartirish」「1 ni qizilga o‘zgartirish」「2 ni qizilga o‘zgartirish」

6)「2 ni sariqqa o‘zgartirish」「1 ni sariqqa o‘zgartirish」「2 ni qizilga o‘zgartirish」「1 ni qizilga o‘zgartirish」

jami 6 xil.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2	6

C. Leksikografik musobaqa #1: Imonaga yordam ber!

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Kichkina Imona sirli sovg‘alarni juda yaxshi ko‘radi. Onasi unga tug‘ilgan kunida ikkita uzunlikdagi satr — g‘alati sehrli kodlarni sovg‘a qildi. Bu satrlar faqat lotin alifbosidagi katta va kichik harflardan iborat ekan!

Hoziroq Imona bu kodlarni leksikografik tarzda solishtirmoqchi. Imona uchun bu qiyin vazifa bo'lib chiqdi. Siz unga yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida ikki qatorda satr beriladi. Har bir satr uzunligi 1 dan 100 gacha bo‘ladi. Satrlar teng uzunlikka ega va faqat lotin alifbosining katta hamda kichik harflaridan iborat.

Chiquvchi ma'lumotlar:

Agar birinchi satr ikkinchisidan kichik bo‘lsa, -1 chiqaring.
Agar ikkinchi satr birinchisidan kichik bo‘lsa, 1 chiqaring.
Agar satrlar teng bo‘lsa, 0 chiqaring.

Izoh:

'A' bilan 'a' — biri-biriga aynan teng deb olinsin !

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	Imona Oysha	-1
2	Oy Men	1
3	Mehr Yer	-1

D. Antiqa funksiya

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Quyida \(F(n)\) funksiyaning qiymatini hisoblash algoritmi berilgan. Bunda \(n\) natural son bo‘lib, quyidagi munosabatlar bilan berilgan:

\(F(0)=0\);
\(F(n)=F(n/2)\), agar \(n>0\) va juft son;
\(F(n)=1+F(n−1)\), agar \(n\) toq son.

Savol: \(1≤n≤N\) oraliqda \(F(n)=K\) bo‘ladigan nechta son bor?

Kiruvchi ma'lumotlar:

N va K natural sonlar beriladi. \((1≤N≤10^{18})\), \((1≤K≤60)\)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Izoh:

1-testda
\(F(0)=0\)

\(F(1)=1+F(0)=1+0=1\)

\(F(2)=F(2/2)=F(1)=1\)

\(F(3)=1+F(3-1)=1+F(2)=1+1=2\) (To'g'ri keladi)

\(F(4)=F(4/2)=F(2)=1\)

\(F(5)=1+F(5-1)=1+F(4)=1+1=2\) (To'g'ri keladi)

\(F(6)=F(6/2)=F(3)=2\) (To'g'ri keladi)

\(F(7)=1+F(7-1)=1+F(6)=1+2=3\)

\(F(8)=F(8/4)=F(2)=1\)

\(F(9)=1+F(9-1)=1+F(8)=1+1=2 \)(To'g'ri keladi)

\(F(10)=F(10/2)=F(5)=2\) (To'g'ri keladi)
Demak 5 ta ekan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 10 2 73 3 15 7	5 24 0

E. Antiqa salomlashish

Xotira: 512 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, siz Informatika olimpiadasidasiz. Zalga \(N\) ta o'quvchi yig'ilgan va barchasi o'zaro tanishmoqda. Lekin bu zalda salomlashish juda qiziq tartibda kechadi:
1-o'quvchi faqat 1 kishi bilan salomlashsa, 2-o'quvchi 2 kishi bilan, ... , \(N-1\)-o'quvchi esa \(N-1\) kishi bilan salomlashmoqda!
Endi esa savol: Oxirgi \(N\)-o'quvchi necha kishi bilan salomlashgan? Mana shu sirni ochadigan dastur tuzing!

Kiruvchi ma'lumotlar:

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

Keyingi \(T\)ta qatorda natural \(N\) soni beriladi. \((1\le N\le 10^9)\)

Chiquvchi ma'lumotlar:

Har bir javobni alohida qatorlarda chop eting.

Izoh:

Izoh:

1-testda N=1 bo'lsa u hech kim bilan salomlashmaydi. Demak 0 javob
N=2 bo'lsa, Demak ikkinchi o'quvchi faqat 1 ta o'quvchi bilan, ya'ni birinchi o'quvchi bilan salomlashadi xalos.

Misollar:

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

F. Antiqa soat

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Rasmda chapdagi oddiy soat o'ngdagi esa noodatiy soat hisoblanadi. O'ngdagi soat oddiy soatdan soniya strelkasi\(K\) foiz tezroq yuradi. Agar ikkala soat ham bir xil \(A\) soatni ko'rsatib turgan bo'lsa va bir qancha vaqtdan so'ng oddiy soat \(B\) soatni ko'rsatsa, noodatiy soat qaysi vaqtni ko'rsatayotgani aniqlovchi dastur tuzing.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(A\) vaqt \(HH:MM:SS\) ko'rinishda beriladi. \((1≤H≤12)\), \((1≤M,S≤59)\)

Ikkinchi qatorda \(B\) vaqt \(HH:MM:SS\) ko'rinishda beriladi. \((1≤H≤12)\), \((1≤M,S≤59)\)

Uchunki qatorda \(K\) natural son beriladi. \((1≤K≤100)\)

Chiquvchi ma'lumotlar:

Masala javobini \(HH:MM:SS\) ko'rinishda chop eting.

Izoh:

Soat ko'rsatkichi 12 soatdan oshmaydi.

Natija chop etishda soniya haqiqiy son chiqishi mumkin shunga butun qismini olish kifoya.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 08:13:18 09:28:41 55 02:06:45 04:43:46 36	10:10:08 05:40:17