fortpost
Высший разум
Offline
Сообщений: 6853
СПАСИБО
-вы поблагодарили: 1794
-вас поблагодарили: 2261
|
|
� : Февраль 06, 2014, 00:08:16 � |
|
Али-Баба делит с разбойником 10 куч золотого песку. Али-Баба может в любой момент взять три кучи и уйти, либо он может выбрать 4 любые кучи и разделить каждую из куч на правую и левую часть. Далее разбойник правые части нетождественно переставляет, и затем части объединяются - каждая левая с новой правой. Сколько сможет Али-Баба унести с собой золотого песку?
|
|
|
Записан
|
Лучший способ оказаться в дураках, это считать себя умнее других. Ф. Ларошфуко
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #1 : Февраль 06, 2014, 12:07:43 � |
|
Показать скрытый текст Наверное как-то так, сводим задачу к кучам монет. Берем всегда 4 самых больших кучи и откладываем от них в сторону 1,2,3,4 монеты (от самой большой одну и т.д.). Что может получиться: 1. Самая большая увеличиться, или 2. 2 увеличивается 1 не меняется, или 3. 1 и 2 не меняются 3 увеличивается.
В тот момент как не будет существовать кучи, отличной от 3-х максимальных, из которой можно забрать 4 монеты, забираем 3 и уходим.
Не очень понимаю, как перевести этот алгоритм в итоговый цифровой ответ.
|
|
|
|
fortpost
Высший разум
Offline
Сообщений: 6853
СПАСИБО
-вы поблагодарили: 1794
-вас поблагодарили: 2261
|
|
� Ответ #2 : Февраль 06, 2014, 12:11:26 � |
|
Показать скрытый текст Наверное как-то так, сводим задачу к кучам монет. Берем всегда 4 самых больших кучи и откладываем от них в сторону 1,2,3,4 монеты (от самой большой одну и т.д.). Что может получиться: 1. Самая большая увеличиться, или 2. 2 увеличивается 1 не меняется, или 3. 1 и 2 не меняются 3 увеличивается.
В тот момент как не будет существовать кучи, отличной от 3-х максимальных, из которой можно забрать 4 монеты, забираем 3 и уходим.
Не очень понимаю, как перевести этот алгоритм в итоговый цифровой ответ. Да в общем оно так!!! З.Ы. В авторском решении удается захапать более 99%
|
|
� Последнее редактирование: Февраль 06, 2014, 12:13:37 от fortpost �
|
Записан
|
Лучший способ оказаться в дураках, это считать себя умнее других. Ф. Ларошфуко
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #3 : Февраль 06, 2014, 12:17:40 � |
|
Показать скрытый текст Наверное как-то так, сводим задачу к кучам монет. Берем всегда 4 самых больших кучи и откладываем от них в сторону 1,2,3,4 монеты (от самой большой одну и т.д.). Что может получиться: 1. Самая большая увеличиться, или 2. 2 увеличивается 1 не меняется, или 3. 1 и 2 не меняются 3 увеличивается.
В тот момент как не будет существовать кучи, отличной от 3-х максимальных, из которой можно забрать 4 монеты, забираем 3 и уходим.
Не очень понимаю, как перевести этот алгоритм в итоговый цифровой ответ. Да в общем оно так!!! З.Ы. В авторском решении удается захапать более 99% я не очень понимаю как это можно посчитать, нужно же делать тогда предположение о количестве песчинок в куче. А если их, допустим по 5 в каждой? Тоже 99% сделает ))?
|
|
|
Записан
|
|
|
|
fortpost
Высший разум
Offline
Сообщений: 6853
СПАСИБО
-вы поблагодарили: 1794
-вас поблагодарили: 2261
|
|
� Ответ #4 : Февраль 06, 2014, 12:38:56 � |
|
Показать скрытый текст Наверное как-то так, сводим задачу к кучам монет. Берем всегда 4 самых больших кучи и откладываем от них в сторону 1,2,3,4 монеты (от самой большой одну и т.д.). Что может получиться: 1. Самая большая увеличиться, или 2. 2 увеличивается 1 не меняется, или 3. 1 и 2 не меняются 3 увеличивается.
В тот момент как не будет существовать кучи, отличной от 3-х максимальных, из которой можно забрать 4 монеты, забираем 3 и уходим.
Не очень понимаю, как перевести этот алгоритм в итоговый цифровой ответ. Да в общем оно так!!! З.Ы. В авторском решении удается захапать более 99% я не очень понимаю как это можно посчитать, нужно же делать тогда предположение о количестве песчинок в куче. А если их, допустим по 5 в каждой? Тоже 99% сделает ))? Предполагается, что песчинок много-премного. Порядка 10 6. Авторское позже будет.
|
|
|
Записан
|
Лучший способ оказаться в дураках, это считать себя умнее других. Ф. Ларошфуко
|
|
|
fortpost
Высший разум
Offline
Сообщений: 6853
СПАСИБО
-вы поблагодарили: 1794
-вас поблагодарили: 2261
|
|
� Ответ #5 : Февраль 06, 2014, 23:40:50 � |
|
А такое вот авторское. Показать скрытый текст РЕШЕНИЕ. Прежде всего, сведем задачу к дискретной. Разделим каждую кучу (с остатком) на мелкие части, размер каждой 10-6 от общего количества песка. Остатком пренебрежем, ибо суммарный размер остатков не больше 10·10-6 = 10-5 от общего числа песка. Будем рассматривать каждую часть как «монетку» и укажем алгоритм, позволяющий Али-Бабе получить более 99% от общего числа монет. Алгоритм действий Али-Бабы заключается в следующем:
1. Всякий раз выбираются 4 самых больших кучи.
2. От самой большой откладывается вправо одна монетка, от второй по величине две, от третьей три, от четвертой четыре.
3. Эти правые части разбойник переставляет, после чего происходит слияние.
4. Если указанную процедуру нельзя провести (т. е. в каждой куче, кроме трех максимальных, не больше чем 4 монеты), то Али-Баба спокойно уходит, забирая три максимальных кучи. Разбойнику достаются копейки. Остается убедиться, что данная процедура заканчивается. В самом деле. За каждый шаг происходит следующее:
а) либо увеличивается максимальная куча,
б) либо не меняется максимальная, но увеличивается вторая по величине,
в) либо не меняются первые две, но увеличивается третья. Ясно, что шагов первого типа конечое число, а когда они кончатся, будет конечное число шагов второго типа, а когда кончатся эти шаги - то третьего. Поэтому процесс остановится. (А.Я. Канель)
|
|
|
Записан
|
Лучший способ оказаться в дураках, это считать себя умнее других. Ф. Ларошфуко
|
|
|
замат
Умник
Offline
Сообщений: 548
СПАСИБО
-вы поблагодарили: 572
-вас поблагодарили: 517
Необходимость не знает закона
|
|
� Ответ #6 : Февраль 07, 2014, 21:02:07 � |
|
Я блин чего то не догоняю. Из10 куч Али-Баба забирает любые 3 или делает 3 масимальные из четырёх любых куч и забирает типа 99% золотого песка. Ну а разбойник забирает 7 оставшихся куч. Ну и как тут 99% получается Сколько песка в этих 7 кучах? Да разбойник просто грохнет его и всё себе заберёт.
|
|
� Последнее редактирование: Февраль 07, 2014, 21:06:43 от замат �
|
Записан
|
«Я знаю, что после смерти на мою могилу нанесут кучу мусора. Но ветер Истории безжалостно развеет ее».И.В.СТАЛИН.
|
|
|
fortpost
Высший разум
Offline
Сообщений: 6853
СПАСИБО
-вы поблагодарили: 1794
-вас поблагодарили: 2261
|
|
� Ответ #7 : Февраль 08, 2014, 01:11:00 � |
|
Я блин чего то не догоняю. Из10 куч Али-Баба забирает любые 3 или делает 3 масимальные из четырёх любых куч и забирает типа 99% золотого песка. Ну а разбойник забирает 7 оставшихся куч. Ну и как тут 99% получается Сколько песка в этих 7 кучах? Да разбойник просто грохнет его и всё себе заберёт. Замат, а вы попробуйте проделать эксперимент. Возьмите 10 кучек по 1000 золотых (это обязательное условие!) монет в каждой, и выполняйте указанный выше алгоритм. В результате получится 7 кучек по 4 монеты в каждой (всего 28), а в оставшихся трех будет 10000-28=9972 монеты. Т.е. имеем 9972/10000*100=99,72%
|
Лучший способ оказаться в дураках, это считать себя умнее других. Ф. Ларошфуко
|
|
|
aqualviv
Новенький
Offline
Сообщений: 3
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
|
|
� Ответ #8 : Февраль 13, 2014, 20:35:57 � |
|
6 куч
|
|
|
Записан
|
|
|
|
|