Мячи
Классическая задача с двумя стеклянными шарами формулируется следующим образом:
"У вас есть два одинаковых стеклянных шара, и вы хотите определить самый низкий этаж в 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.