|
Торт: разрезаем и едим | ☑ | ||
---|---|---|---|---|
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) алгоритм не противоречащий условиям задачи.
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |