시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB38616012645.818%

문제

DPS는 Damage Per Second의 약자이다. DPS는 측정 시간 동안의 총 데미지 양을 전체 측정 시간으로 나눈 값이다. 유저는 $N$ 종류의 스킬을 사용하여 상대에게 데미지를 입힐 수 있는데, 그중 $i$번 스킬은 $R_i$의 시전 대기 시간 이후 $A_i$의 시전 시간동안 일정한 양으로 상대에게 총 $D_i$만큼의 데미지를 입힌다. 시전 대기 시간은 스킬을 시전하기까지 필요한 준비 시간이며, 서로 다른 스킬은 동시에 시전될 수 있다.

유저는 $0$초 시점부터 스킬 시전 대기 시간이 지난 직후에 스킬을 시전하는 것을 반복적으로 수행한다. 이런 방식으로 사냥을 하던 유저는 본인의 실력을 자랑하고자, 측정 시작 시간 $S$부터 측정 종료 시간 $E$까지의 DPS를 계산하고자 한다. 유저를 위해 $S$부터 $E$까지의 DPS를 구해주자.

입력

첫째 줄에 정수 $N, S, E$가 공백으로 구분되어 주어진다. $(1\le N\le 100\,000;$ $0\le S < E\le 100\,000)$

다음 $N$개의 줄에 각 스킬의 시전 대기시간 $R_i$, 시전시간 $A_i$, 총 데미지량 $D_i$가 공백으로 구분되어 정수로 주어진다. $(1\le R_i\le 1\,000;$ $1\le A_i\le 1\,000;$ $0\le D_i\le 10^9)$

출력

첫째 줄에 측정 시간 동안의 DPS를 출력하라. 절대/상대 오차는 $10^{-6}$까지 허용한다.

예제 입력 1

3 0 10
1 2 5
1 3 6
2 4 8

예제 출력 1

4.1

예제 $1$의 경우 다음과 같이 계산된다.

각 스킬에 대한 측정 시간 동안의 총 데미지 양 :

  • $1$번 스킬: 시전 대기 및 스킬 시전 $3$회 반복 후 시전 대기 시간이 지나고 종료하므로 $15$($= 5 \times 3$) 데미지로 공격
  • $2$번 스킬: 시전 대기 및 스킬 시전 $2$회 반복 후 시전 대기 시간이 지나고 시전시간 $A_2 \times \frac{1}{3}$(1초) 소요되므로 $14$($= 6\times 2 + 6 \times \frac{1}{3}$) 데미지로 공격
  • $3$번 스킬: 시전 대기 및 스킬 시전 $1$회 반복 후 시전 대기 시간이 지나고 시전시간 $A_3 \times \frac{1}{2}$(2초) 소요되므로 $12$($= 8\times 1 + 8 \times \frac{1}{2}$) 데미지로 공격

DPS = (측정 시간 동안의 총 데미지 양) / (탐지 시간) = $(15+14+12) / (10-0)$ = $4.1$

예제 입력 2

3 5 10
1 2 5
1 3 6
2 4 8

예제 출력 2

4.3

출처

University > DGIST > 2024 DGIST 알고리즘 경진대회 D번