Кулі
The classic Two Glass Balls brain-teaser is often posed as:
"Маючи дві однакові скляні кулі, ви хочете визначити найнижчий поверх у 100-поверховій будівлі, з якого вони розіб'ються при падінні. Припустимо, що кулі не пошкоджуються, якщо їх кидати з нижчих поверхів. Яка стратегія мінімізує найгірший сценарій за кількістю кидків?"
Припустимо, що у нас є лише одна куля. Нам доведеться кидати її з кожного поверху від 1 до 100 послідовно, що вимагатиме 100 кидків у найгіршому випадку.
Тепер розглянемо випадок, коли у нас є дві кулі. Припустимо, ми кидаємо першу кулю з поверху n. Якщо вона розіб'ється, ми опиняємося в ситуації, коли у нас залишається одна куля, і нам потрібно кидати з поверхів 1 до n-1 послідовно, що дає n кидків у найгіршому випадку (перша куля кидається один раз, друга - максимум n-1 разів). Однак, якщо вона не розіб'ється при падінні з поверху n, ми зменшили проблему до кидання з поверхів n+1 до 100. У будь-якому випадку ми повинні пам'ятати, що вже використали один кидок. Отже, мінімальна кількість кидків у найгіршому випадку - це мінімум серед усіх n.
Ви напишете програму, щоб визначити мінімальну кількість кидків, необхідних у найгіршому випадку, маючи B куль і M-поверхову будівлю.
Вхідні дані
Перша стрічка введення містить одне ціле число P, (1 ≤ P ≤ 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних складається з однієї стрічки, що містить три (3) десяткові цілі значення: номер задачі, за яким слідує пробіл, за яким слідує кількість куль B, (1 ≤ B ≤ 50), за яким слідує пробіл і кількість поверхів у будівлі M, (1 ≤ M ≤ 1000).
Вихідні дані
Для кожного набору даних згенеруйте одну стрічку виходу з наступними значеннями: номер набору даних як десяткове ціле число, пробіл і мінімальна кількість кидків, необхідних для відповідних значень B та M.