This challenge is inspired by a thread in the C board that was lost during the forum reset. It's complexity lies in finding the correct algorithm, the implementation is trivial.

I also added a second question, one that wasn't part of the thread in the C forum, which is pretty hard to answer.

I can give a small hint for the second question, it involves graphs...Code:`Two stone age men have gathered an impressive collection of boulders in their cave, all`

of different size and weight, standing neatly one after the other, in the order they have

been collected. To restore some order in the room, they want to arrange the boulders

from the smallest to the largest, with the smallest at the entrance of the cave and the

largest close to the back wall.

Each boulder is only represented by its weight, so the heavier it is, the largest it is (we

assume that they are all made of the same material). As there are only 2 stone age men,

and the space inside the cave is limited, they are only allowed to swap two boulders at a

time. Additionally, to save their energy, they want to use a method that allows them to

move the minimum necessary weight only.

1. Write an algorithm that takes an array of boulders and orders it from the smallest to the

largest, by only swapping two boulders at a time but with the least effort in terms of kilos

moved.

Example:

{5, 3, 1}

-> {1, 3, 5} and necessary effort: 1+5 = 6

{6, 4, 1, 2}

-> {6, 1, 4, 2}, effort 5

-> {6, 2, 4, 1}, effort 3

-> {1, 2, 4, 6}, effort 7

total effort: 15

2. Prove that your solution is optimal.