Задача о попсовой группе - решение

[atly]

Сама задачка №4 тут.

"Если много выпить, то блондинки и брюнетки подчиняются статистике Ферми - Дирака. Если ещё и они много выпьют - то статистике Бозе - Эйнштейна."
"Физики, сейчас дошутитесь!" - М.: Наукообразие, 2008 - т.3Во-первых, будем считать, что продюсер нумирует случайным образом своих подчинённых от 1 до 15 и запускает их в номерном

Comments

я написал за 3 мин 20 сек

[sternenzaehler]

тоже самое что ниже запостил kouzdra - только на не СИ и в два раза меньше кода. писал по секундомеру, вспомнить старое:):):)
вообще - задачи надо придумывать такие чтобы написание программы на компьютере занимало более 15 минут - тогда есть хороший стимул думать.

над алгебраическим решением думать не стал тк очень много работы сейчас, и нет времени.
специально увеличивать затраты времен на решение задачи которая сводится к перебору 32 000 вариантов я просто не стал. я вообще наверное склонен упрощать.

твое решение посмотрел но обоснование еще не читал. может сам еще подумаю.

а нет, кода столько же

[sternenzaehler]

это я изза пустых строчек неправильно оценил.

Re: я написал за 3 мин 20 сек

[atly]

ну, фигня в том, что число брюнеток и блондинок можно довести до 500 и 1000 соответственно. Ответ от этого не изменится (аналитическое решение = (A-B)/(A+B)). Решение с разворачиванием рекурсии будет вычисляться за миллисекунды, а ваше - практически вечность :)

ну так ты увеличил бы.

[sternenzaehler]

я бы и думал сразу над совсем другой задачей.

а так у меня много работы и всяких задач для разминки нерешенных не начатых тоже много.

вот например:
дана одномерная пустыня (прямая линия). в начальной точке есть количество еды Х. 1 единица еды достаточна для прохождения отрезка в 1 единицу на прямой. в любой точке прямой можно оставить про запас любое количество еды, еда не портится. с собой можно нести не больше М еды.
на какое максимальное расстояние можно отойти начиная в точке 0 с Х еды. - еда и расстояние - не дискретные, делимые на сколь угодно малые части.

нужно алгебраическое решение - в свободное время думаю, пока не придумал.

Re: ну так ты увеличил бы.

[atly]

это очень простая задачка (думал 2 минуты, пока ужин накладывал) :)

тогда покажи путь в котором

[sternenzaehler]

нужно думать.

[atly]

Предположим, тебе надо сдвинуть себя и всю массу жратвы на dR, на какую величину dX при этом уменьшится масса жратвы, как dX зависит от X и dR.

ну так

[sternenzaehler]

"сдвинуть массу еды на R" это ведь и есть ключевой вопрос. сколько надо потратить еды чтобы передвинуть Х еды на расстояние Р.

в это задача и заключается.

получается если еды меньше чем рюкзак, то ее можно взять сразу

если еды 2*рюкзак, то переносим 1/3*Р на расстояние одну треть, возвращаемся и берем осташийся рюкзак. то есть для 2*рюкзак ответ будет 4/3*единицу расстояния.

а как дальше я еще не придумал

Re: ну так

[atly]

ну так ты считай, что dR - достаточно маленькое переещение ;) а не максимальное расстояние

не понял.

[sternenzaehler]

в смысле??

ну дР маленькое перемещение. чтобы перенести Х еды на дР надо будет сделать Х/(М-2дР)-1 ходок перемещений.
если словами то за 1 раз перемещаем весь рюкзак за вычетом дР на путь туда и дР на путь обратно.
минус один потому что крайний раз не надо будет возвращаться.

быстрее это сделать нельзя. верно?

далее

[sternenzaehler]

затраты на перемещение Х еды на расстояние дР составят (Х/(М-2дР)-1)*дР.

это как раз я уже сделал. а вот как дальше?

Re: далее

[atly]

не, не верно

а в чем ошибка??

[sternenzaehler]

??

[atly]

dX = (2[X/M]+1)dR, где [] - целая часть

мне непонятно следующее

[sternenzaehler]

1. пусть Х=М. по твоей формуле получается что дХ=3*дР, в то время как на самом деле Х=М сразу загружается в рюкзак и возвращаться не надо. то есть в данном случае в реале дх=др а по твоей формуле не так.

тоже самое для Х=2М, по твоей формуле дх=5др, реально -3др.

это у тебя ошибка или я не понимаю?

лан, допустим мы исправим формулу так: дх=(2*(Х/М-1)+1)др. тогда для Х=М будет 1 и для Х=2М будет три - правильные ответы.

еще мне непонятно следующее:

у тебя в формуле Х\М то есть количество перевозок равно общий объем делить на емкость рюкзака. но ведь это неверно ибо мы при перевозке да ДР реально перевозим не М а М-2ДР, т.к 2ДР нам надо собственно на перевозку и полезная емкость рюкзака соответственно реально меньше.
это где у тебя учитывается или где я неправ???

Re: мне непонятно следующее

[atly]

это не страшно, сдвинувшись на скольк угодно малую величину, [X/M] станет равна нулю и дальше dX = dR