ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1730. ManBearPig

How to solve it?
Posted by YSYMYTH 2 Jun 2012 17:58
I know it's something about vector of fractions,but don't know how.
Could anyone explain the solution please?
Re: How to solve it?
Posted by 2rf 3 Jun 2012 02:58
1) We can only make fractions of form a / 2^b where a is odd (this is obvious, you can prove it by induction for example)

2) If all fractions have this form then we can simply build full binary tree. Number of leaves will be equal to the largest denominator and creatures in leaves can be determined quite easily.

In fact, problem is easy because we aren't asked to find minimal answer.