Kafel plitəsi

İnnokenti mətbəxində təmir işləri aparır. Peşəkar inşaatçı kimi o, mətbəx üçün kafel plitkadan daha yaxşı bir seçim olmadığını bilir.

İnnokentinin mətbəxi w ilə h metr ölçüsündə düzbucaqlıdır. Təəssüf ki, lazım olan plitka yalnız bir mağazada satılır. Hər bir plitka a ilə b metr ölçüsündədir və üzərində maraqlı bir naxış var. Mətbəxin döşəməsinin gözəl görünməsi üçün plitkalar elə yerləşdirilməlidir ki, hər bir plitkanın tərəfi maksimum bir plitka ilə sərhədlənsin və mətbəxin tərəflərindən biri ilə paralel olsun. Naxış çox spesifikdir, buna görə də plitkaları çevirmək olmaz, hətta hamısını eyni anda çevirmək də olmaz — mətbəxin w uzunluğundakı tərəfi həmişə plitkanın a uzunluğundakı tərəfi ilə paralel olmalıdır.

Bəlkə də plitkaları bir tərəfi boyunca düz kəsiklərlə kiçik hissələrə bölmək lazım gələcək. Bu halda alınan plitka hissələrini də kiçik hissələrə bölmək olar. İnnokenti mətbəxi elə döşəmək istəyir ki, nəticədə mümkün olan ən az sayda plitka və onların hissələrindən istifadə edilsin.

İnnokentiyə mətbəxi gözəl döşəmək üçün lazım olan minimum sayda a ilə b ölçüsündə bütöv plitka almağa kömək edin.