#BZOJ2347. Meetings

Meetings

No submission language available for this problem.

题目描述

拯救地球学会召集了N位会员来参加一个紧急会议,目的是最终通过一个方案来拯救世界。为了在会上达成一致的决议,与会人员将按以下流程进行:
1.每位会员都有一个方案(proposal),需要花P分种来给其他会员进行展示
2.当每位会员都展示完毕,他们需要投票(vote)选出最好的方案,这需要V分钟
例如,如果每个方案花1分钟展示(P=1),投票也花1分钟(V=1),一个100人参加的会议将在101分钟后得出最终结果。
为了更快地得到最终结果,参加会议的会员们决定分组开会,同时进行。每个小组按照上面的流程选出组内最佳的方案。然后每个小组的代表再开会,并从每个小组的最佳方案中选出最终结果。
比如,如果100名会员分成2组,一组40人,另一组60人,会议将按下面的情况进行(仍然设P=V=1):
l        人多的小组花61分钟选出组内最佳方案;
l        人少的小组花41分钟选出组内最佳方案,然后得等人多的小组的会议结束;
l        2个小组的2位代表开会,花2分钟时间互相展示各自的方案,然后花1分钟投票。
这样,会议进行的总时间为61+2+1=64分钟。
但是小组可以再细分成更小的组(subgroup),而且有时候分成2组以上会更快。比如在特殊情况下,1个的小小组(subgroup)不需要给自己做展示,也不用做选择。
给定PV,编写程度,计算N名会员参加会议并得到最终结果所需要的最短时间,假设他们最优化地安排会议和分组。

输入格式

 
1行,也是唯一的一行,有3个整数N, PVN是参加会议的会员人数,P是展示用的时间(单位为分钟),V是投票用的时间(单位为分钟)。

输出格式

1行,也是唯一的一行,应给出整数M,即整个会议得到最终结果所需要的最短时间。
数据范围
1≤N≤1015
1≤P, V≤1 000
70分的测试点中,1≤N≤50 000
40分的测试点中,1≤N≤5 000

9 1 1
6 1 2
6 2 1
8
8
12

数据范围与约定

在第一个样例中,会员们可以分成3组,每组3人,每组需要4分钟,这3组的3名代表再花4分钟即可得到最终结果。