Есть источник случайных битов rand2, который равновероятно возвращает 0 или 1.
Нужно получить равномерное случайное число из диапазона [0, n - 1]. В тренажере вместо настоящей случайности передается готовый поток битов bits, чтобы решение можно было проверить детерминированно.
Используйте минимальное число битов chunk_size, такое что 2 ** chunk_size >= n. Читайте биты чанками, интерпретируйте чанк как binary integer. Если значение меньше n, верните его; иначе отбросьте чанк и читайте следующий.
def uniform_from_rand2_bits(n: int, bits: list[int]) -> list[int]:Верните [value, used_bits], где used_bits — сколько битов пришлось прочитать до принятого значения.
n = 3bits = [0,0][0,2]n = 3bits = [1,1,0,1][1,4]Первый чанк 3 отбрасывается
n = 5bits = [1,0,1,0,0,1][1,6]5 отбрасывается, 1 принимается