시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 27 1 1 100.000%

문제

2012년 지구는 멸망한다. 이러한 멸망하는 지구를 지키기 위해서, 초강대국 사파리 월드에는 긴급 의회를 소집했다. 이 의회에는 N명의 의원이 있다. 

의회에는 회의를 통해서 하나의 의견을 결론으로 낸다. 회의에서, 결론에 도달하기 위해서는, 회의 참석자들이 다음과 같은 과정을 지켜야 한다.

  1. 모든 사람은 의견이 있고, P분동안 다른 사람들에게 설명할 수 있다.
  2. 모든 참석자들이 발표를 한 후에, 가장 좋은 의견에 대해 투표를 한다. 이 투표는 V분 린다.

예를 들어, P=1이고, V=1이라고 하면, 100명의 참가자가 참석한 회의라면 최종 결론이 나오기 까지 101분이 걸린다.

지금 지구가 멸망하고 있는데, 사파리 월드 의원들은 의외로 책임감이 넘쳐서, 이러한 의사 결정 절차를 빠르게 하기로 했다. 그러기 위해서 몇 개의 그룹으로 의원들을 나누고, 동시에 회의를 진행하기로 했다. 각 그룹은 각 그룹의 참석자들 사이에서 가장 좋은 의견을 뽑고, 각 그룹에서 가장 좋은 의견을 내놓은 사람들끼리 다시 회의를 한다.

예를 들어, P=1, V=1이고, 100명의 의원을 40, 60명의 그룹으로 나누면 다음과 같은 과정을 거친다.

  1. 60명의 그룹의 회의는 61분이 걸린다.
  2. 40명의 그룹의 회의는 41분이 걸리고, 60명의 그룹의 회의가 끝날 때 까지 기다린다.
  3. 두 그룹의 가장 좋은 의견을 낸 사람들이 최종 회의에 참가하고, 발표하는데 2분, 투표하는데 1분이 걸린다.

따라서 총 61+2+1 = 64분이 걸린다.

그룹을 만들었을 때, 거기서 또다른 소그룹을 만드는 것은 때때로 의사 결정 속도를 엄청나게 빠르게 하기도 한다. 특별한 예외 경우로 회의의 참석자가 1명인 결정하는데 시간이 걸리지 않고, 다른 사람에게 자신의 의견을 발표할 필요도 없다.

N과 P와 V가 주어졌을 때, 회의와 그룹을 최적의 상태로 나누었을 때, 마지막 의견 하나가 나오는데 걸리는 시간을 출력하시오.

입력

첫째 줄에 N과 P와 V가 주어진다. 1<=N<=10^15, 1<=P,V<=1,000

출력

첫째 줄에 의회가 최종 의견을 내는 시간 M을 출력한다.

예제 입력

9 1 1

예제 출력

8

힌트

3명씩 3개의 그룹으로 나누면, 각 그룹은 회의가 4분씩 걸리고, 다시 마지막에 3명이 회의에 참석해서 회의를 하면 4분이 걸리므로, 8분이 걸린다.

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 5번

  • 문제의 오타를 찾은 사람: 79brue
  • 문제를 번역한 사람: baekjoon