The Motorway Solution translated (Looking for a Challenge 2)

Revision en1, by KKOrange, 2024-04-01 14:38:49

Hello everyone!

After one year, I am back to translating Looking for a Challenge 2. At this rate, I will finish in 2060 :)

Today, I am looking at "The Motorway" from 2013 (see page 79 for English task statement). Abridged problem statement:

There are $$$n$$$ entry points along a motorway. The $$$i$$$th entry point is located $$$a_i$$$ metres from the start of the motorway.

Byteasar would like to build $$$n+1$$$ tollbooths on the motorways so that: - The tollbooths are evenly spread out so that the distance between consecutive tollbooths is the same - Between every two consecutive entry points, there is a tollbooth (it is acceptable for a tollbooth to be positioned exactly at one of the entry points). - There is a tollbooth before the first, and after the last entry point (or exactly at).

Formally, an arrangement of tollbooths can be described by the position of the leftmost booth $$$b_0$$$ and a distance $$$l$$$ between consecutive tollbooths. The tollbooths would be positioned at $$$b_0, b_0 + l, b_0 + 2l, \ldots, b_0 + nl$$$. The $$$j$$$th entry point must be positioned in the interval $$$[b_0 + (j-1)l, b_0 + jl]$$$.

Your job is to find the minimum and maximum possible $$$l$$$ where an arrangement exists. Give your answer within an epsilon of $$$10^{-8}$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English KKOrange 2024-04-01 16:05:27 2 Tiny change: '$\frac{1}{s}$).\n\nCl' -> '$\frac{1}{i}$).\n\nCl'
en3 English KKOrange 2024-04-01 15:00:38 0 (published)
en2 English KKOrange 2024-04-01 15:00:25 3098
en1 English KKOrange 2024-04-01 14:38:49 1458 Initial revision (saved to drafts)