### James S. Plank

Wed Nov 9 20:32:38 EST 2016
First off, think about what the answer string is going to look like. It will be composed of plus signs and digits, and it should be pretty clear that the digits will be sorted.

Now, let's think about where the plus signs go with respect to the digits. If there are any zeros in the string, they are going to go first, before any plus signs. Why? Because if you put a plus sign before a zero, you have increased the penalty of each zero. If you put zero's first, then they incur no penalty.

Ok, so you put all of the zeros first. Now, what about ones? Well, if you have a plus sign, you should put one of them before the one's. Then the one's don't incur any penalty.

You keep doing this for every digit, until you run out of digits. At that point, you simply put all of the remaining plus signs at the end of the string, because plus signs at the end of the string don't penalize you.

Let's reiterate. Suppose your string is "+++987+++654+++321+++011". That's 12 plus signs, three 1's, and one of each other digit. So, your answer will be:

"0+111+2+3+4+5+6+7+8+9+++"

Now, let's think of how best to program this one. I think that the cleanest way to do it is to have a vector with ten elements. Element i is the number of occurrences of the digit 'i'. Additionally, you need to count the plus signs. Then, you can construct the return string from these two pieces of data.

In example 0, the string is "1++". That means that your vector is {0,1,0,0,0,0,0,0,0,0}, and your count of plus signs is 2. Your answer will be "+1+". In example 4, your vector is {2,1,2,0,1,0,1,0,0,0}, and your count of plus signs is 19. Your answer will be "00+1+22++4++6+++++++++++++".

Here are all six examples, printing the vector and the number of plus signs, before calculating the return value:

```UNIX> a.out 0
Digit_Counts: {0,1,0,0,0,0,0,0,0,0}
Plus_Signs:   2
+1+
UNIX> a.out 1
Digit_Counts: {0,0,0,0,1,1,0,0,0,1}
Plus_Signs:   0
459
UNIX> a.out 2
Digit_Counts: {0,0,0,0,0,0,0,0,0,0}
Plus_Signs:   6
++++++
UNIX> a.out 3
Digit_Counts: {0,0,1,0,0,0,0,0,0,0}
Plus_Signs:   6
++2++++
UNIX> a.out 4
Digit_Counts: {2,1,2,0,1,0,1,0,0,0}
Plus_Signs:   19
00+1+22++4++6+++++++++++++
UNIX> a.out 5
Digit_Counts: {0,3,0,0,0,0,0,0,0,5}
Plus_Signs:   2
+111+99999
UNIX>
```

Solution.cpp.

I have it commented below, too:

 ```/* Topcoder SRM 691, D2, 300-Pointer * James S. Plank * November, 2016 */ #include #include #include #include #include using namespace std; class Plusonegame { public: string getorder(string s); }; string Plusonegame::getorder(string s) { vector Digit_Counts; /* This is the number of times each digit appears in the string */ int Plus_Signs; /* This is the number of times that the plus sign appears in the string */ string rv; /* The return string. */ int i, j; /* Initialize Plus_Signs and Digit_Counts to zero. */ Plus_Signs = 0; Digit_Counts.resize(10, 0); /* Count the digits and the plus signs. */ for (i = 0; i < s.size(); i++) { if (s[i] == '+') { Plus_Signs++; } else { Digit_Counts[s[i]-'0']++; } } /* Print out the digits and the plus signs. */ printf("Digit_Counts: {%d", Digit_Counts[0]); for (i = 1; i < 10; i++) printf(",%d", Digit_Counts[i]); printf("}\n"); printf("Plus_Signs: %d\n", Plus_Signs); /* Create the return string from Digit_Counts and the number of plus signs. */ for (i = 0; i < 10; i++) { for (j = 0; j < Digit_Counts[i]; j++) rv.push_back('0'+i); if (Plus_Signs > 0) { rv.push_back('+'); Plus_Signs--; } } /* If there are still plus signs, put them at the end of the return string. */ while (Plus_Signs > 0) { rv.push_back('+'); Plus_Signs--; } return rv; } ```