시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 21 | 18 | 16 | 84.211% |
In order to even start running a campaign, you need some amount of money. How else are you going to pay for annoying robo-calls, slanderous TV ads against your opponent, or all those suits you will have to wear on the campaign trail? There are many different ways of raising funds, including old-fashioned donations, ads on the Internet, expensive fund-raising dinners, and others.
As campaign donations could be construed2 as buying influence over a candidate, campaign finance laws place limits on the total amount of donations that any person can make to a candidate or party. According to the recent 2002 campaign finance law, any individual can contribute at most \$2100 to any one candidate, and at most \$40000 total. However, when these donations are divided over many transactions, it may be hard to figure out just how much someone donated.
You are to write a program that takes a sequence of individual donations, and finds out whether there were any violations, and if so, which donors violated the limits.
2unfortunately, frequently rightly so
The first line contains a number K ≥ 1, which is the number of input data sets in the file. This is followed by K data sets of the following form:
The first line of a data set contains three numbers c, d,t with 1 ≤ c ≤ 100, 1 ≤ d ≤ 1000, 1 ≤ t ≤ 100000. Here, c is the number of political candidates (numbered 1, . . . , c), d the number of donors (numbered 1, . . . , d), and t the number of transactions.
This is followed by t lines, each consisting of three integers di, ci, mi. This line means that transaction i, donor di gave mi dollars to candidate ci. Notice that the same donor-candidate pair can appear multiple times.
For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then, output either the line “No violations” on a line by itself, or “Violators:” on a line by itself, followed by all the donors who violated one of the limits, each on a line by himself. The donors are to be sorted by increasing number.
2 3 2 4 1 1 1500 1 2 500 2 1 100 2 3 2000 3 2 4 1 1 1500 1 2 500 2 3 2500 1 2 1700
Data Set 1: No violations Data Set 2: Violators: 1 2