LINUX.ORG.RU

Cладкая олимпиадная задача

 


0

1

Дан торт который порезан на m*n равных кусков и вы хотите иметь точно один фрукт на каждом куске. Давайте обозначим f(m,n) количество разных вариантов верхушек на торте с m разными фруктами(m ≥ 2), используя каждый фрукт на точно n кусках ( n ≥ 1). Отражения считаются различными, повороты - нет. Например, f(2,1) = 1, f(2,2) = f(3,1) = 2 и f(3,2) = 16. Напишите алгоритм который найдет сумму всех f(m,n) такую что f(n,n) ≤ 1015. и вот есть еще гифка пример f(3,1) Подскажите какими формулами из комбинаторики ищется это f http://s57.radikal.ru/i156/1507/b5/a6718e28b5ed.jpg http://s019.radikal.ru/i609/1507/0b/8781430efaa7.gif



Последнее исправление: Studentik2000 (всего исправлений: 2)

Удивительно наркоманское условие. Я нихрена не понял. Какие верхушки? Где расположены фрукты? Отражения чего? Какие повороты если торт согласно картинке круглый?
Похоже, что соль этой задачи не в нахождении f(m,n), а в расшифровке условия.

Stahl ★★☆
()

А это надо что ли за тебя решить, да?

Sad_Boy
()
Ответ на: комментарий от Studentik2000

Как можно разрезать торт (или это пирог?) на m x n equal pieces, если он круглый? Или он всё-таки прямоугольный?

Harald ★★★★★
()
Ответ на: комментарий от Harald

Ну почему же? представь, что м=1, а н=3, тогда торт надо разделить на 3 равные части. Ничего сложного?
Просто эта задача вобрала в себя все наихудшие черты олимпиадных задач — бессмысленность и беспощадность.

Stahl ★★☆
()
Ответ на: комментарий от nezamudich

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

Studentik2000
() автор топика

f(m,n)= Z(m,m*n)

где Z(m,0)==1 Z(m,km)= (km)!/m!/((k-1)m)!*Z(m,(k-1)m)

и да f(n,n) вроде как (n*n)!/((n!)**n)

f(1,1)==1

f(2,2)==4!/2!/2!=6

f(3,3)==9!/3!/3!/3!=9*8*7*6*5*4/3!/3!=3*4*7*5*4=240*7>1015

И это 1015 али всё таки 10**15

и точно f(n,n)<-100500 али всёж f(m,n)?

qulinxao ★★☆
()
Ответ на: комментарий от proud_anon

моё «вроде как» для разомкнутого батона оказалось, а не для замкнутого пончика.

зы.ох уж этот Фрейд.

qulinxao ★★☆
()
Ответ на: комментарий от proud_anon

4*3*2*1/2/2=6

aabb

abab

abba

baab

baba

bbaa

(aabb abba bbaa baab) И (baba abab)

так как abcd == bcda == cdab == dabc на колечке всегда , на песте иногда.

то /4 aabb и abab

Хм иили думать google:necklace

qulinxao ★★☆
()
Ответ на: комментарий от anonymous

Вот, анон молодец. Я всё смотрю и думаю, какой-то знакомый характер у задачи.

nezamudich ★★
()

/Algebra : An Elementary Text-Book (2 volume set)

http://www.amazon.com/review/R1VQCRISN9IV3I/ref=cm_cr_dp_title?ie=UTF8&AS...

... Sometime in the middle of the century(here 19xx) algebra became a required subject for all students, and very few of them could handle a rigorous exposition of algebra, so instead there came a surplus of «cookie cutter» algebra books in the following decades to accommodate those students. ...

qulinxao ★★☆
()
Ответ на: комментарий от nezamudich

Просто ОП её буквально цинично уничтожил своим переводом.

Судя по нику, ему в этом году только 15 исполняется.

Pythagoras ★★
()

как можно так ужасно переводить?

и это скорее матем, а не программирование.

f1u77y ★★★★
()
Ответ на: комментарий от qulinxao

g(m,n) = (mn)! / (n!)^m вот получилась формула для общего колличества вариантов, это включая повороты, как их отсеять я не догоняю, по этой формуле как раз и получается число 6 в случае с ф(2,2) ты и объяснил постами выше почему 6

Studentik2000
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.