В некоторых задачах вообще нет хитрой идеи. Условие описывает процесс — карточную игру, принтер, железнодорожную станцию — и спрашивает, что получится в конце. Чтобы решить такую задачу, заставьте программу делать ровно то, что сказано в условии, шаг за шагом и в том же порядке. Это и есть моделирование.
Всё обдумывание уходит на два вопроса: как хранить состояние процесса и как не ошибиться ни в одной мелочи. На первый вопрос удивительно часто отвечают стек, очередь и дек.
Условие подсказывает контейнер
Слова условия обычно сами называют нужный контейнер:
| В условии сказано… | Храните в |
|---|---|
| «в порядке прихода», «очередь», «по очереди», «уходит в конец» | queue |
| «сверху», «самый последний», «последний положенный», «отменить» | stack |
| «с любого края», «самый левый или самый правый» | deque |
| «k-й по счёту», «любая позиция» | vector |
Карточная игра: две колоды — две очереди
У каждого из двух игроков колода; все карты разные. В каждом бою оба открывают верхнюю карту; старшая карта побеждает, и её хозяин кладёт вниз своей колоды сначала побитую карту, а потом свою. Тот, у кого кончились карты, проигрывает. Выведите число боёв и победителя,
1или2, — или-1, если игра никогда не закончится.
Ввод
Вывод
Верхние карты берутся из начала, выигранные уходят в конец: каждая колода — очередь.