|
Игра в фишки
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Сопоставим каждой фишке первого цвета число 3, каждой фишке второго цвета – число 5, третьего - 6. Теперь определим число S, как:
где ⊕ - это битовая операция «xor». Одним из свойств операции «xor», которое нам понадобится, является следующее: a ⊕ a = 0. Заметим, что числа 3, 5, 6 были выбраны не случайно, так как
Пусть теперь мы заменили две фишки одного цвета на фишку другого цвета. Учитывая выше сказанное, понятно, что число S от этого не изменилось. Теперь рассмотрим позиции, когда игра «сыграна». В этих позициях S принимает три возможных значения: 3, 5, 6. Таким образом, задача свелась к нахождению числа S (игра может быть сыграна, если S = 3, 5 или 6), которое легко посчитать, используя свойство операции «xor»: a ⊕ a = 0.
Однако, в решении есть одна тонкость. Все дело в том, что данное решение не учитывает тот факт, что количество фишек в промежуточных ситуациях не может стать отрицательным. Поэтому нужно рассмотреть особый случай, когда фишек каких-либо двух цветов нет, а количество фишек третьего цвета не равно 1. Доказательство того, что это единственный случай, нарушающий закономерность, мы оставляем читателю в качестве упражнения.
Разбор: Александр Торопов.
| |
