Имя: Пароль:
IT
 
Торт: разрезаем и едим
0 Ненавижу 1С
 
гуру
09.12.14
09:57
Мальчик разрезал торт на 10 частей (не обязательно равных).
Потом взял и съел самый маленький кусочек (если таких несколько, то любой из них).
Потом разрезал один из оставшихся кусков на 2 и снова съел самый маленький из 10.
И последний раз разрезал один из кусов на два и съел самый маленький из 10.

Вопрос: какую максимальную часть торта мог съесть мальчик?
1 KnightAlone
 
09.12.14
09:59
20% торта макс
2 hunter76
 
09.12.14
10:00
<= 1/10
3 Кай066
 
09.12.14
10:00
От балды - 3/8
4 Aleksey
 
09.12.14
10:01
(1) Почему я могу и 80% съесть при такой формулировки
5 YFedor
 
09.12.14
10:01
4/20
6 Fish
 
09.12.14
10:01
(2) Неправильно.
7 KnightAlone
 
09.12.14
10:01
так как он ест только самый маленькие куски, то чтобы съесть больше - самый маленький кусок должен быть максимально большим, значит резать надо на равные части. сначала режим на 10 равных. съедаем 1/10. потом режем 1/10 на равные половинки, в 2 итерации съедаем еще 1/10
8 Timon1405
 
09.12.14
10:02
3/14
9 Кай066
 
09.12.14
10:02
я могу съесть так 37,5 %
10 PuhUfa
 
09.12.14
10:03
20%
11 MiniMuk
 
09.12.14
10:06
Отрезаем 1/100 1 часть потом еще раз 1/100 - вторую , потом еще 1/100 - тертью.
Остальное делим на 7 равных частей. Получаем 10 не очень равных частей.
Съдам первую.  Делим большой кусок пополам, съедам второй, еще один кусок делим -съедаем третий кусок.
Ответ мальчик съел столько сколько хотел
12 Кай066
 
09.12.14
10:08
(7) во второй итерации получаеи 2 по 1/20й, значит съесть можем только 1/20 во второй итерации, в 3й съедаем ещё 1/20. 1/10+1/20+1/20
13 hunter76
 
09.12.14
10:09
1 раз - съел максимиум - 1/10
2 раз - макс. 1/20
3 раз - макс. 1/20
итого: 2/10 = 1/5, т.е., 20%
14 KnightAlone
 
09.12.14
10:10
(12) че сказать то хотел? 1/10+1/20+1/20 = 20%, что я и написал в (1)
15 KnightAlone
 
09.12.14
10:11
"в 2 итерации съедаем еще 1/10" в две итерации съедаем еще 1/10 - два раза едим по 1/20
16 Кай066
 
09.12.14
10:11
(14) аа, в "две" итерации, а я думал во "второй"
17 Адский плющ
 
09.12.14
10:13
Разделяем торт на части:
1/12 - 8шт
2/12 - 2шт

Съедаем 1/12, на втором шаге делим 2/12 и съедаем ещё 1/12. На третьем тоже самое.


В итоге съели 3/12 = 1/4
18 Timon1405
 
09.12.14
10:14
(12),(14) делим на 14 частей: 1,1,1,1,1,1,1,1,2,2.
1) едим 1
2) делим 2 пополам, едим 1,
3) делим 2 пополам, едим 1
итог 3/14 торта = 21,42%.
Кто больше?)
19 Timon1405
 
09.12.14
10:16
(18), упс, каюсь, у меня с арифметикой беда) получается так же как в (17)
20 Lama12
 
09.12.14
10:16
(13) +1
21 Ненавижу 1С
 
гуру
09.12.14
10:17
жадные 1С-ники, что вы сразу есть начинаете по максимуму?
22 hunter76
 
09.12.14
10:18
(18) почему на 14?
23 Ymryn
 
09.12.14
10:19
(18) пока придерживаюсь этого же решения.
24 AS_DANCE
 
09.12.14
10:22
(18) А почему 14 а не 12??
2/12 = 1/6 максимум что съест мальчик!
25 AS_DANCE
 
09.12.14
10:23
Взяли кусок, разделили на 2 части стало 2 куска. То есть был 1 и появился еще 1!
было 10, в начале стало 11
потом стало 10
потом опять 11
потом опять 10
появилось за все итерации только 2 кусочка!
26 Адский плющ
 
09.12.14
10:24
(21) Что про (17)?
27 SUA
 
09.12.14
10:25
(24)а почему 2 если 3?
28 Ymryn
 
09.12.14
10:25
(18) только действительно 3 / 12, т.е 1 / 4
29 Timon1405
 
09.12.14
10:25
(26) Осталось доказать, что больше нельзя
30 KnightAlone
 
09.12.14
10:26
(17) да, так лучше будет ) 25% получается
31 Локи-13
 
09.12.14
10:28
11 ответ как по мне самый правильный)
32 Локи-13
 
09.12.14
10:28
а там максимальная часть... плохо прочитал условие(
33 Ненавижу 1С
 
гуру
09.12.14
10:31
(26) пропустил, да верно, а больше нельзя?
34 Локи-13
 
09.12.14
10:33
вообще да, 20%
35 SUA
 
09.12.14
10:33
17 похоже на правду:
всего кусков после 3х разрезаний 12
съедено из них 3 минимальных, 3/12=25%
36 Ymryn
 
09.12.14
10:34
(35) тебе надо доказать, что при переходе к 3 из 12 ты всегда ешь минимальные. В общем случае - это неочевидно.
37 KnightAlone
 
09.12.14
10:37
(36) в (17) вроде предельно четко алгоритм описан. что там неочевидно?
38 AS_DANCE
 
09.12.14
10:38
Тут заковыка, он резал случайные куски, а ел минимальные
39 Ymryn
 
09.12.14
10:38
(37) в (17) частный случай. Нет доказательства, что это максимальное значение.
40 Timon1405
 
09.12.14
10:39
(37) неочевидно, что он дает максимальный результат, например, если сначала отрезать 1/11, а потом остатки по-другому распределить, вдруг будет еще лучше
41 Адский плющ
 
09.12.14
10:39
(33) Порядок поедания/отрезания тут неважен (это можно отдельно доказать, думаю)
Т.е. мальчик мог тупо порезать торт на 12 частей а потом съесть три минимальных.
42 Ненавижу 1С
 
гуру
09.12.14
10:40
(36) Итак реально, всего кусков 12

a1<=a2<=a3<=...<=a12
a1+a2+a3+...+a12=1

Очевидно мальчик съел a1+a2+a3, но
a1+a2+a3<=a1+a2+a3
a1+a2+a3<=a4+a5+a6
a1+a2+a3<=a7+a8+a9
a1+a2+a3<=a10+a11+a12

складываем: a1+a2+a3<=(a1+a2+a3+...+a12)/4=1/4
43 Ymryn
 
09.12.14
10:42
(42) Неочевидно. Где гарантия, что разрезая он сперва не съел а4, а потом а2 и а1, так как как а3 получился только на 2 интерации?
44 Krendel
 
09.12.14
10:42
Берем самый простой вариант 10 кусков равномерных.

едим 1-й
делим любой в пропорции пополам у нас 2 куска по 5 и они минимальны


Итого 20 %
по ощущениям предел должен быть в районе 25 %
45 hunter76
 
09.12.14
10:42
максимально - это если сначала порезал на 10 равных частей, съел 1/10, потом 2 раза оставшиеся нетронутые куски резал ровно пополам и съел еще 2 раза по половине 1/10, т.е., 2 раза по 1/20
46 AS_DANCE
 
09.12.14
10:43
согласен обсчитался, 3/12 = 1/4 !))
47 Krendel
 
09.12.14
10:44
(45) неравномерным можно достичь большего
48 Ymryn
 
09.12.14
10:45
(43) *итерации. Приношу извинения.
49 hunter76
 
09.12.14
10:46
(47) всегда ел минимальный кусок, так что вряд ли...
50 Кай066
 
09.12.14
10:49
(47) как раз таки равномерным больше. Всё правильно, сначала режем на 10, потом ещё 2 раза, т.е. всего на 12 частей. Если резать равномерно и жрать по 1/12, то и получаются максимальные 3/12, т.е. 25%
51 palladyi
 
09.12.14
10:53
17,5%
52 13_Mult
 
09.12.14
10:54
3/16
53 KnightAlone
 
09.12.14
10:54
(51) неудачник?) здесь уже выложено 2 алгоритма, как можно съесть 20% и 25%
54 Лефмихалыч
 
09.12.14
10:55
Исходя из того, что всегда мальчик ест самый маленький из имеющихся кусков:
1. В первый раз максимум, который он может съест - это 0.1 торта. при любом неравном делении кусков он съест меньше 0.1
2. Соответственно по второй раз он не сможет съесть больше 0.1/2=0,05
3. остаются куски по 0.1 и 0.05, то есть у него два варианта - либо резать 0.1 пополам, либо 0.05. Исходим из того, что мальчик не идиот и режет максимальный, то есть он съедает еще 0.05
Игого: 0.1+0.05+0.05 = 0.2 торта, то есть 20%
55 13_Mult
 
09.12.14
10:55
Кстати, а торт круглый? ))
56 palladyi
 
09.12.14
10:55
(53) =( Некорректно прочитал ТЗ =(
57 KnightAlone
 
09.12.14
10:56
опровергни (17). он съест в первый раз меньше 0.1 зато потом нагонит и перегонит
58 KnightAlone
 
09.12.14
10:56
(57) это к (54)
59 Иэрпэшник
 
09.12.14
10:58
2/10
60 Лефмихалыч
 
09.12.14
10:58
(57) а, ну или так
61 Кай066
 
09.12.14
10:58
(55) А какая разница? Треугольный, допустим
62 13_Mult
 
09.12.14
10:59
(61) на круглом считать проще. )
63 hunter76
 
09.12.14
11:02
(0) а торт равномерен по плотности?
64 KnightAlone
 
09.12.14
11:04
(63) хороший вопрос!
65 Krendel
 
09.12.14
11:05
Зададимся получением 21

Нам нужны следующие куски 7+14+14+7*9= 98
66 KnightAlone
 
09.12.14
11:05
(0)"Вопрос: какую максимальную часть торта мог съесть мальчик?"

максимальную в объеме или в весе?)
67 hunter76
 
09.12.14
11:06
(64)я анекдот вспомнил про еврейского мальчика, перед которым клали 2 монетки 3 и 5 шекелей. он всегда брал 3, она была больше по размеру. так повотрялось много раз.
Ребе спросил, почему ты поступаешь так неразумно? Возьми 5!
мальчик ответил, если я так сделаю, они перестанут давать мне деньги.
68 Krendel
 
09.12.14
11:06
+(65) цель 24

8+16+16 +7(8,57)
69 Кай066
 
09.12.14
11:06
(66) а пофиг, если надо по объёму, то делим на 12 равных по объёму, а если по весу, то делим на 12 равных по весу.
70 Classic
 
09.12.14
11:06
(54)
Жадный алгоритм не всегда приводит к максимальному результату
71 Krendel
 
09.12.14
11:07
Соответсвено предел 25%
72 Ненавижу 1С
 
гуру
09.12.14
11:07
(43) "дорезаний" было два, а кусочков среди "маленьких" a1, a2, a3 -  три, поэтому хотя бы один был получен изначально
вот меньший из "маленьких" и едим
делаем дорезание №1, если появился "маленький" - опять едим его, если не появился, то уже был, все равно едим его
и так же со вторым дорезанием
73 13_Mult
 
09.12.14
11:07
(63) + и по высоте
74 Кай066
 
09.12.14
11:08
(71) это уже в (17) стало извесно
75 zva
 
09.12.14
11:09
Вопрос: какую максимальную часть торта мог съесть мальчик?
Мог весь торт съесть, в условии же не сказано, что он после третьего куска есть остановился, он только последний раз торт разрезал...
76 Deni7
 
09.12.14
11:09
(0) Можно съесть четверть (25%) торта
77 Krendel
 
09.12.14
11:09
(74) Чукча не читатель ;)
78 Ymryn
 
09.12.14
11:13
В общем, пока решение видится в таком виде.

Чтобы съесть максимум торта, нам надо съесть максимум в каждой итерации. Возьмем последнюю 3 итерацию. У нас есть десять кусков и из них надо съесть 1. Максимум функции F = Min(A) достигается, если A - однородное, т.е. все куски одинаковые на 3 итерации. Откатываемся ко 2 итерации. Для того, чтобы нам съесть максимум торта, кусок, который мы съели, должен быть больше либо равен минимальному куску в третьей итерации. Учитывая, что все куски в третьей итерации однородны и что мы обязаны съедать минимальный во второй итерации, мы получаем, что во второй итерации мы съели такой же кусок, как и в третьей. Аналогично доказываем первую итерацию. Итог мы получаем, что мы съели 3 из 12 равных кусков. Т.е. максимум 25%.
79 s-n-a-y
 
09.12.14
11:15
(0)
Пусть объем  всего торта равен 1
Ответ: 1/2 + 1/4 + 1/8 - Е, где Е > 0 - сколь угодно малое число.
80 Deni7
 
09.12.14
11:15
(78) "Чтобы съесть максимум торта, нам надо съесть максимум в каждой итерации." - это неочевидно. Может максимум достингается разными размерами?
81 Ymryn
 
09.12.14
11:16
(80) это очевидно. Если ты съедаешь в 3ей не максимум - значит это не оптимальное состояние и можно найти лучшее. Значит в ей также надо есть максимум.
82 Classic
 
09.12.14
11:17
(78)
Первое предложение неверное.
83 Xapac
 
09.12.14
11:17
как лесица сыр делила?
84 Ненавижу 1С
 
гуру
09.12.14
11:17
(78) согласен, динамическое программирование, рассуждения с конца процесса
85 Classic
 
09.12.14
11:17
(81)
В максимальном примере (25%) как раз первый раз не максимальный. Максимальным за первый раз является 10% от торта.
86 Ненавижу 1С
 
гуру
09.12.14
11:17
(82) первое предложение лишее, скажем так
87 Ymryn
 
09.12.14
11:18
(82), если ты съел не максимум - значит это не оптимальное решение. Ибо можно съесть больше. Следовательно максимум надо есть на каждой итерации.
88 Гёдза
 
09.12.14
11:19
Максимум в последней итерации, но не обязательно в первых двух
89 Classic
 
09.12.14
11:20
(87)
Читай про жадные алгоритмы и матроиды
90 Xapac
 
09.12.14
11:22
а ответ получается 3/20
91 Ymryn
 
09.12.14
11:25
(85) там доступный максимум. Как бы максимум для функции Min(A), а не Максимум из кусков.
92 s-n-a-y
 
09.12.14
11:28
Если после первого деления торта мальчик делил куски на две равные части, то ответ 1/10 + 1/10 + 1/10 - Е = 3/10 - Е, Е>0 - сколь угодно малое
Если делил на 2 НЕравные части, то ответ 1/10 + 1/20 + 1/40 - Е = 7/40 - Е, Е>0 - сколь угодно малое
93 s-n-a-y
 
09.12.14
11:31
(92) ответы местами перепутал.
Если делил на 2 равные, то 7/40 - Е
Если делил на 2 неравные, то  3/10 - Е
94 Жан Пердежон
 
09.12.14
11:31
сходу же 20%
95 Deni7
 
09.12.14
11:32
(93) Правильный ответ видимо в (17), тока доказательства строгого пока нет.

(94) Нужно максимизировать долю.
96 Ymryn
 
09.12.14
11:33
(89) ну так вроде именно это здесь и используется, если я все правильно помню и понимаю.
97 Кай066
 
09.12.14
11:36
(95) всего 12 долей, максимальная минимальная ))) доля 1/12, какие ещё нужны доказательства?
98 Иэрпэшник
 
09.12.14
11:37
10,75%. Вроде так
99 Xapac
 
09.12.14
11:37
я не пойму что то чё вы тут рассуждаете
чтобы съесть наимбольший наименьший кусок нужно поделить торт на равные части.
то есть на 1/10. и мы съедаем кусочек.
затем парень режет ещё один кусок (любой вить все равны)
тоесть 1/10/2 = 1/20 и ест его(как минимальный)
потом повторяет(решет 1-н большой и ест половину(1/20)

получается 1/10+1/20+1/20 = 4/20 или 1/5 = 0,2
100 Иэрпэшник
 
09.12.14
11:38
(98) Пардон, 15,25%
101 Deni7
 
09.12.14
11:39
(97) Это доказательство такое :)?
102 Иэрпэшник
 
09.12.14
11:40
(100) Не, 17,5%. Вроде так.
103 13_Mult
 
09.12.14
11:49
Похоже Адский плющ самый сытый будет )
104 RomanYS
 
09.12.14
12:29
1/4
105 Помогите
 
18.12.14
09:04
25%
106 Помогите
 
18.12.14
09:04
(104) опередил, блин
107 Ненавижу 1С
 
гуру
18.12.14
09:07
(106) из Эстонии?
108 Помогите
 
18.12.14
09:11
(107) Когда писал ответ, не видел вторую страницу.
109 ikbokov
 
18.12.14
09:31
3/12=1/4
10 кусков 8 по 1/12 и 2 по 1/6
Сожрал 1/12, 1/6 разрезал на 2
Сожрал еще 1/12, 1/6 поделил на 2, сожрал еще 1/12
110 Помогите
 
18.12.14
09:44
(109) я считал 9 кусков по 1/12 и 1 по 3/12, который два раза будет резать. Но суть не меняется.
111 ikbokov
 
18.12.14
09:52
(110) тут все упирается в осознание что всего кусков будет 12, и есть он будет 3 минимальных из них, а дальше уже не важно)
112 BayoNet
 
18.12.14
10:23
Мальчик конечно странный, на всю голову
113 Помогите
 
18.12.14
11:31
(112) Вполне нормальный, если предположить что его попросили нарезать торт на 9 частей, но не есть, а он очень хотел съесть и чтобы это никто не заметил.
114 YHVVH
 
18.12.14
11:46
(99) неа, торой раз он разрезал большой кусок
115 YHVVH
 
18.12.14
11:47
50% Точно сожрет
116 YHVVH
 
18.12.14
11:49
максимум будет 50% + 25% итого 75%
117 KrivosheevE V163rus
 
18.12.14
12:49
Да, как у вас такие цифры-то получаются?

Из 10 неравных или равных долей мелкий подлец ополовинил две. В итоге - 12 долей. Съел 3 наименьшие доли.
Задача - превратить съеденные 3 наименьшие доли в максимально большие.
Как только одна из трёх выбранных долей будет больше любых других наименьших трёх, то она перестаёт быть наименьшей.
Выход один - уровнять полученные 12 долей. Условие, описанное мной, не обеспечивает, но и не противоречит условию автора задачи.
3/12 = 1/4 = 25%
118 Casey1984
 
18.12.14
19:06
Моё решение:

Максимальный первый кусок: 1/10
Максимальный второй кусок: 1/20
Максимальный третий кусок: 1/40

Ответ: 1/10 + 1/20 + 1/40 = 7/40 = 17,5%

Будет правильный ответ, или я его просмотрел?
119 Casey1984
 
18.12.14
19:08
(118) Максимальный кусок, то есть режем на равные куски:)
120 User_Agronom
 
18.12.14
19:10
30%
121 Casey1984
 
18.12.14
19:19
(33) Почему верно, если он резал-жрал-резал-жрал...? ;)
122 Куро
 
18.12.14
19:21
у нас технологи карту раскроя торта делают на компе)))
123 Злопчинский
 
18.12.14
20:28
Предлагаю собраться в пивбаре и смоделировать на пиве!!!
124 RomanYS
 
18.12.14
22:01
(118) ЦБ по твоей формуле ключевую ставку считал... однажды ночью
125 Помогите
 
19.12.14
05:52
(118) Правильный ответ уже был в (105)
126 Помогите
 
19.12.14
05:53
(123) С тобой что ли? Никто не придет.
127 sda553
 
19.12.14
07:19
Решаем в обратном порядке, пытаемся добавлять к изрезанному торту куски и склеивать их так, чтобы добавить как можно больше.

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

Итого 9+1+1+1=12

Значит, съели 3/12
128 lopus
 
19.12.14
07:48
Первый раз он съел минимальный из 10 то есть максимум 1/10,
второй раз взял из 9 оставшихся который был 1/10 еще располовинил считаем равными 1/20, и еще раз 1/20, 1/5 то.е 20%
129 KrivosheevE V163rus
 
19.12.14
08:53
(128)
Цель задачи - найти максимально-возможный съеденный объем торта.
Мальчик может сожрать больше.
130 SerGo-116
 
19.12.14
15:38
четверть торта
131 Casey1984
 
19.12.14
18:34
(125) Почему он правильный?
132 Ndochp
 
19.12.14
18:56
(131) Потому, что он больше, чем твои 17,5 и в (109) алгоритм не противоречащий условиям задачи.