Connection Status:
Competition Arena > Plusonegame

Plusonegame

SRM 691 · 2016-05-02 · by subscriber

SRM 691 · 2016-05-02 · by subscriber · Simulation, String Manipulation
Class Name: Plusonegame
Return Type: String
Method Name: getorder
Arg Types: (string)
Problem Statement

Problem Statement

Hero plays a game with a deck of cards and a counter. Initially, the counter is set to zero. During the game Hero must play each card in the deck exactly once. He gets to choose the order in which he plays the cards. You are given the description of the deck in the String s. Each character of s is either '+' or a digit ('0'-'9'). Each character represents one card, as described below.
  • Whenever Hero plays a card with a '+', the counter is incremented. (I.e., its value is increased by 1.)
  • Whenever Hero plays a card with a digit, he gets some (possibly zero) penalty points. The number of penalty points is calculated as abs(C - D), where C is the current value of the counter and D is the digit on the card.
Hero wants to minimize the sum of penalty points he receives during the game. Find an order in which he should play the cards, and return that order in a String. If there are multiple optimal orders of cards, return the lexicographically smallest among them.

Notes

  • Let S and T be two different but equally long strings, and let i be the smallest index such that S[i] and T[i] differ. We say that S is lexicographically smaller than T if the character S[i] has a smaller ASCII value than the character T[i].
  • The ASCII value of the '+' character is smaller than the ASCII values of digits.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be either '+' or digit('0' - '9').
Examples
0)
"1++"
Returns: "+1+"

Hero should increment the counter to 1, then play the card '1' for 0 penalty points, and then increment the counter again.

1)
"549"
Returns: "459"

Each of the six possible permutations of these cards leads to the same result: Hero will receive 4+5+9 = 18 penalty points. The string "459" is the lexicographically smallest of the six possible strings.

2)
"++++++"
Returns: "++++++"
3)
"+++++2+"
Returns: "++2++++"
4)
"++++4++++200++2++1+6++++++"
Returns: "00+1+22++4++6+++++++++++++"

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

Coding Area

Language: C++17 · define a public class Plusonegame with a public method string getorder(string s) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous