Этажи индекса
Администратор базы данных прикидывает, сколько страниц прочитает поиск по индексу. Индекс — B-дерево с минимальной степенью t: в каждой странице, кроме корня, от t − 1 до 2t − 1 ключей, в корне — от 1 до 2t − 1, у страницы с k ключами, если она не лист, ровно k + 1 детей, и все листья на одной глубине. Поиск читает по странице на каждом этаже. Сколько этажей может быть у такого дерева с n ключами — в самом плотном случае и в самом разреженном?
Второй тест — индексы этого каталога: 436 069 слов «Войны и мира», 47 585 разных слов романа, 19 073 землетрясения из каталога USGS и 8966 страниц сайта, при разных размерах страниц.
Вход
В первой строке q (1 ≤ q ≤ 10⁵). В каждой из следующих q строк — t и n (2 ≤ t ≤ 10⁹, 1 ≤ n ≤ 10¹⁸).
Выход
Для каждой строки — наименьшее и наибольшее возможное число этажей через пробел.
Примеры
Пример 1
4 2 1 2 7 2 8 64 436069
1 1 2 3 2 3 3 3
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сколько ключей помещается в дерево из L этажей, если все страницы заполнены до отказа? А сколько их нужно как минимум, чтобы этажей было L?
2Подсказка 2
Формулы получатся с логарифмами, но считать логарифмы в числах с плавающей точкой здесь нельзя: на границах, где n ровно на один ключ меньше целого этажа, округление уводит ответ на единицу.
3Идея
В самом плотном дереве у каждой страницы 2t − 1 ключей и 2t детей, и L этажей вмещают (2t)L − 1 ключей; наименьшее число этажей — наименьшее L, при котором это не меньше n. В самом разреженном у корня один ключ и два ребёнка, у остальных страниц t − 1 ключей и t детей; на L этажах это 2tL−1 − 1 ключей, и наибольшее число этажей — наибольшее L, при котором это не больше n. Обе величины находятся перебором L в целых числах.
4Разбор
Минимум ключей на L этажах: на втором этаже 2 страницы, на третьем 2t, на k-м 2tk−2, в каждой t − 1 ключей; вместе с ключом корня это 1 + 2(t − 1)(1 + t + … + tL−2) = 2tL−1 − 1. Максимум — геометрическая прогрессия (2t − 1)(1 + 2t + … + (2t)L−1) = (2t)L − 1.
Этажей при n ≤ 10¹⁸ не больше шестидесяти, так что перебор по L мгновенный. В Python степени — точные целые. В Go tL быстро выходит за пределы uint64, поэтому умножаем с насыщением: как только произведение превысило бы порог больше любого n, считаем его порогом.
Для индекса по словам романа со страницами на 127 ключей (t = 64) оба ответа — три этажа: в каких бы пропорциях ни заполнились страницы, поиск прочитает три страницы.
4+Решение
5Сложность
O(log n) на строку: столько шагов перебора по этажам.
6Типичные ошибки
- Логарифмы в плавающей точке.
math.log(216, 6)— при t = 3 и n = 215, когда три полных этажа заняты до последнего ключа, — даёт 3,0000000000000004 вместо 3, иceilответит 4; на n около 10¹⁸ точностиfloatне хватает вовсе. Третий — пятый тесты состоят из таких границ. - Корень как обычная страница. В корне может быть один ключ; если требовать от него t − 1, максимальная высота выйдет меньше настоящей.
- Переполнение в Go. 264 при t = 2 достигается уже на 64-м этаже, а (10⁹)³ не помещается в
int64.