Вхід і реєстрація
Статті · 9 червня 2008, 9:09 1262
Alexander Skakunov, Founder в Місія на Марс

Трудный вопрос на собеседовании #2

Продолжаем серию переводов цикла «Трудные вопросы на собеседовании».

Задача #2

Рассмотрим игру, в которую играют двое на круглом столе неопределенного диаметра. Каждый игрок имеет безграничное количество одинаковых монет (четвертаков) и ходит, располагая монету на столе так, что она целиком находится на столе и не накрывает другие монеты, расположенные на игровом поле. Побеждает тот игрок, который делает последний допустимый ход. У кого из игроков (если таковой будет) может быть стратегия, гарантирующая победу, и какова эта стратегия?

Ждите ответ через неделю!

UPDATE: решение

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

Теми: задача, співбесіда
👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn



18 коментарів

Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.
anonymous 20.09.2010 21:58

да, она реально выигрышная

Відповісти
Підтримати
anonymous 20.09.2010 21:58

2Sanya: прочитай внимательней комментарий под номером 17. Есть понятие того, что означает «диаметрально противоложно»?

Відповісти
Підтримати
anonymous 20.09.2010 21:58

А вариант, когда монеты выкладываются на столе неплотно не рассматривается? Как известно, вокругодной монеты впритык укладывается шесть таких же монет. Допустим, после первого хода первого игрока в центр, начинается «обкладывание» центральнаой монеты. Но если второй игрок третьим ходом (т.е. когда остается место для двух монет рядом) положит свою монету вплотную к центральной, но на определенном расстоянии от соседних, то первый игрок не может сделать симметричный ход, не расширив диаметр занятого монетами круга.

Відповісти
Підтримати
Alexander Skakunov Founder в Місія на Марс 20.09.2010 21:58
Итак, оригинальный ответ:

У игрока 1 есть выигрышная стратегия. Его первым ходом должно быть расположение монеты в точном центре стола. Если это уже достаточно вам сказало, то, думаю, дальше вам лучше не читать. Если же вы до смерти хотите узнать все остальное, читаем дальше.Затем игрок 2 располагает монету где-либо на столе (но не в центре, разумеется). Теперь убедимся, что игрок 1 всегда имеет допустимый ход: располагая монету диаметрально противоложно только что поставленной монете игрока 2 (т.е. самый первый ход игрока 1 будет средней точкой на линии между последним ходом игроков 1 и 2). Продолжаем, пока стол не заполнится, но т.к. игрок 1 всегда имеет допустимый ход, игрок 2 столкнется с тем, что у него-то допустимого хода нет. И игрок 1 побеждает.Обратите внимание, что эта стратегия работает даже в вырожденном случае, когда стол имеет размеры четвертака.

Відповісти
Підтримати
anonymous 20.09.2010 21:58

А если размер монеты больше диаметра стола, то выиграет второй игрок, поскольку первый не сможет положить свою монету.

Відповісти
Підтримати
anonymous 20.09.2010 21:58

Если диаметр стола «неопределенный», и монеты — тоже, то возможна ситуация, когда диаметр монеты будет больше или равен диаметру стола. В таком случае первый игрок побеждает всегда:)

Відповісти
Підтримати
anonymous 20.09.2010 21:58

У второго игрока может быть стратегия гарантирующая победу в том случае, если первый игрок первым ходом не поставит монетку в центр — поставить монетку близко к центру настолько, чтобы в центре «слота» для монетки не осталось и далее играть симметрично ходам первого игрока...:)

Відповісти
Підтримати
Aleksey Kolupaev CTO в eduki 20.09.2010 21:58

Центральная симметрия необязательна, достаточно и осевой.

Відповісти
Підтримати
Микола Палієнко CEO в EVO 20.09.2010 21:58

Задача имеет одинаковое решение для стола в виде любой центральносимметричной фигуры.решение предложено в первоых трех коментарияхСледующий.

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 20.09.2010 21:58

А для эллиптического стола с полуосями a и b и радиусом монетки c?

Відповісти
Підтримати
Alexander Shelpuk Software Developer в Petcube 20.09.2010 21:58

Хотів би поділитись своїми роздумами. Висловлена умова про те, що «для правильных многоугольников точно ничего не меняется =) » не є достатньою та і необхідною також. Скажімо для трикутників висловлена раніше стратегія не підійде. Але вона чудово працює у випадку такого неправильного многокутника, як прямокутник.Ця задача вирішується виказаною стратегією у випадку будь-яких фігур симетричних відносно свого геометричного центра. Для прикладу стіл може бути прямокутником, а фігура правильним шестикутником. Для правильних многокутників можна зробити поправку на те, що вони повинні мати парну кількість вершин...Ну, а у випадку фігур несиметричних відносно свого геометричного центру... То тут треба враховувати розмір фігури у стола (=

Відповісти
Підтримати
anonymous 20.09.2010 21:58

Вспомнился анекдот про козірній пипец:)

Відповісти
Підтримати
anonymous 20.09.2010 21:58

Можно уточнение? Игроки ходят пошагово, как в шахматах? Или же на время кто быстрее?:)

Відповісти
Підтримати
anonymous 20.09.2010 21:58

для правильных многоугольников точно ничего не меняется =)

Відповісти
Підтримати
Sergii Voloshyn Product Manager в DOU.ua 20.09.2010 21:58

Интересно, что меняется, если стон не круглый, а квадратный? И монетки квадратные:)

Відповісти
Підтримати
Dmytro Chudov CEO в Chudovo OÜ 20.09.2010 21:58

достаточно положить первым монету по центру. Потом, учитывая что стол круглый, в любом случае найдется ход у первого.

Відповісти
Підтримати
alexdolgin 20.09.2010 21:58

Насколько я понимаю, в этой игре выиграет тот, кто ходит первым. Стратегия простая: первым ходом положить монету по центру, каждый следующий ход — клсть монету симметрично предыдушей монете противника.

Відповісти
Підтримати

Підписатись на коментарі

Не підписуватись
Скористайтесь акаунтом
×
з умовами використання сайту і політикою конфіденційності.