Olimpiada masalalari

Kitob raqami. 112-misol. Kumush navbatdagi kitobni talqin etayotgan paytda, o‘qilgan betlar nomerlarining yig‘indisini hisoblab ko‘rdi. Bu yig‘indini Q orqali belgilaymiz. Oxirgi o‘qilgan betning nomerini aniqlovchi dastur yozing.
#include
#include
using namespace std;

int main()

{
int Q, i = 0, S=0;
cout << "Sahifalar soni:"; cin >> Q;
while (S < Q)
{
i++;
S += i;
}
cout << i << endl;

return 0;
}


117-misol. Katta sonlarni bir-biriga ko‘paytirish natijasida xotira to‘lib qolishi mumkin. Shuning uchun, berilgan butun tur (integer yoki longint) ning eng katta chegaraviy sonidan oshib ketuvchi ko‘paytmani chop etish maqsadida tabiiy vositalardan foydalanish kerak.
Eng katta chegaraviy sondan oshib ketuvchi ikki son ko‘paytmasini chop etish uchun dastur tuzamiz.

Faqat besh. 118-misol. 12345679 ni qanday songa ko‘paytirib, faqat 5 dan iborat bo‘lgan sonni hosil qilish mumkin?
#include
#include
using namespace std;
int Tekshir(int a)
{
int k = 0, q;
while (a != 0)
{
q = a % 10;
if (q != 5)
{
return 0;
}
else
k = 1;
a = a / 10;
}
return k;
}
int main()
{
int k = 0, i = 0, a = 12345679;
while (!k)
{
i += 5;
k=Tekshir(a*i);

}
cout << i << endl;
return 0;
}
Tasmalar. 120-misol. Bir mutaxassis uzun tasmada boshidan boshlab, har 36 sm da ko‘k qalam bilan belgilar kiritadi. Boshqa mutaxassis boshidan boshlab, har 25 sm da qizil qalam bilan belgilar kiritadi. Ko‘k belgi biron-bir qizil belgiga nisbatan 1 sm masofada joylashib qolishi mumkinmi?
Algoritmi.
Javob: mumkin. Masalan 9- ko‘k belgi va 13-qizil belgi bir-biriga nisbatan 1 sm masofada joylashadi, chunki 13 25 - 9 36 = 1.
Bu masalada, umuman olganda 25x - 36y = 1, 25x - 36y = - 1 tenglamalardan biron-birining butun sonlardan iborat yechimini topish yoki bunday yechimlar yo‘qligini isbotlash yetarlidir. Shunday standart protsedura borki, uning yordamida har doim tenglamaning yechimini topsa bo‘ladi (agar bo‘lsa). Uni bizning masalamizda ko‘rsatib o‘tamiz. EKUB(36; 25) topish uchun Evklid algoritmining barcha qadamlarini yozib chiqaylik:
36 = 25 1 + 11; 25 = 11 2 + 3; 11 = 3 3 + 2; 3 = 2 1 + 1.
Bu tenglamalar zanjirini qoldiqlar bo‘yicha qayta yozib chiqamiz:
11 = 36 - 25 1; 3 = 25 - 11 2; 2 = 11 - 3 3; 1 = 3 - 2 1.
U holda quyidagiga ega bo‘lamiz:
1 = 3 - (11 - 3 3) = 3 4 - 11 = (25-11 2) 4 - 11 = 25 4 - 11 9 =
= 25 4 - 11 9 = 25 4 - (36 - 25) 9 = 25 13 - 36 9.
Natijada 25 13 - 36 9 = 1, tenglama hosil bo‘ladi, u esa o‘z navbatida 25x - 36y = 1 tenglamaning bitta yechimini beradi.
Aniqlash. Noaniq tenglamalar bittadan ortiq no‘malumga ega bo‘lgan tenglamalardir.