NSD Sorğuları Oyunu

Çixmanın dünən ad günü idi (əslində yox), və o, Kutsmenlə təxmin oyunu oynayırdı: Kutsmen Çixmanın yaşını tapmağa çalışırdı. Kutsmen bilir ki, Çixmanın yaşı $1$-dən $n$-ə qədər olan təbii bir ədəddir. Kutsmen bir x_i ədədi deyə bilər və Çixman bu ədəd ilə yaşının ən böyük ortaq bölənini (ƏBOB) cavab verəcək.

Gəlin, n = 6 olduğu halda durumu nəzərdən keçirək. Kutsmen $3$ təklif edir və Çixman ƏBOB $1$ cavabını verir. Bu, Çixmanın yaşının $3$ və ya $6$ ola bilməyəcəyini, ancaq $1$, $2$, $4$, $5$ ola biləcəyini göstərir. Sonra Kutsmen $2$ təklif edir və Çixman ƏBOB $2$ cavabını verir. Indi yaş ya $2$, ya da $4$ ola bilər, $1$ və $5$ ola bilməz. Nəhayət, Kutsmen $4$ təklif edir və Çixman $2$ cavabını verir. Beləliklə, Çixmanın yaşı dəqiq $2$-dir. Kutsmenə ümumilikdə $3$ sorğu lazım oldu.

Ancaq, Çixmanın yaşını cəmi $2$ sorğu ilə də öyrənmək olar. Bunun üçün Kutsmen ilk növbədə $6$ təklif etməlidir; cavabdan sonra yaşı əlavə bir sorğu ilə dəqiqləşdirmək olar.

Kutsmen optimal oynayarsa, ən pis halda Çixmanın yaşını tapmaq üçün lazım olan minimal sorğu sayını tapın.