ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1387. Vasya's Dad

Help, please. p1387 - Vasya's Father.
Posted by Victor Barinov (TNU) 2 Nov 2005 01:14
What is answer for n = 8?

Mine is 117, but I have WA on test #8. I can't find a mistake in my code :(

Thanks!
Re: Help, please. p1387 - Vasya's Father.
Posted by md 4 Nov 2005 13:25
I have WA#8 too. Where was your mistake?

Some values I calculated:
"1",
"1",
"2",
"4",
"9",
"20",
"49",
"117",
"297",
"746",
"1947",
"5021",
"13378",
"35237",
"95123",
"254825",
"694987",
"1882707",
"5184391",
"14177587",
"39289183",
"108337723",
"301997384",
"837774846",
"2347293253",
"6546903307",
"18417850843",
"51617715836",
"145722478875",
...
Your sequence not right (+)
Posted by Victor Barinov (TNU) 4 Nov 2005 18:10
right is

1, 1, 2, 4, 9, 20, 48, 115,..

My mistake was for n = 7:
Your think that there
f(7) = f(6) + f(5)*f(1) + f(4)*f(2) + f(3)*f(3) + f(4)*f(1)*f(1) + ...

But correct is:

f(7) = f(6) + f(5)*f(1) + f(4)*f(2) + f(3)*(f(3)+1)/2! + f(4)*f(1)*(f(1)+1)/2! + ...

so we will take not f(3)*f(3) = 2*2 = 4, but f(3)*(f(3)+1)/2! = 2*(2+1)/2! = 3, and f(7) = 48.

Edited by author 04.11.2005 18:12
Thank you (+)
Thank you very much for your hint! It turned out to be very-very useful for me. Without it I would have spent many hours debugging...
Re: Your sequence not right (+)
Posted by labike 11 Aug 2013 16:38
can  you let  me  see you  code ?  i just  can not  ac it   ,,,thanks,,,