Informatica Online Judge

  Barn Repair (외양간 수리) [0259 / 0103]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 71   Total Tried : 366


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 215byte
My Best Submission (C++) : N/A

[]

Background

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer Johns cows. Happily, many of the cows were on vacation, so the barn was not completely full.

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.

어둡고 폭풍이 몰아치던날밤, 농부 John의 젖소들이 있는 외양간 지붕과 문이 날라가 버렸다. 다행히 많은 젖소는 자리에 없었서(휴가중) 외양간은 가득하지 않았다.

외양간에 있던 젖소들은 외양간의 칸에서 서로서로 몸을 한줄로 길게 가까이 붙인채 있었다. 몇개의 외양간 칸 안에는 젖소들이 있었다; 몇개에는 없었고. 모든 칸들은 모두 같은 너비이다.

농부 John은 문들이 없어졌기 때문에, 그 칸들 앞에 빨리 새로운 판자들을 세워야 한다. 그에게 목재판을 제공하는 새로운 사람은 그가 어떤 길이를 원하던 그에게 만들어 줄것이다, 하지만 목재판을 제공하는 사람은 모든 판자들 중에서 적은 수만 운반해줄 것이다. 농부아저씨 Farmer John은 그가 구입해야만 하는 판자들의 최종길이를 최소화하고 싶어한다.

구입할 수 있는 최대의 판자수 M(1 <= M <= 50) 외양간이 가진 최대 칸 S(1 <= S <= 200);외양간의 칸들 안에 있는 젖소들의 수 C(2 <= C <= S), 젖소들이 차지하고 있는 칸들의 수(1 <= stall_number <= S)가 주어질 때, 젖소들을 그 안에 가두기 위해 막혀져야 하는 최소한의 빈칸을 계산하여라.

필요한 총 칸막이 개수를 출력하는 프로그램을 작성하시오.

Input

첫 줄에 M, S, C가 공백으로 구분되어 입력된다.
두 번째 줄부터 C개의 줄에 걸쳐서 소가 있는 칸의 번호가 입력된다.

Output

필요한 칸막이 개수를 출력한다.

IO Example

입력
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

출력
25

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]