Problem I. 370. (March 2015)
I. 370. There is only one old and unstable suspension bridge over a wild mountain river. The bridge consists of cables attached together, and of some planks lying across the cables. At some places there are gaps between the planks, so we want to repair the bridge or rearrange the planks, but we have only a few extra of them.
Someone measured the gaps between the planks from the left bank to the right bank of the river. The file hid.txt, downloadable from our webpage, contains these data in centimeters.
The first line of the file contains the length \(\displaystyle H\) of the suspension bridge (\(\displaystyle 300\le H\le 50\;000\)). The second line contains the theoretically determined safe step length \(\displaystyle L\) (\(\displaystyle 40\le L\le 80\)). The following \(\displaystyle N\) lines (\(\displaystyle 1\le N\le H\)) contain the distance between the planks. Walking through the planks is safe, if any plank distance is smaller then the step length \(\displaystyle L\) (since each plank is narrow, its width is neglected).
For example (with / denoting a newline character): 352 / 75 / 28 / 74 / 84 / 22 / 69 / 73 / ...
In the example, the bridge length is 352 cm, the safe step length is 75 cm, the distance between the first plank and the left bank of the river is 28 cm, the distance between the first plank and the second plank is 74 cm, and so on.
Your program i370 should solve the following tasks.
Before writing any result to the screen, the number of the actual task (for example, Task 4) should be displayed. Diacritical marks in the output may be omitted.
1. Read the data from the file hid.txt and solve the following tasks.
2. Display the distance between the last plank and the right bank of the river.
3. Determine the distance (in cm) up to which we can walk safely on the bridge starting from the left bank. If the entire bridge is safe, then you should display this information.
4. Display the longest connected bridge segment where walking through is not safe, by specifying the starting and final plank numbers of this segment.
5. We want to remove a single plank. In how many ways can we do this such that one can still walk safely through the newly introduced gap?
6. Collect and display all neighboring plank pairs between which at least one new plank should be installed to make the bridge safe. For example: 2-3.
7. Give the minimum number of planks to be installed to make the bridge safe.
8. Two people would like to cross the original old bridge by holding each other's hands. They agree that no two feet will be put on the same plank. Moreover, they carry some extra planks to put down temporarily in front of them when necessary; after they pass over that plank, the second person can get it again within 1 step length and give it back to the first person. Determine the minimum number of planks they have to carry so that they can safely cross the bridge. Planks originally attached to the bridge cannot be removed.
Example: the feet positions of person A and person B as they move along:
A_foot1 5, A_foot2 4, B_foot1 3, B_foot2 2, B can get the first plank if it is not attached and give it to A. A can put down a plank in front of them at distance \(\displaystyle L\), A_foot2 6, B_foot2 4, he can get the second plank ...
The source code (i370.pas, i370.cpp, ...) of your program with its short documentation (i370.txt, i370.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted.
Downloadable file: hid.txt
(10 pont)
Deadline expired on April 10, 2015.
Statistics:
12 students sent a solution. 10 points: Németh 729 Gábor. 9 points: Dombai Tamás, Hamrik Szabin, Rittgasszer Ákos. 8 points: 4 students. 7 points: 3 students. 5 points: 1 student.
Problems in Information Technology of KöMaL, March 2015