Problem M
The Wolf of Wall Street
Jordan has a demanding job as a stockbroker on Wall Street. Every day, clients want to buy and sell stocks on the exchange. The clients may either ask to sell a certain number of a specific stock $X$ at a price $a$ or may bid to buy a specific stock at a price $b$. It is then Jordan’s job to figure out which orders match each other and thus clear the market.
This is further complicated by the fact that there are
$N$ different stocks
listed on the exchange. Being possibly the best stock broker
ever, Jordan has so far managed to keep track of all this
information in his head, but as he is dreaming of four day work
week and is quite the capable programmer, he wonders if he
instead could program a computer to run his exchange for
him.
Whenever the bid price is greater than or equal to the ask price, a deal is struck. A buy order offering the bid price is matched with a sell order demanding the ask price, and shares are exchanged at the rate of the ask price until either the sell order or the buy order (or both) is fulfilled (i.e., the buyer wants no more stocks, or the seller wants to sell no more stocks). The program should, given a list of orders (either buy or sell), a quantity, a ticker and a price calculate, after each order, print the current ask, bid and stock price of the given ticker.
Input
On the first line a positive integer: the number of test cases, at most $100$. After that per test case:
-
One line with an integer $n$ ($1 \leq n \leq 1000$): the number of orders.
-
$n$ lines of the form ”order_type x shares ticker at $y$”, where order_type is either ”buy” or ”sell”, ”ticker” is a string of four characters denoting the stocks of a company, $x$ ($1\leq x \leq 1000$) is the number of shares of a stock someone wishes to buy or to sell, and $y$ ($1\leq y \leq 1000$) is the desired price.
Output
Per test case:
-
$n$ lines each of the form ”$t_ i~ a_ i~ b_ i~ s_ i$” where $t_ i$,$a_ i$,$b_ i$ and $s_ i$ are the current ticker, ask, bid and stock price, respectively, after the $i$-th order has been processed and all possible deals have taken place. Whenever a price is not defined, output ”-” instead of the price.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 7 buy 10 shares AAPL at 100 sell 1 shares NVDA at 120 sell 20 shares TSLA at 110 buy 30 shares TSLA at 110 sell 10 shares AAPL at 99 buy 1 shares NVDA at 120 buy 5 shares AAPL at 100 6 sell 10 shares AAPL at 100 buy 1 shares AAPL at 80 buy 20 shares AAPL at 90 sell 30 shares AAPL at 90 buy 10 shares AAPL at 101 sell 1 shares AAPL at 80 |
AAPL - 100 - NVDA 120 - - TSLA 110 - - TSLA - 110 110 AAPL - - 99 NVDA - - 120 AAPL - 100 99 AAPL 100 - - AAPL 100 80 - AAPL 100 90 - AAPL 90 80 90 AAPL 100 80 90 AAPL 100 - 80 |
