- 2 Charlemagne The King Of Frankia Is Considering Building Some Castles On The Border With Servia The Border Is Divide 1 (213.45 KiB) Viewed 46 times
2 Charlemagne, the King of Frankia, is considering building some castles on the border with Servia. The border is divided into N segments. The King knows the height of the terrain in each segment of the border. The height of each segment of terrain is stored in array A, with A[P] denoting the height of the P-th segment of the border. The King has decided to build a castle on top of every hill and in the bottom of every valley. Let [P..Q] denote a group of consecutive segments from P to Q inclusive such that (0 ≤ P ≤ Q≤ N-1). Segments [P..Q] form a hill or a valley if all the following conditions are satisfied: • The terrain height of each segment from P to Q is the same (A[P] = A[P+1] = ... = A[Q]); • If P >0 then A[P-1] <A[P] (for a hill) or A[P-1] > A[P] (for a valley); ● If Q< N-1 then A[Q+1] <A[Q] (for a hill) or A[Q+1] > A[Q] (for a valley); That is, a hill is higher than its surroundings and a valley is lower than its surroundings. Note that if the surroundings on either side of the hill or valley don't exist (i.e. at the edges of the area under consideration, where P = 0 or Q = N-1), then the condition is considered satisfied for that side of the hill/valley. 11 Flies task S t Test Outp