시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 61 9 6 20.000%

문제

스타크래프트를 좋아하는 현환이는 큰 고민에 빠졌다. 상대의 배럭을 공격할 것인지, 아니면 배력에서 마린을 뽑을 것인지.

가장 처음에 현환이는 마린을 N명 가지고 있다. 보통의 스타그래프트 게임과 다르게 이번 게임은 한 턴씩 진행된다. 매 라운드마다 각각의 마린이 할 수 있는 행동은 상대편의 마린을 죽이거나, 배럭을 공격해 HP를 1 감소시키는 것이다.

상대방은 가장 처음에 마린이 하나도 없다. 상대방 배럭의 HP는 B이고, 한 턴에 U명씩 마린을 뽑는다.

 

한 라운드는 다음과 같은 순서로 진행된다.

  1. 현환이는 각각의 마린이 무엇을 해야할지 결정해야 한다. 즉, 상대편의 마린을 공격해서 죽이거나, 배럭을 공격해서 HP를 1 감소시킬 것인지 정해야 한다. 각 마린은 서로 다른 행동을 취할 수 있다. 만약, 상대방 배럭의 HP가 0이 되면, 배럭은 파괴된다.
  2. 현환이의 턴이 끝나면, 상대방의 턴이다. 상대방이 가지고 있는 마린의 수를 K라고 했을 때, 상대방은 현환이의 마린 K명을 죽인다.
  3. 상대방의 배럭이 아직 파괴되지 않았다면, 상대방은 마린 U명을 새로 생산한다.

현환이는 상대방의 배럭을 파괴시키고, 상대방의 마린을 모두 죽이려고 한다. 이것이 가능하다면, 현환이가 최소 몇 턴 만에 가능한지를 구하고, 불가능하면 -1을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N B U가 주어진다. 모든 수는 5000보다 작거나 같은 자연수이다.

출력

첫재 줄에 상대방의 배럭을 파괴시키고, 상대방의 마린을 모두 죽이려고 할 때, 필요한 최소 턴의 수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

10 11 15

예제 출력

4

힌트

라운드 1

  • 현환이의 모든 마린은 상대방 배럭을 공격한다. 상대방 배럭의 HP는 1이 된다.
  • 상대방은 현재 마린이 없기 때문에, 공격을 할 수가 없다.
  • 상대방이 새로운 마린 15명을 뽑는다.

라운드 2

  • 현환이의 마린 1명이 배럭을 공격해 파괴시키고, 나머지 마린 9명은 상대방의 마린을 공격한다.
  • 상대방은 이제 마린이 6명 있다. 현환이의 마린 6명을 죽인다.
  • 배럭이 파괴되었기 때문에 상대방은 마린을 뽑을 수 없다.

라운드 3

  • 현환이는 이제 마린 4명이 있다. 상대방 마린을 공격한다.
  • 상대방의 남은 마린은 2명이다. 현환이를 공격하고, 현환이의 남은 마린 수는 2명이 된다.
  • 배럭이 파괴되었기 때문에 상대방은 마린을 뽑을 수 없다.

라운드 4

  • 현환이가 상대방을 공격하면, 상대방의 마린이 모두 없어지기 때문에, 현환이가 게임을 승리하게 된다.

출처