Toplar

Klassik İki Şüşə Kürə məntiq tapmacası tez-tez belə verilir:

"İki eyni şüşə kürəniz olduğunu nəzərə alaq. Sizin vəzifəniz budur ki, 100-mərtəbəli binada hansı ən aşağı mərtəbədən atdıqda şüşə kürələrin sınacağını müəyyən edəsiniz. Fərz edin ki, kürələr bu mərtəbədən aşağıda atıldıqda sınmır. Ən pis halda atılma sayını minimum edəcək strategiya hansıdır?"

Tutaq ki, yalnız bir kürəmiz var. O halda $1$-dən $100$-ə qədər bütün mərtəbələrdən ardıcıl atmalı olardıq ki, ən pis halda $100$ atım tələb olunur.

İndi iki kürə olan halı nəzərdən keçirək. Tutaq ki, birinci kürəni $n$-ci mərtəbədən atırıq. Əgər sınsa, bir kürə qalır və $1$-dən n-1-ə kimi mərtəbələrdə bir-bir yoxlamalıyıq; ən pis halda $n$ atım olar (birinci kürə bir dəfə atılır, ikincisi isə maksimum n-1 dəfə). Lakin, əgər kürə $n$-ci mərtəbədən atıldıqda sınmırsa, problem n+1-dən $100$-ə qədər mərtəbələrə tətbiq olunur. Hər iki halda nəzərə almalıyıq ki, artıq bir atma etmişik. Beləliklə, ən pis halda atma sayının minimumu bütün $n$-lər arasında minimumudur.

Bu məsələ üçün sizə verilən $B$ kürə və $M$-mərtəbəli bina üçün ən pis halda ən az atım sayını tapacaq proqram yazmalısınız.