🤔 Задача: 672. Bulb Switcher II
Есть комната с 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 {
fun flipLights(n: Int, m: Int): Int {
val seen = mutableSetOf<Int>()
val n = minOf(n, 6)
val shift = maxOf(0, 6 - n)
for (cand in 0 until 16) {
val bcount = Integer.bitCount(cand)
if (bcount % 2 == m % 2 && bcount <= m) {
var lights = 0
if ((cand shr 0 and 1) > 0) lights = lights xor (0b111111 shr shift)
if ((cand shr 1 and 1) > 0) lights = lights xor (0b010101 shr shift)
if ((cand shr 2 and 1) > 0) lights = lights xor (0b101010 shr shift)
if ((cand shr 3 and 1) > 0) lights = lights xor (0b100100 shr shift)
seen.add(lights)
}
}
return seen.size
}
}👉Новости 👉Платформа