I'm just a student so this might be wrong, but here's how i interpreted it:
The program:
Basically you are asked to create a program that takes in a string as an argument and outputs the number: X + Y
(and you want X+Y to be as small as possible)
Finding X:
When your program starts you are allowed to change ONE of the letters in your string. But you dont have to do this.
X is the difference in ASCII value of the two letters that change.
So, for example, if you are given the string "abc" and you change the letter "a" to a "d":
"a" has the ASCII value: 97
"d" has the ASCII value: 100
So the difference (X) is 3 (because 100-97 = 3)
if you dont change the string then the difference (X) will always be 0.
(you may think that you should never change the string then, because then X will always be 0. But you have to keep in mind that changing one of the letters may result in Y becoming many times smaller so the overall the output of the program (X+Y) is smaller )
Finding Y:
I'm not 100% sure about this part but here is how i understood it:
Basically you have to choose two (a pair of) indices in your string array.
The two indices are denoted as i and j.
BUT you cant just choose any pair of indices, the two indices you choose must follow these "rules":
1) i must either be 1 or larger
2) i must be less than j
3) j must be less than or equal to the length of the string
4) The ASCII value of the character at index i must be less than the ASCII value of the character at index j
There may be 0 or multiple pairs that follow these rules.
Y is the number of pairs that follow the rules.
Hard part:
The hard part is that your program MUST output the smallest possible number.
So for example if you are given a string
and you dont change a letter in the string: then X will be 0 and Y will be 10. Output 10.
But if you instead change one of the letters so that X is 3 that could result in Y only being 4. Output 7.
How to solve it:
i have no idea :-(
Perhabs somebody can confirm whether my interpretation is correct, and how to solve it?
Stav, I think your explanation has one small problem. Rule #3 for the values of i and j is that i must be less than or equal to j. So basically a naive way to compute Y is:
1 2 3 4 5 6 7 8
string S;
...
unsigned Y=0;
for (size_t i=0; i< S.size()-1; ++i) {
for (size_t j=i+1; j<S.size(); ++j) {
if (S[i] < S[j]) ++Y;
}
}
Now to solve it? Hmm. Consider one position in the string. When you change it, it affects Y only for the pairs that involve that position. I guess you could compute the best X+Y value for changing that position. Then move to the next position and do the same.