401_Binary_Watch

Решение задачи 401. Binary Watch

Возможно, вам знакомы такие наручные часы. Время на них отображается в двоичном формате. Индикация предельно проста. Часы отображают два целых числа:

• 4 разряда в верхнем ряду отображают часы от 0 до 11. Или от 0b0000 до 0b1011
• 6 разрядов в нижнем ряду отображают минуты от 0 до 59. Или щт 0b000000 до 0b111011

Индикатор PM указывает на соответствующую половину суток. Однако, в этой задаче он не рассматривается.

Забудем про индикатор PM. Предположим, что функционируют только 10 оставшихся индикаторов. Более того, мы не видим какие именно индикаторы горят, нам известно только их количество. Авторы задачи просят нас вывести все возможные значения времени, которые могут соответствовать n горящих индикаторов. Время нужно вывести в формате ЧЧ:ММ, причем часы должны отображаться без лидирующих нолей. То есть, такое отображение верно: 9:08, а так нельзя: 01:55.

Есть два подхода к решению задачи. Опишу оба.

Бэктрекинг с проверкой допустимых пермутаций.

В нашем распоряжении 10 разрядов, и число n - количество установленных битов. Мы можем перебрать все возможные пермутации n единиц и 10 - n нолей. Для этого напишем рекурсивную функцию, PrintCombs(num, pos, count) где num - индикатор, pos - порядковый номер устанавливаемого бита, а count - количество битов которые осталось установить. Изначально num = 0, pos = 0, count = n. Базовый случай - count == 0 - все допустимые биты установлены, то есть нужное количество индикаторов горит. В цикле для i от pos до 10 рекурсивно вызываем PrintCombs(num | (1 << i), i + 1, count - 1). То есть у рекурсии будет два возможных варианта завершения:

• count == 0 Получили пермутацию числа с n установленных бит.
• count > 0, i == 10 Вышли из цикла. Откатились в предыдущий вызов.

Функция попробует включить каждый i-тый бит, но не превысит count включенных бит. То есть нам будут доступны все возможные пермутации для n бит в 10 разрядах.

На этапе count == 0 нужно проверить полученное число на валидность. Сначала разделим его на два числа:

• Нам нужны 4 старших бита, отвечающих за часы. Сдвинем число на 6 бит вправо h = num >> 6ul.
• С помощью маски 0b111111 == (1ul << 6ul) - 1 узнаем состояние 6 младших битов m = num & ((1ul << 6ul) - 1)

Теперь осталось проверить что h < 12, а m < 60. Если все в порядке, отправляем h и m в функцию, генерирующую строку отображения времени в требуемом формате, а результат записываем в массив результатов.

Мое решение лежит здесь.

Перебор допустимых значений времени с подсчетом установленных битов.

Это подход к задаче с другого конца. Мы просто переберем все минуты в 12 часах (помним, что индикатор PM не работает). И для каждого варианта посчитаем установленные биты. Если их число равно n, сгенерируем результирующую строку.

Считать установленные биты будем с помощью простой функции PopCount(n), которая возвращает их количество. Она просто извлекает младший бит из n -> n & 1, а затем возвращает сумму полученного значения и результата рекурсивного вызова PopCount(n >> 1ul). Базовый случай n == 0. Все можно записать в одну строчку: int PopCount(int n) { return n == 0 ? 0 : (n & 1ul) + PopCount(n >> 1ul); }

Мое решение с подсчетом битов лежит здесь