COCI '11 Contest 1 #1 Jabuke

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$ $N$ columns. At the bottom of the screen, there is an $M$ $M$ -columns-wide boat $(M < N)$ $(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$ $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$ $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$ $N$ and $M$ $M$ $(1 \le M < N \le 10)$ $(1 \leq M < N \leq 10)$ .

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

The following $J$ $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

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

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.

2

NightShade922526 commented on Dec. 9, 2021, 7:57 p.m.

thank you