시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 1024 MB106534328633.608%

문제

cologne는 Trimps라는 게임을 하고 있다. 이 게임에는 $N$마리의 몬스터가 차례대로 있다. $i$번째 몬스터의 현재 체력은 $A_i$이다. 몬스터에게 $x$만큼의 대미지를 주면 몬스터의 체력이 $x$만큼 줄어들고, 이로 인해 체력이 $0$ 이하가 되면 몬스터가 죽게 된다.

cologne의 목표는 전투를 통해 모든 몬스터를 죽이는 것이다. 전투는 여러 개의 턴으로 이루어져 있으며 각 턴은 다음과 구성된다.

  1. 체력이 $0$ 초과인 가장 첫 몬스터를 찾아서 $D$만큼 대미지를 준다.
  2. 대미지를 준 몬스터의 체력이 $0$ 미만인 $-h$인 경우 오버킬이 일어난다. 오버킬은 다음과 같은 방법으로 처리된다.
    • 대미지를 준 몬스터의 다음 몬스터가 존재하지 않을 경우, 턴을 종료한다.
    • 대미지를 준 몬스터의 다음 몬스터가 존재할 경우, 다음 몬스터에게 $h$의 $p$퍼센트를 소숫점 첫째자리에서 버림한 만큼의 대미지를 준다.

모든 몬스터를 죽이기 위해서는 몇 턴이 필요할까?

입력

첫 줄에 몬스터의 수 $N$, 기본 대미지 $D$와 오버킬 비율 $p$가 공백으로 구분되어 주어진다. $(1 \le N, D, p \le 100)$

다음 $N$개의 줄에는 각 몬스터의 체력 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 100)$

주어지는 모든 수는 정수이다.

출력

모든 몬스터를 죽이기 위해 필요한 턴 수를 출력하여라.

예제 입력 1

7 20 15
30 21 1 2 30 22 3

예제 출력 1

9

전투는 다음과 같이 진행된다.

  1. 첫 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $10$이 된다.
  2. 첫 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $-10$이 된다.
    • $10$의 $15\%$인 $1.5$를 소숫점 첫째자리에서 버림한 $1$만큼 두 번째 몬스터에게 대미지를 줘, 체력이 $20$이 된다.
  3. 두 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $0$이 된다.
  4. 세 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $-19$가 된다.
    • $19$의 $15\%$인 $2.85$를 소숫점 첫째자리에서 버림한 $2$만큼 네 번째 몬스터에게 대미지를 줘, 체력이 $0$이 된다.
  5. 다섯 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $10$이 된다.
  6. 다섯 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $-10$이 된다.
    • $10$의 $15\%$인 $1.5$를 소숫점 첫째자리에서 버림한 $1$만큼 여섯 번째 몬스터에게 대미지를 줘, 체력이 $21$이 된다.
  7. 여섯 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $1$이 된다.
  8. 여섯 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $-19$가 된다.
    • $19$의 $15\%$인 $2.85$를 소숫점 첫째자리에서 버림한 $2$만큼 일곱 번째 몬스터에게 대미지를 줘, 체력이 $1$이 된다.
  9. 일곱 번째 몬스터에게 $20$의 대미지를 줘, 체력이 $-19$가 된다.

노트

오버킬은 한 번만 이루어진다. 즉, 한 턴에 세 마리 이상의 몬스터에게 대미지를 줄 수는 없다.

출처

University > KAIST > KAIST HAJE 프로그래밍 대회 A번