Q$1$

Throughout this problem, you are a broker interfacing with the Berkeley Exchange. Your program will read events from stdin and emit output to stdout.

Part $1$

In part $1,$ you are tasked with tracking market activity on the Exchange. Your program will read printed trades as they come in and $,$ when requested, print market activity data for a particular security. More details below.

Input

the input is composed of a stream of data coming from the Berkeley Exchange, with two data types:

print $($a record of a trade on the exchange$)$

volume$-$check $($a computation request for your program$)$

Each trade print is on a separate line. Each line contains the following space$-$delimited fields:

$1.$ the string "print"

$2.$ timestamp $($int$)$: the time at which the volume$-$check command was issued, denoted as seconds since market open

$3.$ security $($string$)$: the name of the security for which to calculate

example input

print $12$ SILVER $10012$

print $29$ PEARL $2599$

volume$-$check $49$ SILVER

print $61$ PEARL $25100$

input is guaranteed to be valid, note that

input is guaranteed to be non$-$decreasing $,$ i$.$e$.$ each timestamp will be greater than or equal to the previous one.

string values are unquoted

all numerical values fit in standard $32-$bit primitive types

TASK

Your first goal is to calculate the running volume of trades on the market $,$ with per$-$minute granularity.

Each time that a "volume$-$check $"$ is received, print the volume and previous trade price of this security traded within the trailing $60$ seconds $.$

you may use the following definitions:

if a volume$-$check arrives at time T$,$ include all trades both printed before the volume$-$check and with timestamp greater than T$-60$

volume is the sum of all relevant trade quantities

previous trade price is the price of the most recent print for this security

if no trades have been executed in the past minute for a particular security $,$ the volume is $0$ and the price is $"$NA$"$

implementations should be efficient for many volume checks,i$.$e$.$ still efficient if O$($volume checks $)=$O$($trade prints$)$

Q$2$ TRADING FOR A CLIENT

In this next part, you are also tasked with trading orders on behalf of one client. The rules for volume checks and general guidelines remain as described in the previous problem statement. You are encouraged to use your solution to the previous part as a starting point for this task.

Orders

Orders have the following space$-$delimited fields:

the string order

timestamp $($int$)$: the time at which the order is issued.

security $($string $)$: the name of the desired security to trade

client $($string$)$: the client's name

goal$\_$shares $($positive integer$)$:the number of shares the client would like to trade

participation$\_$rate $($decimal$)$: A $2-$digit decimal in $(0\mathrm{.}00,1\mathrm{.}00)$ naming what percentage of this security$\text{'}$s trailing$-$minute market trading volume this client is willing to take for this order. More specifics order "Note on participation rate"

Examples:

order $122$ GOLD BOB $1000\mathrm{.}05$

Details

Your goal, whenever an order is received, is to fulfill as many shares as possible in the order, up to goal$\_$shares and constrained by participation rate. The trades you execute will be emitted as prints just like those observed in part $1.$

Operate under the following definitions:

Orders expire $60$ seconds after they are received. An order with time stamp T may only be traded in any second $[$T$,$ T$+59]$ inclusive

Your client will only ever have at most one active order for a security at any time T$.$ Equivalently, if your client sends an order at a time T for security X$,$ they will not send another order for security X until time T$+60$ or later.

On the BERKELEY EXCHANGE $,$ a trade may be considered filled as soon as it is printed. The trade's volume may then be immediately removed from the client's goal shares and included in the overall market volume. The timestamp for fulfilling a trade should be the same as the most recent timestamp received from the input stream.

Always trade the maximum number shares permitted by the participation rate constraint. Never break up a feasible trade into multiple smaller trades. Shares may only be traded in integer quantities $,$ and participation rate is an inclusive $($less$-$than$-$or$-$equal$-$to$)$ constraint.

the price of each new trade you execute is the previous trade price for that security

always trade as soon as possible. That is$,$ fill all feasible trades for any active orders before moving to the next input item.

for each order, output a sequence of trade prints in order to fulfill the order. as in part $1,$ a trade print is formatted as follows:

print $\{$timestamp$\}\{$security$\}\{$num$\_$shares$\}\{$price$\}$