Pricing TollboothsProblem code: TOLLS |
All submissions for this problem are available.
Your company has recently built its own highway from which they hope to generate some revenue. The highway has no branches or intersections, it is a simple line segment. Your company also has access to simple data from some potential customers that describe their start and endpoint locations and their budget.
Tollbooths are also located on various locations on the highway. The total toll a customer pays is the sum of all tolls on the tollbooths that lie between their start and end locations. If a customer cannot afford the total toll they must pay, then they simply don't make the trip and end up paying nothing.
No customer wants to start or end their destination at the precise location of a tollbooth so we can represent the problem as follows. We have a graph that is a simple path with N nodes. Each node represents a potential start or end location of a customer and there is a single tollbooth located on the middle of each edge. So the total toll a customer pays is the sum of the tolls on the edges they cross to reach their endpoint.
Your task is to set the tolls on each of the tollbooths to generate some revenue for your company.
Input:
The first line contains an integer T (about 40) indicating the number of test cases.
Each test case begins with two positive integers N and M (both at most 100) where N is the number of nodes in the graph and M is the number of potential customers. M lines follow where the i'th line contains the information of the i'th client.
Each such line consists of three integers S, E, B where 1 <= S,E <= N are, respectively, the start and end locations of the customer and 1 <= B <= 1,000,000 is the customer's budget.
A blank line separates test cases (as well as the first line containing T and the first test case).
Output:
For each test case, you are to output a single line consisting of N-1 integers, each of which is between 0 and 1,000,000. The i'th integer (1 <= i <= N-1) denotes the toll placed on the edge connecting nodes i and i+1.
Scoring:
From the output, we will calculate the total revenue obtained from all customers who can afford the total toll on their route according to the prices you set. The score for each test case is then calculated as R/T where R is the revenue obtained and T is the total budget of all customers. The score for the entire set of test cases is just the sum of the scores of each individual test case.
Example: Input:
2 3 3 1 2 10 2 3 10 1 3 10 4 3 1 2 10 2 3 10 1 4 15
Output:
5 5 10 10 0
In the first test case, the first two customers only pay a total toll of 5 and the last customer pays 10 so the total revenue is 20. The score for this case is 20/30.
In the second case, the first two clients pay their full budget but the last client cannot afford the desired route. The total revenue is then 20 and the score for this case is 20/35.
| Author: | friggstad |
| Date Added: | 10-04-2010 |
| Time Limit: | 7 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
only to make sure...is S<E
only to make sure...is S<E always TRUE?
no, reverse travel from
no, reverse travel from 4-1(say) is also possible
Which submission counts, the
Which submission counts, the highest score or the last submission?
@atul: First of all, you
@atul: First of all, you should not be discussing specific test cases and their solutions. It is grounds for disqualification. Secondly, this is the challenge problem, meaning there is no one right answer. You can output whatever you want provided it conforms to the output specification, and it will be scored is described by the problem statement.
I have some 3 submitions,
I have some 3 submitions, will only count my last submition?
plz admin explain what's
plz admin explain what's going wrong in my code..
output is coming correct..
output is coming correct..
@Niels, walter - it always
@Niels, walter - it always uses your best submission even if you submit worse ones afterwards.
@Kallol - you will not be given hints until after the contest has finished.
dont u think output for last
dont u think output for last test case shld be 7 7 0 ..... so tat revenue generated is (7 + 7 + 14) = 28 /35
or 5 5 5 .... so tat revnue generated is ( 5 +5 + 5) = 25/35
As David said, there is no
As David said, there is no right answer; as long as you output a valid answer it will be accepted. The sample output is a valid answer.
Are multiple submissions
Are multiple submissions allowed on this problem?
if the answer for the first
if the answer for the first test case is
10 10
is it wrong?
No, that is a valid output.
No, that is a valid output.
then every answer should be
then every answer should be treated as correct answer but the scoring will be done on the basis of total revenue genareated
and if i am right then why am i getting wrong answer ?
You will be adjudged wrong
You will be adjudged wrong answer if your output does not comply with the output format mentioned in the problem.
I think the output format is
I think the output format is correct for me, still I am getting wrong answer. The output is long integers separated by one space and there is no trailing space at the end of line.
If you are getting wrong
If you are getting wrong answer, then your output format is not correct, so you shouldn't think it is.
I have the following in my
I have the following in my output file for given input:
9 10
4 9 2
Please tell the mistake.
Well of course that is valid;
Well of course that is valid; the judge will test your code on different inputs than that!
The output for a test case is
The output for a test case is long integers separated by one space in a single line and there is no trailing space at the end of line. There is no extra line between different test cases. I am using this output format. Is it correct?
For each test case, you are
For each test case, you are to output a single line consisting of N-1 integers, each of which is between 0 and 1,000,000. If you're doing that ... it WILL be accepted.
I am sorry to bother by so
I am sorry to bother by so many comments, but I am still getting error. The program is working fine on my machine and I have tested by generating more test cases. If it is acceptable I can provide the lines of my program which I am using for printing.
I'm afraid you will have to
I'm afraid you will have to wait until the end of the contest if you want help. Please do not post code.
I am unable to submit
I am unable to submit solution to this problem...
Is their any problem in the website right now??
@admin why am I unable to
@admin
why am I unable to submit solution to any problem ??
People are submitting their solutions but I can't....
Do we get any other info
Do we get any other info about test case structure? Are they randomly generated or are there hand-crafted tests as well? What are the distributions for variables N, M and B?
These tiebreakers are consistently lacking this kind of information. I don't think the intent is to force us to submit a whole bunch of solutions just to extract that info.
Some of the data is randomly
Some of the data is randomly generated and some of it is hand-crafted to defeat simplistic approaches. Moreover, the random data was generated in a few different ways.
If we do not have info on the
If we do not have info on the test data in the problem statement, please do not reveal them by posting comments. You are then giving information to only a fraction of all the people participating, since not everyone reads all the comments.
I agree that the information
I agree that the information should be included in the problem statement. But if you have done so, don't include the information as comments.
Its the last day of the
Its the last day of the contest, and I still see differences in what the scoreboard shows and what we see in the my submissions page!
@admin Are u sure ur test
@admin
Are u sure ur test data matches the constraints??
If the constraints are true than maixmum sum of all the tolls shud fit in an integer assuming MAXB is 1e6.
But i get wa when i try to use that fact.So much so,that i get wa even after using long long int.
Appreciate if u check into the problem.
The test data does conform to
The test data does conform to the input specification.
Will the code be judged
Will the code be judged against unseen test data after the contest?
And if yes, will all the
And if yes, will all the accepted submissions be used (and the max score taken)? Or just the current highest scoring submission?
The submissions do not get
The submissions do not get rejudged on new data. The current data is what is used.
Why is there a slight
Why is there a slight difference between the score on the 'My Submissions' Page and the rank page?
e.g in my case, my best submission scores .851 points, but my score on ranklist is 5.837. I haven't made any submission that fetched me .837 points.
The main scoreboard is always
The main scoreboard is always right. The one on 'My Submissions' has been wrong for months.