Бінарний пошук#4117
Фрагмент програми нижче виконує бінарний пошук цілого числа в масиві:
Перед викликом BinarySearch змінна була встановлена в деяке ціле число від до включно, а масив був заповнений цілими значеннями.
Відомо, що процедура завершилася повідомленням "Found item i = XXX in L = XXX comparisons" з деякими відомими значеннями та .
Ваше завдання — написати програму, яка знаходить усі можливі значення , за яких могло зʼявитися таке повідомлення. Однак кількість можливих значень може бути досить великою. Тому вас просять обʼєднати всі послідовні в інтервали й записати лише перше та останнє значення в кожному інтервалі.
Вхід складається з одного рядка з двома цілими числами та (0 \leq i < 10000 та 1 \leq L \leq 14), розділеними пробілом.
У першому рядку виведіть одне ціле число — загальну кількість інтервалів для можливих значень . Далі у рядках виведіть ці інтервали у зростаючому порядку. Кожен рядок повинен містити два цілих числа A_i та B_i (A_i \leq B_i), розділених пробілом, що означають перше та останнє значення інтервалу.
Якщо немає жодного можливого значення , виведіть лише одне число .
Приклад 1