2013
12-11

# Tax Avoidance

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 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 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.

PCS
B 100 10000
B 100  9000
S 150  9500
E
CSC
B  100 10000
S   50 11000
E
#

PCS FBFS   -250.00
CSC LBFS    500.00`

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

4. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。