В прошлый раз мы с вами познакомились с теорией игр — той самой штукой, что помогает понять, почему коты всегда оказываются на самом вкусном месте дивана, а мужья умудряются забыть купить хлеб даже после трех напоминаний. Но сегодня мы окунемся в её применение, которое заставит вас взглянуть на ЕГЭ по информатике как на увлекательный квест, где вместо драконов и волшебников — Петя и Ваня метают камни. Причём не друг в друга! Хотя с таким азартом — кто знает…
Итак, представьте: два героя школьных легенд — Петя и Ваня — стоят перед кучей камней.
Звучит просто? А вот и нет! Игра-то хитрая: нужно довести количество камней до определённого числа, используя только заранее разрешённые ходы: добавить один камень, два или увеличить количество камней в N раз. Если бы мне платили за каждый такой ход в детстве… Но вернёмся к нашим баранам — то есть к нашим камням.
Задания 19-21 ЕГЭ по информатике именно про это.
Сначала кажется: «Вот сейчас я быстро решу и пойду гулять». Но тут как в анекдоте про программиста: «Почему ты так долго сидишь? Я ж сказал «быстро»!» Так и тут — решение 20 и 21 заданий полностью зависит от того, как ты раскроешь тайны задания 19.
Это как строить дом без фундамента — разве что домик из песка.
Давайте попробуем стать стратегами и отправимся в мир абстрактной игры с кучей камней. У нас есть два игрока (да-да, Петя и Ваня), куча камней (сначала немногочисленная, потом уже почти горная), и задача: выиграть не сразу, а хитрее — победить своим вторым ходом.
Представьте себя на месте Вани.
Нужно сделать так, чтобы после твоего хода в куче было хотя бы 20 камней. Логично?
Конечно! Но сколько же должно быть камней до твоего хода?
Тут пригодится магия обратных операций — вычитаем 2 или 5 из нужного количества (20) и получаем 18 или 15. То есть если перед ходом у тебя есть хотя бы 15 камней, можно смело бросать пять штук и праздновать победу.
А теперь посмотрите на Петиное положение: он должен оставить после своего хода минимум 15 камней, чтобы не проиграть сразу. Сколько же было у него изначально?
Вот тут начинается веселье! Применяем обратные операции снова — вычитаем 2 или 5 из пятнадцати и получаем… внимание… десять или тринадцать!
Но погодите-ка! Если у Пети было десять камней, зачем ему делать пятнадцать для соперника?
Это всё равно что подарить бабушке смартфон с надписью «не включать»! А вот если у него было тринадцать – тут уж вариантов мало: либо добавляешь два камня – привет пятнадцать – либо пять – привет двадцать!
Как говорится, выбор между двумя золами.
Так вот при тринадцати камнях Петя обречён проиграть при правильной игре Вани. Это как пытаться убедить кота принять ванну – вроде возможно теоретически, но практически бесполезно.
Чтобы визуализировать эту драму больше драматизма добавим картинку (в голове). Каждый путь ведёт к победе Вани в большинстве случаев — словно фильм ужасов с предсказуемым финалом.
Теперь перейдём к классической формулировке задания номер двадцать: найти два наименьших значения S (не путать со скоростью Wi-Fi), при которых Петя может выиграть только со второго раза вне зависимости от ходов Вани.
Это как искать иголку в стоге сена… но иголка эта золотая и светится ночью!
И вот здесь начинается самое интересное: если вы думаете, что всё просто – вспомните историю про студента Мишу, который пытался решить подобную задачу за пять минут до экзамена.
Итог был предсказуем: Миша получил пятёрку за находчивость… преподавателя!