Швидкість

Чи знайомі ви з грою Speed? Це популярна карткова гра, в якій два гравці змагаються, хто швидше зможе викласти свої карти на столи.

Щоб грати в Speed, два гравці сідають один навпроти одного. Кожен має свою колоду та рядок, а між ними розташовані два столи для створення купи: один зліва, інший справа. Рядок може вмістити лише чотири карти. Гра продовжується за кількома простими правилами:

1. Гравець може перемістити карту зі свого рядка на купу, лише якщо ранг переміщеної карти є сусіднім до рангу карти на вершині купи. Наприклад, A і 2, 4 і 3 є сусідами. A і K також вважаються сусідами в цій грі.

2. Гравець може взяти карту з колоди і покласти її на вільне місце в рядку.

3. Якщо обидва гравці намагаються одночасно перемістити карти на один і той самий стіл, лише швидший гравець може покласти карту. Інший гравець не може перемістити свою карту на купу (оскільки вона більше не є сусідом верхньої карти) і повинен повернути її назад у свій рядок.

Спочатку кожен гравець бере чотири карти зі своєї колоди і кладе їх обличчям вгору на рядок. Якщо карт недостатньо, щоб заповнити рядок, беруть стільки, скільки можливо. Гра починається з того, що кожен бере ще одну карту з колоди і кладе її на столи праворуч одночасно. Якщо колода вже порожня, можна перемістити будь-яку карту зі свого рядка на стіл. Потім вони продовжують виконувати свої дії згідно з описаними правилами, доки обидва не зайдуть у глухий кут, тобто не матимуть можливості переміщати карти. Щоразу, коли виникає глухий кут, вони починають спочатку, кожен бере карту (або бере карту зі свого рядка) і кладе на свій правий стіл, незалежно від її обличчя. Гравець, який першим закінчить свої карти, виграє гру.

Містер Джеймс А. Геймс настільки захопився цією простою грою, що вирішив розробити роботів, які в неї грають. Він щойно завершив проектування роботів і їхню програму, але не впевнений, чи вони працюють добре, оскільки дизайн дуже складний. Тому він попросив вас, свого друга, написати програму, яка симулює роботів. Алгоритм для роботів розроблений наступним чином:

• Робот бере карти в порядку, в якому вони роздані.

  • Кожному роботу завжди дається одна або більше карт.

  • У реальній грі Speed гравці спочатку класифікують карти за кольорами, щоб легко визначити, який гравець поклав карту. Але цей крок пропускається в цій симуляції.

  • Гра використовує лише один набір карт, розділений на дві частини. Іншими словами, у двох колодах, які надані роботам, може бути не більше однієї карти з однаковим обличчям.

• Як підготовка, кожен робот бере чотири карти і кладе їх у рядок справа наліво.

  • Якщо в його колоді недостатньо карт, візьміть усі карти з колоди.

• Після завершення цього кроку обома роботами, вони синхронізуються один з одним і починають гру, одночасно кладучи перші карти на столи.

  • Якщо в колоді залишається одна або більше карт, робот бере верхню карту і кладе її на правий стіл. Інакше робот бере крайню праву карту зі свого рядка.

• Потім два роботи продовжують рухатися відповідно до основного правила гри, описаного вище, доки жоден з них не зможе більше переміщати карти.

  • Коли робот бере карту зі свого рядка, він бере карту (якщо можливо) з колоди, щоб заповнити вільне місце після того, як карта покладена на стіл.

  • Переміщення карт займає певний час. Коли робот завершує покладання карти на стіл, а інший робот рухається, щоб покласти карту на той самий стіл, робот у русі повинен негайно відмовитися від дії та повернути карту на її початкове місце.

  • Робот може почати рух, щоб покласти карту на купу в той самий момент, коли сусід розміщений на вершині купи.

  • Якщо два роботи намагаються покласти карти на один і той самий стіл одночасно, лише робот, що переміщує карту ліворуч, може успішно покласти карту через налаштування позицій.

  • Коли у робота є кілька кандидатів у своєму рядку, він віддає перевагу картам, які можна розмістити на правому столі, ніж тим, які не можна. Якщо все ще залишаються кілька варіантів, робот віддає перевагу слабшій карті.

• Коли настає ситуація глухого кута, роботи починають спочатку, кожен кладе карту на стіл, а потім продовжують рухатися знову відповідно до описаного вище алгоритму.

• Коли один з роботів закінчує карти, тобто переміщує всі роздані карти, гра закінчується.

  • Робот, який закінчив карти, виграє гру.

  • Коли обидва роботи закінчують карти одночасно, робот, який перемістив сильнішу карту в останньому ході, виграє.

Сила карт визначається їхніми рангами, а потім мастями. Ранги сильні в такому порядку: A > K > Q > J > X (10) > 9 > ··· > 3 > 2. Масті сильні в такому порядку: S (піки) > H (черви) > D (бубни) > C (трефи). Іншими словами, SA є найсильнішою, а C2 є найслабшою. Роботи потребують наступної кількості часу для завершення кожної дії:

• $300$ мілісекунд, щоб взяти карту в рядок,

• $500$ мілісекунд, щоб перемістити карту на правий стіл,

• $700$ мілісекунд, щоб перемістити карту на лівий стіл, і

• $500$ мілісекунд, щоб повернути карту на її початкове місце.

Скасування дії завжди займає постійний час $500$ мс, незалежно від прогресу дії, що скасовується. Цей час рахується з точного моменту, коли дія переривається, а не з початку дії. Ви можете припустити, що ці роботи добре синхронізовані, тобто між ними немає розбіжності в часі. Наприклад, припустимо, що Робот A отримав колоду "S3 S5 S8 S9 S2", а Робот B отримав колоду "H7 H3 H4", тоді гра буде виглядати, як описано нижче. Зверніть увагу, що в описі "стіл A" (відповідно "стіл B") позначає правий стіл для Робота A (відповідно Робота B).

• Робот A бере чотири карти S3, S5, S8 і S9 у свій рядок справа наліво. Робот B бере всі три карти H7, H3 і H4.

• Потім два роботи синхронізуються для початку гри. Нехай цей момент буде 0 мс.

• У той самий момент Робот A починає переміщати S2 на стіл A з колоди, а Робот B починає переміщати H7 на стіл B з рядка.

• На 500 мс обидва роботи завершують переміщення карт. Потім Робот A починає переміщати S3 на стіл A (що вимагає $500$ мс), а Робот B починає переміщати H3 також на стіл A (що вимагає $700$ мс).

• На 1000 мс Робот A завершує покладання S3 на стіл A. Робот B перериває свій рух і починає повертати H3 у рядок (що вимагає $500$ мс). У той самий час Робот A починає переміщати S8 на стіл B (що вимагає $700$ мс).

• На 1500 мс Робот B завершує повернення H3 і починає переміщати H4 на стіл A (що вимагає $700$ мс).

• На 1700 мс Робот A завершує покладання S8 і починає переміщати S9 на стіл B.

• На 2200 мс Робот B завершує покладання H4 і починає переміщати H3 на стіл A.

• На 2400 мс Робот A завершує покладання S9 і починає переміщати S5 на стіл A.

• На 2900 мс обидва роботи завершують покладання карт на стіл A. Оскільки Робот B переміщує карту на стіл ліворуч від нього, Робот B завершує покладання H3. Робот A переривається.

• Тепер Робот B завершив переміщення всіх розданих карт, тому Робот B виграє цю гру.