House Numbers
Time limit1sMemory limit128 MB
Given add and remove sub-orders over ranges of house numbers, find the set of numbers kept and count how many of each digit 0 to 9 appear across them.
- Level
Medium4 of 10
- Topics
- Implementation, Array, Simulation, Math
- Solved
- No attempts yet
Problem
NarmakSung runs a hardware shop that makes new digit plates for house numbers. If a house number is 195, for example, he has to create one plate for digit 1, one for digit 9, and one for digit 5. But the orders are not always that simple. He may get orders to make digit plates, for example, for all houses on one side of a street.
Since making several plates of the same digit costs much less than making all digits for each house one by one, he wants to know, for a big order he receives, how many of each digit plate he has to make.
Input
The first number in the input, (), is the number of orders. Following this, orders are given. Each order starts with a line containing a street name, an arbitrary string of length at most 50 characters. The next line contains a single integer (), the number of sub-orders, followed by lines of sub-orders. Sub-orders are of three kinds:
- A single house number: the sub-order line contains only a single integer ().
- A series of house numbers: the sub-order line starts with a
+, followed by three integers (). This means plates must be made for house numbers from up to with step ; that is, for . It is guaranteed that , that is a multiple of , and that . - A series of house numbers to be excluded: the sub-order line starts with a
-, followed by three integers under exactly the same conditions as above.
If a house number is ordered more than once across separate sub-orders, it is counted only once as long as it is never excluded (like number 100 in the second order). If a house number is excluded anywhere in an order, it cancels every order for that number, even if the number appears later (like number 500 in the second order). It is also possible to exclude numbers that never appear in any other sub-order; such numbers are simply ignored (like 900 in the second order).
Output
For each input order, one set of output data consisting of 13 lines is written. Each set starts with one line containing the street name exactly as it appeared in the input order. The next line must be of the form C addresses, where is the total number of house numbers to be made. In the special case , the line must read 1 address. The next 10 lines must have the following form: line contains the number of digit plates needed for digit . These 10 lines use the format Make X digit Y, where is how many copies of digit ( from 0 to 9) are needed. The last line states the total number of digits needed, in the format In total Z digits. If only one digit must be produced, it must read In total 1 digit to be grammatically correct. The output is case-sensitive.