Для случая (б) — откладываем карточку C, про которую мы не знаем ответа, в сторону, и смотрим XOR в какой-нибудь (меньшей по размеру) из кучек К.
- Если получилось 0000 — нам не соврали, а C нужно положить в другую кучку K’.
- Если получился код C — нам не соврали, а C нужно положить в ту же кучку K.
- Если ни то, ни другое, но в сумме одна или три единицы, то нам соврали, и эта сумма это код соответствующей карточки. Перекладываем её из одной кучки в другую, и кладём С в K’.
- И наконец, иначе добавляем ещё и код C; должен получиться код карточки, которую нужно переложить из одной кучки в другую. А карточку C кладём в K.
Всё, враньё поймали, разложили ответы правильно, и опять складываем красные числа в стопке «да».
Post #4327
1.52K