Как рассадить интровертов в баре
hard

Как рассадить интровертов в баре

Заходят как-то в бар два интроверта...

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

В Петербурге на улице Рубинштейна есть один бар, в который ходят лишь необщительные люди, назовём их интровертами. (На самом деле интроверты общительные, необщительность — это миф. Но это задачка, поэтому упростим.)

Интроверты садятся вдоль барной стойки, где есть 25 мест. Когда входит новый посетитель, он всегда садится у стойки как можно дальше от остальных гостей. Никто не садится на соседнее место рядом с другим интровертом: если кто-то входит и видит, что свободных мест мало, и надо сесть рядом с кем-то, то он уходит.

Бармен хочет получить как можно больше клиентов. У него есть право посадить самого первого посетителя на любое место у стойки. Куда выгоднее посадить первого интроверта с точки зрения бармена?

Для начала найдём идеальный вариант, который устроил бы бармена. Для этого нарисуем 25 квадратов в ряд и закрасим те, на которых кто-то сидит. Помните, что ни один интроверт по задаче не сядет на соседнее место к другому.

Как рассадить интровертов в баре

Получается, что это самая плотная рассадка, которая возможна в этом баре. Так у стойки сидят 13 человек. Осталось только найти место для самого первого посетителя.

Для начала попробуем решить эту задачу в лоб и посадим первого посетителя на первый стул:

Как рассадить интровертов в баре

Теперь второй посетитель должен сесть на свободное место как можно дальше от него, то есть занять стул № 25:

Как рассадить интровертов в баре

Третьему достаётся стул № 13, так как он ровно посередине между этими двумя:

Как рассадить интровертов в баре

Два следующих займут свободные места точно посередине между центральным и боковыми:

Как рассадить интровертов в баре

И вот тут настаёт момент истины: четыре следующих посетителя тоже сядут точно посередине между занятыми местами. Это значит, что между каждым будет по 2 пустых места:

Как рассадить интровертов в баре

В итоге у нас занято всего 9 мест, но сесть больше никуда нельзя: у каждого свободного стула есть как минимум один занятый сосед. Значит, этот вариант не подходит. Нужен другой.

Чтобы прийти к правильному ответу, попробуем решать задачу с конца.

Вспомним идеальную рассадку:

Как рассадить интровертов в баре

Здесь сидит максимальное количество гостей — 13, и между каждым из них есть свободное место. Отмотаем на шаг назад и посмотрим, как могли бы сидеть интроверты, чтобы новые гости сели точно между ними:

Как рассадить интровертов в баре

В этом случае 6 новых гостей садятся точно посередине между занятыми стульями и идеально заполняют все места.

Теперь сделаем ещё шаг назад и посмотрим, как должны сидеть гости, чтобы новые клиенты сели на нужные стулья:

Как рассадить интровертов в баре

Получается, что если мы посадим первых четырёх гостей так, как на рисунке выше, то дальше всё будет хорошо. Сделаем ещё шаг назад, чтобы понять, как они смогли так сесть:

Как рассадить интровертов в баре

Из рисунка видно, что два новых посетителя должны сесть как можно дальше от занятых мест. Для этого один садится ровно посередине между двумя занятыми, а второй — с самого края, на первое место. Таким образом, между всеми ними будет максимально возможное расстояние. Осталось понять, как сели эти первые два интроверта.

Если бы первый гость сел с краю на стул № 25, второму бы пришлось сесть с противоположного края на стул № 1 (мы это разобрали в самом начале, в неправильном варианте). Значит, первый гость сел на стул № 9, а второму пришлось сесть максимально далеко от него — на самый последний стул:

Как рассадить интровертов в баре

Получается, самого первого гостя бармен должен посадить на стул № 9.

Как так вышло? Просто посчитали от обратного. Программисты называют это Test-First Development, хех.

Обложка:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Вам может быть интересно
Что о вас на самом деле знают Google и Facebook (и все остальные)
Что о вас на самом деле знают Google и Facebook (и все остальные)

Если коротко — они знают о вас почти всё. Но с этим тоже можно что-то сделать.

medium
Как взорвать ракету одной переменной
Как взорвать ракету одной переменной

Краткий мастер-класс по правильному объявлению типов данных.

easy
Почему школьники не любят уроки программирования
Почему школьники не любят уроки программирования

Почему обучение основам программирования в школах такое ужасное и что с этим можно сделать.

easy
Задача про математику и гендерное равенство
Задача про математику и гендерное равенство

Как логика, математика и статистика приводят к созданию новой крепкой семьи.

easy
Школьная загадка про сейф, которая ставит в тупик большинство взрослых
Школьная загадка про сейф, которая ставит в тупик большинство взрослых

Но не программистов.

hard
Парадокс средней оценки
Парадокс средней оценки

Как такое возможно: сделать всё по отдельности лучше всех, но проиграть в общем зачёте?

hard
Задача про команду программистов, тимлида и таск-трекер
Задача про команду программистов, тимлида и таск-трекер

Описание простое, а задачка — нет

easy
Коктейльная задача про доли и крепость
Коктейльная задача про доли и крепость

Ну, будем!

easy
Нестандартная задача про наши счастливые годы: 2020-й и 2021-й
Нестандартная задача про наши счастливые годы: 2020-й и 2021-й

С виду она очень простая, но это не так

medium
hard