В этот бар ходят необщительные посетители. Вдоль барной стойки расположены 25 мест. Всякий раз, когда входит новый посетитель, он обязательно садится на самое дальнее, насколько это возможно, место от остальных гостей. Никто не садится рядом с кем-то: если посетитель входит и видит, что "свободных" мест нет, он тут же разворачивается и уходит из бара. Бармену, естественно, хочется, чтобы за стойкой сидело как можно больше клиентов. Если ему разрешено усадить первого посетителя на любое место, куда выгоднее его посадить с точки зрения бармена?
Ответ: На девятое место с конца, неважно слева или справа. Тогда люди рассядутся в итоге на места с нечетными номерами, что дает максимально возможное число посетителей -13
Комментарии
по-моему можно и на крайнее посадить и на середину, с тем же результатом
Если посадить, как Вы предлагаете, клиенты рассядутся через два места, то есть одно занятое, два свободных, одно занятое, два свободных и так далее. Проверьте сами, мест всего 25 — это несложно.
да, точно )
ff
Усадить на 17 место (оно же 9-е).
Для любого количества мест (положим, N) алгоритм такой:
Нужно построить ряд чисел: 2, 3, 5, 9, 17 и т. д., где каждый член является степенью двойки плюс один. То есть i-й член равен 2i+1. В этом ряду нужно выбрать наибольшее число ?N, и на место с этим номером посадить первого клиента. Это заставит большую половину мест быть занятой ровно через одно. А меньшая половина сядет как попало. При этом если дополнить условия задачи так, что бармен может выбрать место и для второго клиента, то нужно будет сажать его в меньшую половину, пользуясь тем же алгоритмом. И то же для третьего и т. д. Такие пироги.
В задаче нет никакой сложности, чтобы при решении пользоваться формулами.
Совершенно очевидно, что места в итоге должны быть заняты через одно, причем их максимум составит 13 (13>25/2>12), что обеспечит занятость крайних мест (т.е. 1 и 25), а также других нечетных мест. Учитывая условие задачи, заполняемость мест нужно рассматривать относительно равномерности заполняемости некоторых групп нечетными местами - их может быть либо 2, либо 3. Тот, кто, поддавшись соблазну, посадит первого посетителя посередине (на 13-е место), получит 2 группы мест: с 1 по 15 и с 15 по 25, в каждой из которых займется четное место. Значит, число групп должно быть 3, а именно: с 1 по 9, с 9 по 17 и с 17 по 25.
это только гарантирует, что основная часть успешно пудет дельтьися на 2 ровные части и в итоге заполнится равномерно через 1-го.
Но вторая часть может заполниться не так хорошо, например, через двоих. Тфк что по-моему, это не общее решение, просто совпало так, что в этой задаче этот подход дал правильный результат
Нужно демонтировать четные места :)
самый правильный ответ!Если половина мест всё равно не используется то на фиг они нужны!
Тогда четные места станут соседними
С точки зрения бармена, если человек общительной и он это чувствует то он бы посадил как можно его ближе к себе.
Что за бред если посадить на 13 место точнее в самую середину как раз таки и будет занято 13 мест.... посчитайте.
Нет, это не так. Если продемонстрировать это наглядно, всё становится ясно.
Если посадить первого клиента 9 место, то клиенты будут рассаживаться таким образом (0 - свободное место, 1 - занятое):
01 0 1 1 1
02 0 0 0 0
03 0 0 0 1
04 0 0 0 0
05 0 0 1 1
06 0 0 0 0
07 0 0 0 1
08 0 0 0 0
09 1 1 1 1
10 0 0 0 0
11 0 0 0 1
12 0 0 0 0
13 0 0 1 1
14 0 0 0 0
15 0 0 0 1
16 0 0 0 0
17 0 1 1 1
18 0 0 0 0
19 0 0 0 1
20 0 0 0 0
21 0 0 1 1
22 0 0 0 0
23 0 0 0 1
24 0 0 0 0
25 0 1 1 1
А если посадить его в середину, то так:
01 0 1 1 1
02 0 0 0 0
03 0 0 0 0
04 0 0 0 1
05 0 0 0 0
06 0 0 0 0
07 0 0 1 1
08 0 0 0 0
09 0 0 0 0
10 0 0 0 1
11 0 0 0 0
12 0 0 0 0
13 1 1 1 1
14 0 0 0 0
15 0 0 0 0
16 0 0 0 1
17 0 0 0 0
18 0 0 0 0
19 0 0 1 1
20 0 0 0 0
21 0 0 0 0
22 0 0 0 1
23 0 0 0 0
24 0 0 0 0
25 0 1 1 1
А зачем? Если они и так начинают с 25-го и их получается 13?
А мне кажется, что правильным будет ответ-любое нечётное место. Ведь в условии сказано что посетители будут садиться максимально далеко от уже сидящих, в итоге заполнение будет максимальным. 1-25-13-7(19)-3(17)-5-15-21-23-11-9