Hey guys, just wanna share my approach and wanna know your way of doing them!
Quite a famous puzzle, sorting the array and the traveller with min element always takes others to other end.
lets say probability is x (p/100), for the n-1 lines, total prob. is x^(n-1) and lets say we have y as the increased prob. so y^n = x^(n-1) => y = x^(1-1/n). So our increase is p — y*100. (Use doubles)
Problem D1: Line of Delivery (Part 1)
As each of the stone can replace next stone and pass on the energy, the final positions will be the same as input energies. If 0 to i stones are thrown, the resulting positions will be sorted energies of 0 to i. So just sorting the array and indexing 1 from end works. Taking the upper or lower key with min difference for each G outputs ans.
Problem D2: Line of Delivery (Part 2)
If you guys solved problem C & D2, please let me know your approaches.
C: Suppose you know that "a lot" of points are on one line (let's say, over half). Can you find a simple way of finding that line?
D2: The same observation as for D1 — we just need to find the final positions of the balls, because we know they will be in sorted order. Now suppose we already launched $$$k$$$ balls, and they have positions $$$a_1, \ldots, a_k$$$. A new ball comes in with energy $$$x$$$ — how does that affect the sequence? My hint is instead of looking at $$$a_i$$$, look at $$$b_i := a_i - i$$$ (assuming $$$a_i$$$ is sorted).