The Society for Saving the World has called their N members to an emergency congress to finally
agree on a plan for saving the world. To reach a common decision in any meeting at the congress, the
meeting participants proceed as follows:
To speed up the overall decision-making process, the participants of the congress have decided to split
into groups and work in parallel. Each group selects the best proposal among themselves using the
procedure described above. Then the representatives of the groups meet and pick the final plan among
the proposals voted best in each group.
For example, if the 100 participants would split into two groups of 40 and 60, respectively, the process
could work as follows (again, P = V = 1):
But the groups might further divide themselves into subgroups and sometimes it could be useful to
split into more than two groups. As a special case, a subgroup of 1 member can decide in no time, as
there is no need to present one’s own proposal to oneself.
Write a program that, given presentation and voting times P and V , computes the minimal time
needed for the N participants of the congress to reach a common decision, assuming they organize
their meetings and groups optimally.
The first and only line of input contains the three integers N, P, and V: N is the number of participants
of the congress, P is the presentation time (in minutes), and V is the voting time (in minutes).
1 ≦ N ≦ 1015
1 ≦ P, V ≦ 1000
The first and only line of output should contain the integer M, the minimal number of minutes needed
for the congress to reach a decision.
9 1 1 6 1 2 6 2 1
8 8 12
In the first example, the participants can be divided into 3 groups of 3 members each. Then each group
needs 4 minutes and the 3 representatives need another 4 minutes for their final meeting.
Migrated from old NTUJ.
BOI2011 Competition day 2
No. | Testdata Range | Score |
---|