ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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,,,