National Olympiad in Informatics, China, 1998

Day 1, Problem 1 - Personal Income Tax

A country's income tax law regulates for citizens' personal income taxes to be based on their wage and income.

Wage taxation is calculated on a monthly basis. 800 dollars worth of fees is subtracted from one's total monthly wage, and the result is used as the base amount from which their personal income tax is calculated. The tax rate is outlined in the following table:

BracketBase Amount Range (Each Month)Tax Rate (%)
1No more than 500 dollars5
2More than 500 dollars, up to 2000 dollars10
3More than 2000 dollars, up to 5000 dollars15
4More than 5000 dollars, up to 20000 dollars20
5More than 20000 dollars, up to 40000 dollars25
6More than 40000 dollars, up to 60000 dollars30
7More than 60000 dollars, up to 80000 dollars35
8More than 80000 dollars, up to 100000 dollars40
9More than 100000 dollars45

Income taxation is calculated independently, and separately each payout instance. For each payout, if the amount does not exceed 4000 dollars, then 800 dollars of fees is taken away to get the base amount. If the amount exceeds 4000 dollars, then 20% of that is subtracted to yield the base amount. The base amount is then used to calculate the income tax rate.

BracketBase Amount Range (Each Payout)Tax Rate (%)
1No more than 20000 dollars20
2More than 20000 dollars, up to 50000 dollars30
3More than 50000 dollars40

From the above, one should realize that both wage and income taxes are to be calculated in a compounded fashion. That is, one must start at the first income bracket and pay as much of that given range as possible according to the rate specified in the bracket. If there is money left over (their current amount exceeds the base amount range), then they move down to the next income bracket, where they apply as much of the excess amount as they can. This continues until they have exhausted all of the value.

For example, an individual's wage for one month is 3800 dollars. After subtracting 800 dollars of fees, they apply the remaining 3000 dollars to each of the income brackets. Bracket 1 is completely filled with 500 dollars, bracket 2 is completely filled with 1500 dollars, and bracket 3 gets the remaining 1000 dollars. The rates applied to the brackets are respectively 5%, 10%, and 15%. Thus the total wage tax for that month is 500×5% + 1500×10% + 1000×15% = 325 (dollars). The calculating process is outlined in the figure given on the left.

You must write a program to help a company keep track of the taxes they have to pay for one year, given the information of all of their payouts (the type of payout, time of payout, and the amount paid). Your program must find the sum of both the wage tax and income tax for all of their employees.

Input Format

The first line of inputs contains one integer M (M ≤ 50000), the number of employees in the company. The remaining lines each describe the information for one payout instance. There are two possible formats:

  • Wage tax payout: PAY ID Date Amount
  • Income tax payout: INCOME ID Date Amount

Here, ID represents the ID of the employee being paid (an integer from 1 to M), Date is the date of the payout in the format MM/DD where MM is the month (1 ≤ MM ≤ 12), DD is the day (1 ≤ DD ≤ 31), and Amount is the amount paid in dollars (assume that each amount is a positive integer no larger than 1 million).

A line with the character "#" denotes the end of input. Adjacent values in the input will be separated by one or more spaces.

Output Format

The output contains a positive number P, the total amount of tax (wage and income) that the company must pay on behalf of all of its employees for that year in dollars. This value must be rounded and displayed to 2 decimal places.

Sample Input

PAY 1 2/23 3800
INCOME 2 4/8 4010
INCOME 2 4/18 800
PAY 1 8/14 6700
PAY 1 8/10 1200
PAY 2 12/10 20000

Sample Output


All Submissions
Best Solutions

Point Value: 7
Time Limit: 1.00s
Memory Limit: 16M
Added: May 01, 2014

Languages Allowed:

Comments (Search)

I've done the computations by hand and my output doesn't match the sample output given.

The samples are definitely correct. The description however can be quite confusing. You have to calculate the wage taxation separately for each month (in this case, the 8/14 and 8/10 ones have to be added). And for each calculation of the wage or income, you have to follow the bracketing system.

I think there's a serious misunderstanding on my part then, here are my calculations for reference:

For taxes on wages, we have:

ID 1 for month 2 needs to pay taxes on 3000. That's 500(0.05) + 1500(0.10) + 1000(0.15) = 325.

ID 1 for month 8 needs to pay taxes on 7100. That's 500(0.05) + 1500(0.10) + 3000(0.15) + 2100(0.20) = 1045.

ID 2 for month 12 needs to pay taxes on 19200. That's 500(0.05) + 1500(0.10) + 3000(0.15) + 14200(0.20) = 3465.

For taxes on income, we have:

The instance of 4010 is reduced down to 3208, and taxes on that are 3208(0.05) = 160.4.
The instance of 800 is reduced to 0, so no taxes are incurred.

This sums to 4995.40.

I'm asking for the problem statement to be validated because I see an accepted solution, which means there is some consistent state somewhere. (Alternatively, I guess I'm asking for an explanation of the sample output that is consistent with the current problem statement.)

Dangit! There actually was a mistake in the description - the income tax percentages were incorrectly transcribed. So sorry about that, it's fixed now.
I'm trying to translate these NOI problems as fast as I can (there really is a lot and my goal right now is just to get them up), that's why there might be these sneaky little mistakes sometimes. I appreciate the efforts to point them out.