Режем торт

[Sender]

Хорошо. Поскольку для $12$ требуется не более $6$ дополнительных разрезов, это автоматически понижает верхнюю оценку для $12$ гостей до $34$. Оттуда не более $12$ разрезов до следующего рубежа, т.е. $a(13)\leqslant 46$, $a(14)\leqslant 53$. Ясно, что все эти оценки завышенные, но можно поправить в A265286.

[dimkadimon]

Для 12 гостей у меня получилось ещё лучше - 31 кусочка:

58 98 177 208 218 224 233 308 341 424 427 560 770 845 847 859 868 980 1057 1101 1209 1253 1330 1442 1451 1463 1465 1540 1750 2002 2212

guests=7: 2212+1540+208 = 2002+1209+427+224+98 = 1750+1057+845+308 = 1465+1101+560+424+233+177 = 1463+1451+770+218+58 = 1442+1330+847+341 = 1253+980+868+859
guests=8: 2212+1253 = 2002+1463 = 1750+1057+560+98 = 1540+847+845+233 = 1465+1451+341+208 = 1442+980+424+224+218+177 = 1330+1209+868+58 = 1101+859+770+427+308
guests=9: 2212+868 = 2002+845+233 = 1750+1330 = 1540+1442+98 = 1465+847+427+341 = 1463+1101+308+208 = 1451+859+770 = 1253+1209+560+58 = 1057+980+424+224+218+177
guests=10: 2212+560 = 2002+770 = 1750+845+177 = 1540+424+308+224+218+58 = 1465+1209+98 = 1463+1101+208 = 1451+980+341 = 1442+1330 = 1253+859+427+233 = 1057+868+847
guests=11: 2212+308 = 2002+341+177 = 1750+770 = 1540+980 = 1465+847+208 = 1463+1057 = 1451+427+424+218 = 1442+845+233 = 1330+868+224+98 = 1253+1209+58 = 1101+859+560
guests=12: 2212+98 = 2002+308 = 1750+560 = 1540+770 = 1465+845 = 1463+847 = 1451+859 = 1442+868 = 1330+980 = 1253+1057 = 1209+1101 = 427+424+341+233+224+218+208+177+58

[kotenok gav]

dimkadimon в сообщении #1315488 писал(а):

Я использую обычный depth first search.

А причем он?

[dimkadimon]

Это для функции проверки решений. Нам дали размер всех кусочков и количество гостей. Теперь мы пробуем разбить наши кусочки. Используем DFS чтобы вставить один кусочек за другим. Как только вставили, уменьшаем искомую сумму и помечаем новый кусочек как "использованный"

-- 06.06.2018, 16:30 --

Советую посмотреть эту ссылку

https://stackoverflow.com/questions/470 ... ge-in-java

[kotenok gav]

А до какого числа надо проверять размеры кусков?

[dimkadimon]

До S/N, где S сумма всех кусков и N количество гостей.

[kotenok gav]

А как посчитать сумму всех кусков не зная их?

[Sender]

kotenok gav в сообщении #1317557 писал(а):

А как посчитать сумму всех кусков не зная их?

Если считать все куски целыми, то все их суммы также целые, значит $S$ кратно $\text{НОК}(1, \dots, N).$ До сих пор всегда существовали решения с минимально необходимым количеством кусков для $S=\text{НОК}(1, \dots, N).$

-- Ср июн 06, 2018 12:05:44 --

Более общий подход, не предполагающий обязательной целости кусков, изложен 12d3 в https://dxdy.ru/post1315876.html#p1315876.

[dimkadimon]

Улучшил 12 гостей до 30 кусков:

37 53 121 131 275 287 329 331 485 530 539 637 749 791 847 868 978 1001 1039 1099 1211 1309 1442 1463 1519 1673 1771 1981 2035 2189

guests=7: 2189+1771 = 2035+1309+329+287 = 1981+1001+978 = 1673+1211+1039+37 = 1519+1442+868+131 = 1463+791+637+539+530 = 1099+847+749+485+331+275+121+53
guests=8: 2189+1001+275 = 2035+1099+331 = 1981+847+637 = 1771+1442+131+121 = 1673+1463+329 = 1519+1039+530+287+53+37 = 1309+868+749+539 = 1211+978+791+485
guests=9: 2189+485+275+131 = 2035+637+287+121 = 1981+1099 = 1771+1309 = 1673+1039+331+37 = 1519+978+530+53 = 1463+868+749 = 1442+847+791 = 1211+1001+539+329
guests=10: 2189+530+53 = 2035+329+287+121 = 1981+791 = 1771+1001 = 1673+1099 = 1519+978+275 = 1463+1309 = 1442+868+331+131 = 1211+1039+485+37 = 847+749+637+539
guests=11: 2189+331 = 2035+485 = 1981+539 = 1771+749 = 1673+847 = 1519+1001 = 1463+530+275+131+121 = 1442+791+287 = 1309+1211 = 1099+1039+329+53 = 978+868+637+37
guests=12: 2189+121 = 2035+275 = 1981+329 = 1771+539 = 1673+637 = 1519+791 = 1463+847 = 1442+868 = 1309+1001 = 1211+1099 = 1039+749+485+37 = 978+530+331+287+131+53