| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P154SUMA - ROUND 4A - Chạy đua |
Ant man (người kiến) có khả năng biến cơ thể mình nhỏ lại cỡ một con kiến, kẻ thù của anh là YellowJacket cũng có năng lực như vậy. Trong một lần so tài với nhau, cả 2 thi chạy đua với quãng đường 1km trong kích thước một con kiến, ai đi hết quãng đường đó với thời gian ngắn nhất sẽ thắng.
Biết rằng trong khi chạy, Ant man sẽ mỏi và chạy chậm dần, ban đầu, anh có tốc độ là 1 m/phút, sau lần giảm tốc độ đầu tiên, anh còn 0.5 m/phút, lần thứ 2 là 1/3 m/phút, …
Cho các thời điểm và vị trí Ant man sẽ bị giảm tốc độ, hãy tính xem anh đến đích sau bao nhiêu phút.
Input
Dòng đầu tiên chứa số N là số lần giảm tốc độ của Ant man (0 < N <= 10^4).
N dòng sau, mỗi dòng chứa 1 trong hai dạng sau: “T k” hoặc “D k” với:
- “T k” là phút thứ k kể từ đầu Ant man sẽ bị giảm tốc độ.
- “D k” là vị trí bằng k kể từ 0 mà Ant man bị giảm tốc độ.
Tại một thời điểm, anh có thể bị giảm tốc độ nhiều lần nếu như thời điểm đó anh ở vị trí thứ x, mà tại vị trí này có sự kiện giảm tốc.
Các thời điểm, vị trí có thể không được liệt kê theo thứ tự.
Output
In ra thời gian mà Ant man sẽ đi hết quãng đường 1km, làm tròn đến số tự nhiên gần nhất.
Example
Input:3
T 1
D 2
T 6
Output: 3994
Giải thích : Ant man đi 1m đầu với v = 1 m/p và mất 1p. Sau đó v = 1/2 m/p, và mất 2 p để đi đến
vị trí bằng 2, sau đó v = 1/3 m/p. Sau khi đi tiếp 3p nữa (1 mét), vận tốc còn lại là 1/4 m/p, đi nốt
quãng đường 997m còn lại mất 998 * 4 p, tổng thời gian là 997 * 4 + 1 + 2 + 3 = 3994 p.
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-24 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
