시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB376402620.968%

문제

스타크래프트를 좋아하는 준겸이는 턴 방식의 스타크래프트 게임을 하려고 한다. 이 게임에서 가장 중요한 것은 상대의 배럭을 공격할 것인지, 마린을 생산할 것인지 결정하는 것이다.

현재 준겸이는 마린 N마리를 가지고 있다. 각 턴마다 각각의 마린은 상대의 배럭을 공격해 데미지를 1 줄것인지, 상대의 마린을 공격해 게임에서 제외할 것인지 결정해야 한다. 게임의 시작시점에 상대방은 마린을 하나도 가지고 있지 않다. 하지만, 배럭의 체력은 B이고, 매 턴마다 U마리의 마린을 생산한다.

게임의 진행을 정리해보면 다음과 같다.

  1. 준겸이의 마린은 상대방의 마린을 공격해 게임에서 제외할 것인지, 배럭을 공격해 체력을 1 감소시킬 것인지 결정해야 한다. 이 결정은 각각의 마린마다 다르게 선택해도 된다. 배럭의 체력이 0이 되면 파괴된다.
  2. 상대의 모든 마린이 준겸이의 마린을 공격한다. 상대의 마린이 K마리인 경우, 준겸이의 마린 중 K마리가 게임에서 제외된다.
  3. 상대의 배럭이 아직 파괴되지 않았다면, 마린을 U마리 생산한다.

준겸이가 현재 가지고 있는 마린의 수 N, 배럭의 체력 B, 상대가 매 턴마다 생산하는 마린의 수 U가 주어진다. 상대의 배럭을 파괴하고, 모든 마린은 게임에서 제외시키기 위해 필요한 최소 턴의 수를 구해보자.

입력

첫째 줄에 세 정수 N, B, U가 주어진다.

출력

첫째 줄에 상대의 배럭을 파괴하고, 모든 마린은 게임에서 제외시키기 위해 필요한 최소 턴의 수를 출력한다. 만약, 불가능한 경우 -1을 출력한다.

제한

  • 1 ≤ N, B, U ≤ 5,000

예제 입력 1

10 11 15

예제 출력 1

4

턴 1

  • 준겸이의 마린이 배럭을 공격한다. 상대 배럭의 체력은 1이 된다.
  • 상대는 마린을 가지고 있지 않기 때문에, 준겸이의 마린을 공격할 수 없다.
  • 상대가 가지고 있는 마린이 0마리에서 15마리가 된다.

턴 2

  • 준겸이의 마린 1마리가 배럭을 공격해 배럭을 파괴한다. 나머지 9마리 마린은 상대의 마린을 공격한다.
  • 상대는 마린을 6마리 가지고 있다. 준겸이의 마린 6마리를 게임에서 제외한다.
  • 배럭은 파괴되었기 때문에, 상대는 마린을 생산할 수 없다.

턴 3

  • 준겸이는 마린 4마리를 가지고 있다. 상대의 마린을 공격하고, 상대가 가지고 있는 마린의 수는 2마리가 된다.
  • 상대의 마린이 준겸이의 마린을 공격해 준겸이의 마린 2마리를 게임에서 제외한다.
  • 배럭은 파괴되었기 때문에, 상대는 마린을 생산할 수 없다.

턴 4

  • 상대의 마린을 공격해 남아있던 마린 2마리를 게임에서 제외한다.

예제 입력 2

1 2 1

예제 출력 2

-1

예제 입력 3

1 1 1

예제 출력 3

1

예제 입력 4

25 200 10

예제 출력 4

13

출처