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

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 ??

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

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.

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

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.

But, why this formula is right ???

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).

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

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

(-) 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 :)

>>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

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

Sorry.

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

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

Нарыто:
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

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

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

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

Edited by author 06.11.2005 18:05

>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 ...