Решение задачи про деление бактерий
Задачу удобно решать, если представить её как битовую маску
Рассмотрим заполнение пробирки одной бактерией. В первую секунду заполнен ровно 1 младший бит (нулевой бит) 000...0001. Через 60 секунд у нас будет заполнен 60-й бит, то есть 60-й бит является условием заполнения колбы.
Если положить три бактерии, то битовая маска примет вид 000...0011 (двоичное представление числа 3 — 11). Через 59 секунд сдвигом будет заполнен 60-й бит. Однако 59-ый бит тоже будет равен 1, и часть бактерий вывалится из пробирки.
Если рассмотреть пробирку через 58 секунд, то она не заполнится до конца, поскольку будут заняты 58-й и 59-й бит.
Ответ: 59 секунд.
Мы показали решение задачи с точки зрения программиста, но её можно решить и математически через степени двойки, что, по сути, аналогично предложенному решению.
Источник
Задачу удобно решать, если представить её как битовую маску
std::uint64_t, ведь каждая бактерия удваивается в конце каждой секунды.Рассмотрим заполнение пробирки одной бактерией. В первую секунду заполнен ровно 1 младший бит (нулевой бит) 000...0001. Через 60 секунд у нас будет заполнен 60-й бит, то есть 60-й бит является условием заполнения колбы.
Если положить три бактерии, то битовая маска примет вид 000...0011 (двоичное представление числа 3 — 11). Через 59 секунд сдвигом будет заполнен 60-й бит. Однако 59-ый бит тоже будет равен 1, и часть бактерий вывалится из пробирки.
Если рассмотреть пробирку через 58 секунд, то она не заполнится до конца, поскольку будут заняты 58-й и 59-й бит.
Ответ: 59 секунд.
Мы показали решение задачи с точки зрения программиста, но её можно решить и математически через степени двойки, что, по сути, аналогично предложенному решению.
Источник