Сложность: medium
Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2
👨💻 Алгоритм:
1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.
2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.
3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.
😎 Решение:
class Solution {
function flipLights($n, $m) {
$seen = [];
$n = min($n, 6);
$shift = max(0, 6 - $n);
for ($cand = 0; $cand < 16; ++$cand) {
$bcount = substr_count(decbin($cand), '1');
if ($bcount % 2 == $m % 2 && $bcount <= $m) {
$lights = 0;
if ((($cand >> 0) & 1) > 0) $lights ^= 0b111111 >> $shift;
if ((($cand >> 1) & 1) > 0) $lights ^= 0b010101 >> $shift;
if ((($cand >> 2) & 1) >Ставь 👍 и забирай 📚 Базу знаний