COCI '11 Contest 1 #1 Jabuke

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 1.0s
Memory limit: 32M
Problem type

Mirko has recently discovered an old video game. The screen of this game is divided into N columns. At the bottom of the screen, there is an M-columns-wide boat (M < N). The player can move this boat left or right during the game, but the boat must remain completely within the screen at all times. The boat initially occupies the leftmost M columns.

Apples are being dropped from the top of the screen. Each apple starts its fall at the top of one of the N columns, falling straight down until it reaches the bottom of the screen. The next apple starts its fall just after the current one has reached the bottom.

An apple is said to be picked up if the boat is placed so that it occupies the column down which the apple is falling when it reaches the bottom. The goal of the game is to pick up all of the apples, in a way that minimizes the distance that the boat must travel.

Input Specification

The first line of input contains two space separated integers N and M (1 \le M < N \le 10).

The second line of input contains an integer J (1 \le J \le 20), the number of falling apples.

The following J lines contain the column positions of those apples, in the order in which they will fall.

Output Specification

The only line of output must contain the minimal distance that the boat must travel in order to pick up all the apples.

Sample Input 1

5 1
3
1
5
3

Sample Output 1

6

Sample Input 2

5 2
3
1
5
3

Sample Output 2

4

Comments


  • 0
    NightShade922526  commented on Dec. 7, 2021, 1:11 a.m. ← edit 4

    I think example case number 2 is wrong if calculated mathematicallly. The boat starts with length 2 so the first apple will fall right in. The second apple is at 5, so the boat needs to travel 3 units to get it. The 3rd apple is at 3, where the other end of the boat is, so the answer i think is 3. Please tell me if i am wrong or not.


    • 3
      d  commented on Dec. 7, 2021, 7:06 a.m.

      When the boat collects the second apple, the boat occupies columns 4 and 5. The boat must move left 1 column to collect the third apple.