Задачка про пиратов

[Gaziz]

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

[Дочь л-та Шмидта]

Ну, это совсем простенькая задачка, в одно действие. Та же задачка усложняется, если есть 10 очень жадных пиратов, и в случае, если кто-то не согласен с дележом, делящего скармливают акулам. Но тогда делить должен следующий.

[Waterbyte]

Ну и? Чего тянете-то? Каков алгоритм-то? "негомогеничным"... Газиз, с "нефотогеничным" не перепутал? Напомнило моего шефа с его "гетерофазными" системами...

[Gaziz]

Алгоритм очень элегантный - один из пиратов делит добро на 2 кучки а второй выбирает себе одну из них.

Задача немного усложняется когда появляется третий пират - попробуйте решить сами

[Stanislav]

Алгоритм очень элегантный - один из пиратов делит добро на 2 кучки а второй выбирает себе одну из них.
Задача немного усложняется когда появляется третий пират - попробуйте решить сами

Задача давно решена для N делящих - один отворачивается, а остальные делят на равные кучки. Потом отвернувшегося спрашивают, показывая на случайную кучку - это кому? Он отвечает - Иванову. и т.д.

[Waterbyte]

Алгоритм очень элегантный - один из пиратов делит добро на 2 кучки а второй выбирает себе одну из них.
Задача немного усложняется когда появляется третий пират - попробуйте решить сами

Задача давно решена для N делящих - один отворачивается, а остальные делят на равные кучки. Потом отвернувшегося спрашивают, показывая на случайную кучку - это кому? Он отвечает - Иванову. и т.д.

Stanislav, с таким алгоритмом скармливание отвернувшегося акулам по версии дочери л-та обеспечено. Метод индукции применять надоть, однозначно. Вот тока как?

[Дима]

Первый отрезает 1/N-ую, по его мнению, часть, но не забирает ее, а становится в конец очереди. Второй имеет выбор: взять этот кусок или стать в конец очереди. Если никто из очереди этот кусок не берет, он достается первому. И.т.д. Для чистоты эксперимента очерердь можно перемешивать сразу после отрезания кусочка...

[Дочь л-та Шмидта]

Я напутала, извините. В задачке про десятерых пиратов и акул было гомогеничное содержимое. (Жемчуг, по-моему).
А про трех пиратов - разное. Они по-разному решаются.

[Дима]

Во, придумал Изначально это задачка была про дележку торта, оттого у меня и куски в решении Но вернемся к сокровищам (негомогеничным).

Шаг 1: первый пират выделяет минимально возможную кучку, которую он хотел бы получить.

Шаг 2: 3 варианта.
1. Никто из оставшихся эту кучку не хочет. Тогда она достается первому. Переходим к шагу 1 без уже осчастливленного пирата и с оставшейся кучей.
2. Эту кучку хочет еще один пират. Кучка достается этому одному. Переходим к шагу 1 без уже осчастливленного пирата и с оставшейся кучей.
3. Эту кучку хотят несколько пиратов(возможно, все). Переходим к шагу 3

Шаг 3: (в случае, когда на первую кучку более двух желающих):
1. Следующий пират может отнять от кучки немножко, чтобы остаток его все равно удовлетворял. Переходим к шагу 1 с этой кучкой и подгруппой, из которой исключен первый пират.
Если этот пират не хочет отнимать, берем следующего.
2. Никто из пиратов не хочет уменьшать кучку. Тогда она достается первому, который кучку и отмерил. Переходим к шагу 1 с оставшейся кучей.

Так как на любом этапе подгруппа пиратов уменьшается, то алгоритм конечен. Ну и "никто не уйдет обиженным"

[spavel]

с негомогеничным ( ) сокровищами проблема. Они могут не делится на N (при N > 1)

[Дима]

с негомогеничным ( ) сокровищами проблема. Они могут не делится на N (при N > 1)

В условиях задачи нету слова "поровну". Каждый просто должен быть доволен своей долей

[spavel]

ну возьми 4 монеты и 6 человек как пример.

[Waterbyte]

Чё-то не вполне ясно. Вопросы имею.

Шаг 3: (в случае, когда на первую кучку более двух желающих):

А что, если не более, а ровно два?

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

И что в таком случае достаётся первому пирату? На каком из следующих этапов он может присоединиться назад к группе, если "его" кучка без чего-то уже ушла кому-то ещё?

[Дима]

А что, если не более, а ровно два?

Нет разницы, 2 или более. Первый пират отложил кучку, которая понравилась еще ровно двоим. Далее эти двое переходят к шагу 3 - уменьшению этой кучки. Кучка в конечном итоге достается тому, кто ее последним уменьшил.

И что в таком случае достаётся первому пирату? На каком из следующих этапов он может присоединиться назад к группе, если "его" кучка без чего-то уже ушла кому-то ещё?

Правило простое: если кучка, созданная первым пиратом, была уменьшена, то он не принимает участие в ее дележке(напомню, что первый пират изначально должен создать МИНИМАЛЬНО возможную кучку, на которую он согласен). Соответственно, он возвращается в общую группу и примет участие в распределении следующей кучки.

[Дима]

Хех, упростим идею
Все пираты выстраиваются в очередь. Первый насыпает устраивающую его кучку и становится в конец очереди. Каждый следующий из очереди имеет 2 опции: либо выйти из очереди (и не принимать участия в дележе этой кучки), либо уменьшить кучку и стать в конец очереди. Процесс заканчивается, когда в очереди остается 1 пират. Кучка ему и достается. Как нетрудно заметить, этот пират и был последним, кто уменьшил кучку.