Connection Status:
Competition Arena > SynchronizingGuideposts

SynchronizingGuideposts

SRM 309 · 2006-06-28 · by _efer_

SRM 309 · 2006-06-28 · by _efer_ · Search
Class Name: SynchronizingGuideposts
Return Type: long
Method Name: minCost
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

There are several guideposts on one side of a highway indicating the distance to a gas station that has not yet been built. Unfortunately, the guideposts are not synchronized, so they might not all refer to the same location. You must build the gas station at a location that will minimize the cost of moving the guideposts to their correct positions. It costs one dollar per kilometer to move each guidepost. In addition, there is a limit to how far each guidepost can be moved without incurring further taxes. If a guidepost is moved further than than its limit, it costs an additional C dollars for each kilometer that exceeds the limit.

You are given a String[] guideposts, each element of which describes a single guidepost. Each element is formatted as "position distance limit" (quotes for clarity only), where position is a nonnegative integer specifying the location of the guidepost relative to the entry point of the highway, distance is an integer specifying the distance to the gas station that's written on the guidepost (negative values mean that the guidepost is located beyond the gas station), and limit is a nonnegative integer specifying the maximum distance the guidepost can be moved without paying further taxes. All values are given in kilometers. The position of the gas station relative to the entry point of the highway must be a nonnegative integer. Return the minimum cost of moving the guideposts as a long.

Notes

  • Since the position of the gas station has to be a nonnegative integer, there is no need to move a guidepost by a fractional amount.

Constraints

  • guideposts will contain between 1 and 50 elements, inclusive.
  • Each element of guideposts will contain between 5 and 50 characters, inclusive.
  • Each element of guideposts will be formatted as described in the problem statement.
  • Each position will be an integer between 1 and 1,000,000,000, inclusive.
  • Each distance will be an integer between -1,000,000,000 and 1,000,000,000, inclusive.
  • Each limit will be an integer between 0 and 1,000,000,000, inclusive.
  • Each position, distance, and limit may include leading zeros.
  • C will be between 1 and 1000, inclusive.
Examples
0)
{"6 -1 5","2 10 4","10 0 5","8 6 5","20 -6 4"}
1000
Returns: 15

With C being so high, we better make sure that none of the guideposts are moved beyond their limits. We can do this by placing the gas station at position 10.

1)
{"59 23 13","9 8 28","91 18 50","32 10 80","110 61 120","54 45 18","73 24 118","30 8 73"}
5
Returns: 479

Placing the gas station at position 81 yields the optimum cost.

2)
{"79 4 114","68 41 102","80 80 68","48 1 50","59 17 34","118 59 17","29 3 11","31 26 48","74 27 2"}
46
Returns: 5731
3)
{"61 -55 20","35 -25 6","53 -14 78","52 -16 78","71 49 21","80 71 72","70 61 7","23 68 125","20 -16 9","99 44 82","78 -58 100","56 -16 70","14 9 3","86 63 99"}
735
Returns: 207977
4)
{"109 -99 82","23 9 62","104 39 88","64 17 86","100 -96 23","101 -86 87","11 10 5","58 -24 25","34 -26 65","26 21 113","110 -25 116","42 9 10","57 14 105"}
908
Returns: 39432
121)
{"1 -2 10","2 -3 20","3 -4 30","4 -5 40","5 -6 50"}
333
Returns: 5

Interestingly, all guideposts refer to the same position. Since this position is slightly off the highway, you should move each guidepost one kilometer.

Submissions are judged against all 130 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SynchronizingGuideposts with a public method long long minCost(vector<string> guideposts, int C) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous