[USACO 2014 Jan B]Bessie Slows Down
题号:NC24566
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Bessie the cow is competing in a cross-country skiing event at the winter
Moolympic games. She starts out at a speed of 1 meter per second.
However, as she becomes more tired over time, she begins to slow down.
Each time Bessie slows down, her speed decreases: she moves at 1/2 meter
per second after slowing down once, then 1/3 meter per second after slowing
down twice, and so on.

You are told when and where Bessie slows down, in terms of a series of
events. An event like this:

T 17

means that Bessie slows down at a specific time -- here, 17 seconds into
the race. An event like this:

D 10

means that Bessie slows down at a specific distance from the start -- in
this case, 10 meters.

Given a list of N such events (1 <= N <= 10,000), please compute the amount
of time, in seconds, for Bessie to travel an entire kilometer. Round your
answer to the nearest integer second (0.5 rounds up to 1).

输入描述:

Line 1: The value of N.

Lines 2..1+N: Each line is of the form "T x" or "D x", indicating a
time event or a distance event. In both cases, x is an
integer that is guaranteed to place the event before Bessie
reaches one kilometer of total distance. It is possible for
multiple events to occur simultaneously, causing Bessie to
slow down quite a bit all at once. Events may not be listed
in order.

输出描述:

Line 1: The total time required for Bessie to travel 1 kilometer
示例1

输入

复制
2
T 30
D 10

输出

复制
2970

说明

Bessie travels the first 10 meters at 1 meter/second, taking 10 seconds.
She then slows down to 1/2 meter/second, taking 20 seconds to travel the
next 10 meters. She then reaches the 30 second mark, where she slows down
again to 1/3 meter/second. The remaining 980 meters therefore take her
980 * 3 = 2940 seconds. The total time is therefore 10 + 20 + 2940 = 2970.