Обсуждение @ 1366. Подарки @ Timus Online Judge

akidra_8881 python wrong answer help [3] // Задача 1366. Подарки 21 авг 2020 08:54

vtalgo16_plitvinov WA11 [1] // Задача 1366. Подарки 29 фев 2016 01:22

Sunnat Thanks KIT // Задача 1366. Подарки 29 апр 2013 16:45

Freezing Sun WA14 // Задача 1366. Подарки 17 сен 2009 19:04

freedevc Thanks // Задача 1366. Подарки 28 окт 2008 09:55

CHIDEMYAN SERGEY Please help!!! MLE#21.Here is code: [7] // Задача 1366. Подарки 25 фев 2008 20:22

Sawe What is the answer for N=1000? (-) [2] // Задача 1366. Подарки 29 дек 2006 18:15

{AESC USU} Dembel Re: What is the answer for N=1000? (-) [1] // Задача 1366. Подарки 29 дек 2006 21:21

My AC program outputs
1480300003716690803639166141189660542377872467716834615546918460898888171222360711813189873910548675459590726189130673952565926739378359567722411682225282955956835967209806662206094278319048852420295993918145867464929632177223403177771955752603660100590106551721447382848788617582081310047350358184775693687864320616320161884468076859109403218325729966499814817722523251910400861544265546575384584445357657178710339466137717023503056252650043203882433860978792626830828468703859597819544889563899703925789442886604592950312345074787367168818241367836225845351388059822881452853157092920449246805492179297901159845450144415217557357263061954571997705726917546636177873914180435642912954635442323456238142340910752454816552406177681946008016133704545795503609904692149425055853719332957948207301824597654871393025676689264387133050350749500959081818757218706290284427041888179306280825957697116463097109027133895778139249850841954896876020466195020089609619793369712000118458329727664968204252323090144241603833525494325871758
0459951322429538762079323749213310619485478167533526424544336840634977862657715415393616579517641428024670820968425502109482342196679493125860192623788850206306117990892038912243728009669418031875672954018774352295528769340334462719200819324315004792668311620678980873752032993217592668963103980133320527177306869411988668143940820863453661616212548496824643329908661897203872632014352453015915512281606720947935915897510467617568994297290953898191551861043805896681345455213581061764326832650888474000756305781255775687211982794817701249872000284658432008360288350567522393041571024094338314208769709123757048278135225616280959304899730763636907169037354447533472772222696440183810580410403369885904650807263622112128476725617926138469557580012677787191460879974033313516907808504030187073870072198602651832414459785453439394011054887477145673354881969001489115029988337456903614450407565028424715429112260226257773863450239446806663726060151559041267799765637213898847989262978734485546962599318890221534174397659133578613
4612426484416557074485085137922648888557127618980204107341206517456111787177656668620397156874752365541689736459115633909848251703534756902949331850082296669410306980175719986482188446333446450823956158029544268395051423740042819986368612454904255206373684842598857136228239326853906860111911390847498545181350875035398066868621959973870036473108206470890805125591766035651660263166256071859066523494404932873989243033885387310363168734739688132495065765084286985470381074859852651721482664917019227944750044815550686001

Edited by author 29.12.2006 21:22

sasha Re: What is the answer for N=1000? (-) // Задача 1366. Подарки 1 фев 2007 22:52

Lifanov for n=4 answer 6 ? [21] // Задача 1366. Подарки 23 апр 2005 13:39

I'm get tester Re: for n=4 answer 6 ? [20] // Задача 1366. Подарки 23 апр 2005 14:24

You are wrong, Lifanov. Result is 9.
DCBA
CDBA
BCDA
BDAC
BADC
DCAB
CDAB
CADB
DABC

Lifanov How calc this? [18] // Задача 1366. Подарки 23 апр 2005 14:57

F(n)=(n-1)! +C(n,2)*F(2)*F(n-2)+C(n,3)*F(3)*F(n-3) ...C(n,n/2)*F(n/2)*F(n-n/2)
it is solution , but how i solve this for n=1000 ??

xMagGTU Дмитрий Тишкин GPRS Re: How calc this? [17] // Задача 1366. Подарки 23 апр 2005 15:53

I think the right is
we need cals h(n) which is
h(n)=f(n,0);
f(0,b)=b!;
f(1,b)=b*b!;
f(a,b)=(a-1)*f(a-2,b+1)+b*f(a-1,b);

but I can't prog this for small n, I think h(n) correct

xMagGTU Дмитрий Тишкин GPRS Re: How calc this? [1] // Задача 1366. Подарки 23 апр 2005 16:07

I send to judge the stupid prog
which not used BIG NUMBERS(num where digits>20)
and get wrong in 11 test
I think in for 11 test f(a,b) not in longint(2*10^9)
2 hour &30 minute in hole.

Lifanov if use this formula and BIG NUMBERS we have TLE. // Задача 1366. Подарки 24 апр 2005 18:19

for n>100 it will be work very slow :(

Kit Re: How calc this? [14] // Задача 1366. Подарки 24 апр 2005 20:04

It works so slow...
You may use this:
f(0) = 1;
f(1) = 0;
f(n) = (n - 1)*(f(n - 1) + f(n - 2))
It will work much faster.
Try to prove this formula.

Lifanov Thanks. I got AC. [1] // Задача 1366. Подарки 25 апр 2005 08:39

But, why this formula is right ???

Kit Re: Thanks. I got AC. // Задача 1366. Подарки 25 апр 2005 13:25

We want to find out value of f(n). The child #1 can give his own boxe any of other (n - 1) childrens. Suppose, he give it to the child #2. The child #2 can give his boxe either to the child #1, or to one of the rest of children. In the first case we have f(n - 2), in the second - f(n - 1).

Victor Barinov (TNU) Here it is one more formula (+) [8] // Задача 1366. Подарки 25 апр 2005 16:26

f(1) = 0;
f(n) = n*f(n-1) + (-1)^n;

Kit Re: (+) [7] // Задача 1366. Подарки 25 апр 2005 17:34

What you mean placing (+) and (-)? It is much used, but I don't understand it.
The formula is very interesting.

Victor Barinov (TNU) Re: (+) // Задача 1366. Подарки 25 апр 2005 21:48

(-) mean, that all that I wanted to say is situated in theme
(+) mean, that "will be continue..." :)

Yes formula interesting. My friend "create" it, and we get AC on contest, but we can't to prove it "strongly".

------
Sorry for bad English :)

xMagGTU Дмитрий Тишкин GPRS end [5] // Задача 1366. Подарки 25 апр 2005 22:09

>>The formula is very interesting.
formula from Victor Barinov (TNU)
f(1) = 0;                     (V1)
f(n) = n*f(n-1) + (-1)^n;     (V2)
same as formula from Kit
f(0) = 1;                     (K0)
f(1) = 0;                     (K1)
f(n) = (n - 1)*(f(n - 1) + f(n - 2)) (K2)
cose:
   from v2:
     (-1)^n    = f( n )- n *f(n-1)
     (-1)^(n+1)= f(n+1)-(n+1)*f( n )
sum they:
      0 = f(n+1) +f(n)-(n+1)*f(n)-n*f(n-1)
   or 0 = f(n+1)- n*f(n)-n*f(n-1)
   or f(n+1)=n*(f(n)+f(n-1))
   or f(n)=(n-1)*(f(n-1)+f(n-2)) That is   (K2)

???Victor Barinov (TNU) can you explain how you thot for find V2???

В варианте :
h(n)=f(n,0);    (Tx)
f(0,b)=b!;      (T0)
f(1,b)=b*b!;    (T1)
f(a,b)=(a-1)*f(a-2,b+1)+b*f(a-1,b);T(2)

Можно расуждать так
пуст (a) детей ещё могут нарватся(вытащить из оставшихся кучи свой хлам) и (b) детей не нарвутся уже точно (их презент уже нашёл нового хозяина).
Расмотрим все возможные варианты ребёнка из группы а:
0) выташил свой, 1 случай -> Дальше лудше и не представлять:)
1) выташил презент кого то другого из a, (a-1 случай )-> тем самым сделав того б :) то есть (a-1)*f(a-2,b+1),
2) вытащил презент кого то из b (b случаев) ->
a уменшилось на 1,число b осталось преждним: b*f(a-1,b)

и граничные случаи:
0)когда все подарки чужие (то есть их бывшие владельцы уже взяли чьёто добро и ушли с воспитателем на прогулку):
f(0,b)=b!
1) когда остался 1 хозяин , остальное чужое (хозяин может выбрать один из чужих(b вариантов), и случай сведется к предыдущему
f(1,b)=b*b!

>>if use this formula and BIG NUMBERS we have TLE. Послано >>Lifanov 24 апреля 2005 18:19
>>for n>100 it will be work very slow :(
при использовании таблицы предвычислений!!!(то есть считать одно и тоже конкретное f(a,b) только раз )и арифметики BIGNUM tle не будет, не должно быть, э ну ...
А вы Lifanov использовали таблицу или всё в рекурсии?

>>>F(n)=(n-1)! +C(n,2)*F(2)*F(n-2)+C(n,3)*F(3)*F(n-3)
...C(n,n/2)*F(n/2)*F(n-n/2)                         (L1)
it is solution , but how i solve this for n=1000 ??
???Lifanov can you explain how you thot for find L1???

Кто силён в рекурентностях, как свести Tx-T2 к K0-K2?

PS. Sorry, My Eng bad , so some Thot i write in rus, I understend that this site is for all piple , so if someWhy
translate(If need) , that shud be great

Victor Barinov (TNU) f(n) = n*f(n-1) + (-1)^n // Задача 1366. Подарки 26 апр 2005 16:03

Мой друг ее угадал, как я уже, кажется, говорил.

Sorry.

We can to continue discussion by e-mail. Mine is victorbarinov@ua.fm

Lifanov ???Lifanov can you explain how you thot for find L1??? [3] // Задача 1366. Подарки 27 апр 2005 20:37

L1 - Эта формула не верна. Она учитывает некоторые варинаты повторно.

>>if use this formula and BIG NUMBERS we have TLE. Послано >>Lifanov 24 апреля 2005 18:19
>>for n>100 it will be work very slow :(
при использовании таблицы предвычислений!!!(то есть считать одно и тоже конкретное f(a,b) только раз )и арифметики BIGNUM tle не будет, не должно быть, э ну ...
А вы Lifanov использовали таблицу или всё в рекурсии?

Думаю тут предвычисления не помогут.Причин две очень большой размер операндов (порядка 2600 десятичных знаков -> долго обрабытвать так как много операций) и во вторых нужно слишком много памяти даже для хранения одних только факториалов от 1 до 1000. А если попытаться хранить f(a,b) где 1<=a,b<=1000 то нужно 1 млн BIGNUM :)
Sorry, Thot i write in rus

Edited by author 27.04.2005 20:38

Edited by author 27.04.2005 20:38

Edited by author 27.04.2005 20:40

xMagGTU Дмитрий Тишкин GPRS Итог обсуждения кому подарки [2] // Задача 1366. Подарки 27 апр 2005 23:56

Нарыто:
online база числовых последовательностей основаная на
известном справочнике Слоана:
http://www.research.att.com/~njas/sequences/index.html

Оказывается для последовательности f= 0,1,2,9,44,265 из задачи 1366 есть имя(одно из имён) Субфакториал.

Варианты решения(1366):
1)Классическое образование(классные преподы -классные студенты) -> знание что за весчь Субфакториал
2)Отличный ум и хорошая интуиция из ?,0,1,2,9,44 ->
продолжить f(n)=n*f(n-1)+(-1)^n
либо f(n)=(n-1)(f(n-1)+f(n-2)) (т.е. повторить Эйлера :) )
3)чит во время интернет-контеста последовательности через интернет
http://www.research.att.com/~njas/sequences/index.html

PS f(a,b) ещё проще можно делать
f(0,b)=b!
f(a,b)=f(a-1,b)-f(a-1,b-1)
Очень рекамендую поигратся
http://www.research.att.com/~njas/sequences/index.html

Burunduk1 Speak english! [1] // Задача 1366. Подарки 28 апр 2005 10:28

One of the rights of this forum is using
only English language.
Please, do it.

Ich Re: Speak english! // Задача 1366. Подарки 2 май 2005 02:30

The answer is exactly equal to round(n!/e)

Tbilisi SU: Andrew Lutsenko Re: How calc this? [2] // Задача 1366. Подарки 10 окт 2006 23:31

>You may use this:
>f(0) = 1;
>f(1) = 0;
>f(n) = (n - 1)*(f(n - 1) + f(n - 2))
>It will work much faster.
>Try to prove this formula.

This formula is great, just like mine :D.
But there is one small mistake:
f(0)=0
and
f(1)=1

Good luck ...

Tbilisi SU: Eldar Bogdanov Re: How calc this? [1] // Задача 1366. Подарки 17 окт 2006 01:25

Andrew, you're wrong - F(0)=1 and F(1)=0 :)
For n=1, there is no way that the child gives his present to anybody else, so the answer has to be 0.

P.S. I seem to have the best time for this problem... :D

SuperLight no message // Задача 1366. Подарки 17 окт 2006 20:28

Alexandrov Sergey Re: for n=4 answer 6 ? // Задача 1366. Подарки 6 ноя 2005 18:03

I'm get tester писал(a) 23 апреля 2005 14:24

You are wrong, Lifanov. Result is 9.
DCBA
CDBA
BCDA
BDAC
BADC
DCAB
CDAB
CADB
DABC

What the difference between 1st and 5th variant???
A >> D >> C >> B >> A

Edited by author 06.11.2005 18:05

Обсуждение задачи 1366. Подарки