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

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

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

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

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

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

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

Реше­ние

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ещё по теме