HDU 1458 Tax Avoidance

Problem Description

Now that inflation is under control the tax base is fairly stable, and hence the Infernal Revenue Department is desperately seeking more ways of extracting more money from the citizenry. One proposal is to institute a capital gains tax - in particular a tax made on the profit realised by buying and selling shares on the Stock Exchange. This seems to be a safe bet, since most ordinary people are not involved and therefore it will only affect the ``rich'' who can afford to pay. However, the Society of Creative Acountants has heard of these proposals and realise that it could well affect them.

The problem arises from the fact that shares do not have a fixed (or even steadily moving) price, and thus one has to determine which of the entire portfolio were sold. IRD have identified two ways of determining this; called respectively First Bought, First Sold (FBFS) and Last Bought, First Sold (LBFS). These are most easily explained by an example. Assume that you bought 10000 shares at 100c per share, then bought another 10000 at 90c per share and then sold 15000 shares at 95c per share. The sale will realise $14,250. Under the FBFS method you will be deemed to have sold the oldest stocks first so they will have cost you $10,000 plus $4,500, i.e. $14,500. You have therefore suffered a loss of of $250 and would not be liable for tax. Under the LBFS scheme, you are deemed to have sold the youngest shares first and hence these would have cost $9000 plus $5000, a total of $14,000, meaning you would have to pay tax on $250.

Write a program that will read in a series of share transactions, and for each share determine which method is the optimum. The optimum is the one that minimises the profit (if both earn a profit) or maximises the loss (if at least one makes a loss). In case of a tie, choose LBFS.

Input

Input will consist of a series of sets of share transactions. Each set will start with the name of the share (3 upper case characters) on a line by itself. This name will be unique in the data set. This will be followed by a series of buy and sell transactions. Each transaction will be on a line by itself and will start with one of the letters `B' (Buy) or `S' (Sell), followed by the number of shares involved (up to 100,000) and the price (in cents, up to 10,000) separated by one or more spaces. You will never sell more shares than you own. Each set of transactions will be terminated by a line starting with an `E'. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each set of transactions. Each line will consist of the share name, a single space, the chosen method, a single space and the profit or loss on the overall transaction (in dollars). This should be in a field 9 characters wide with two digits after the decimal point.

Sample Input

PCS

B 100 10000

B 100 9000

S 150 9500

E

CSC

B 100 10000

S 50 11000

E

#

Sample Output

PCS FBFS -250.00

CSC LBFS 500.00

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
using namespace std;
string s,c;
long long ans1,ans2,x,y;
struct two
{
	long long x,y;
	two(){}
	two(long long x,long long y):x(x),y(y){}
};

int main()
{
	while (cin>>s,s!="#")
	{
		deque<two> p,q;
		ans1=ans2=0;
		while (cin>>c,c!="E")
		{
			if (c=="B")
			{
				scanf("%lld%lld",&x,&y);
				p.push_back(two(x,y));
				q.push_back(two(x,y));
			}
			else
			{
				scanf("%lld%lld",&x,&y);
				ans1+=y*x;
				for (long long i=x;i>0;)
				{
					long long j=p.back().x,k=p.back().y;
					p.pop_back();
					if (i>=j) {i-=j; ans1-=j*k;}
					else {ans1-=i*k; p.push_back(two(j-i,k)); i=0;}
				}
				ans2+=y*x;
				for (long long i=x;i>0;)
				{
					long long j=q.front().x,k=q.front().y;
					q.pop_front();
					if (i>=j) {i-=j; ans2-=j*k;}
					else {ans2-=i*k; q.push_front(two(j-i,k)); i=0;}
				}
			}
		}
		cout<<s<<" ";
		printf("%s ",ans2<ans1?"FBFS":"LBFS");
		printf("%9.2lf\n",0.01*min(ans1,ans2));
	}
	return 0;
}