시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB117355816468050.886%

문제

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

예제 입력 1

5 1
3
1
5
3

예제 출력 1

6

예제 입력 2

5 2
3
1
5
3

예제 출력 2

4
W3sicHJvYmxlbV9pZCI6IjI4MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWFjZmMgXHViMmY0XHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzYyNFx1Yjc3ZFx1YzJlNFx1YzVkMFx1YzExYyBcdWJjMTRcdWFkNmNcdWIyYzhcdWI5N2MgXHVjNjJlXHVhZTMwXHViMjk0IFx1YzYyNFx1Yjc5OFx1YjQxYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWMyYTRcdWQwNmNcdWI5YjBcdWM3NDAgTlx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyYTRcdWQwNmNcdWI5YjBcdWM3NTggXHVjNTQ0XHViNzk4XHVjYWJkXHVjNWQwXHViMjk0IE1cdWNlNzhcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTU4XHViMjk0IFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YWMwMCBcdWM3ODhcdWIyZTQuIChNJmx0O04pIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViMjk0IFx1YzkxMVx1YzVkMCBcdWJjMTRcdWFkNmNcdWIyYzhcdWI5N2MgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJjMTRcdWFkNmNcdWIyYzhcdWIyOTQgXHVjMmE0XHVkMDZjXHViOWIwXHVjNzU4IFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJjMTRcdWFkNmNcdWIyYzhcdWIyOTQgXHVjNjdjXHVjYWJkIE1cdWNlNzhcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHVkMDZjXHViOWIwXHVjNzU4IFx1YzcwNFx1YzVkMFx1YzExYyBcdWMwYWNcdWFjZmMgXHVjNWVjXHViN2VjIFx1YWMxY1x1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWFjZmNcdWIyOTQgTlx1Y2U3OFx1YzkxMSBcdWQ1NWMgXHVjZTc4XHVjNzU4IFx1YzBjMVx1YjJlOFx1YzVkMFx1YzExYyBcdWI1YThcdWM1YjRcdWM5YzBcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBcdWMyYTRcdWQwNmNcdWI5YjBcdWM3NTggXHViYzE0XHViMmU1XHVjNWQwIFx1YjJmZlx1Yzc0NFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NWMgXHVjMGFjXHVhY2ZjXHVhYzAwIFx1YmMxNFx1YjJlNVx1YzVkMCBcdWIyZmZcdWIyOTQgXHVjOTg5XHVjMmRjLCBcdWIyZTRcdWI5NzggXHVjMGFjXHVhY2ZjXHVhYzAwIFx1YjVhOFx1YzViNFx1YzljMFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxNFx1YWQ2Y1x1YjJjOFx1YWMwMCBcdWMwYWNcdWFjZmNcdWFjMDAgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1Y2U3OFx1Yzc0NCBcdWNjMjhcdWM5YzBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWJjMTRcdWFkNmNcdWIyYzhcdWIyOTQgXHVhZGY4IFx1YzBhY1x1YWNmY1x1YWMwMCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHViMmZmXHVjNzQ0IFx1YjU0YywgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YjJmNFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIyZjRcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmMxNFx1YWQ2Y1x1YjJjOFx1Yzc1OCBcdWM3NzRcdWIzZDkgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBNICZsdDsgTiAmbGU7IDEwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWM3NTggXHVhYzFjXHVjMjE4IEpcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEogJmxlOyAyMCkgXHViMmU0XHVjNzRjIEpcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YWNmY1x1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwIFx1YzBhY1x1YWNmY1x1Yjk3YyBcdWIyZjRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKQUJVS0UiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyByZWNlbnRseSBkaXNjb3ZlcmVkIGFuIG9sZCB2aWRlbyBnYW1lLiBUaGUgc2NyZWVuIG9mIHRoaXMgZ2FtZSBpcyBkaXZpZGVkIGludG8gTiBjb2x1bW5zLiBBdCB0aGUgYm90dG9tIG9mIHRoZSBzY3JlZW4sIHRoZXJlIGlzIGFuIE0tY29sdW1ucy13aWRlIGJvYXQgKE0gJmx0OyBOKS4gVGhlIHBsYXllciBjYW4gbW92ZSB0aGlzIGJvYXQgbGVmdCBvciByaWdodCBkdXJpbmcgdGhlIGdhbWUsIGJ1dCB0aGUgYm9hdCBtdXN0IHJlbWFpbiBjb21wbGV0ZWx5IHdpdGhpbiB0aGUgc2NyZWVuIGF0IGFsbCB0aW1lcy4gVGhlIGJvYXQgaW5pdGlhbGx5IG9jY3VwaWVzIHRoZSBsZWZ0bW9zdCBNIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFwcGxlcyBhcmUgYmVpbmcgZHJvcHBlZCBmcm9tIHRoZSB0b3Agb2YgdGhlIHNjcmVlbi4gRWFjaCBhcHBsZSBzdGFydHMgaXRzIGZhbGwgYXQgdGhlIHRvcCBvZiBvbmUgb2YgdGhlIE4gY29sdW1ucywgZmFsbGluZyBzdHJhaWdodCBkb3duIHVudGlsIGl0IHJlYWNoZXMgdGhlIGJvdHRvbSBvZiB0aGUgc2NyZWVuLiBUaGUgbmV4dCBhcHBsZSBzdGFydHMgaXRzIGZhbGwganVzdCBhZnRlciB0aGUgY3VycmVudCBvbmUgaGFzIHJlYWNoZWQgdGhlIGJvdHRvbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW4gYXBwbGUgaXMgc2FpZCB0byBiZSBwaWNrZWQgdXAgaWYgdGhlIGJvYXQgaXMgcGxhY2VkIHNvIHRoYXQgaXQgb2NjdXBpZXMgdGhlIGNvbHVtbiBkb3duIHdoaWNoIHRoZSBhcHBsZSBpcyBmYWxsaW5nIHdoZW4gaXQgcmVhY2hlcyB0aGUgYm90dG9tLiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBpcyB0byBwaWNrIHVwIGFsbCBvZiB0aGUgYXBwbGVzLCBpbiBhIHdheSB0aGF0IG1pbmltaXplcyB0aGUgZGlzdGFuY2UgdGhhdCB0aGUgYm9hdCBtdXN0IHRyYXZlbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE0gJmx0OyBOICZsZTsgMTApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBKICgxICZsZTsgSiAmbGU7IDIwKSwgdGhlIG51bWJlciBvZiBmYWxsaW5nIGFwcGxlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBKIGxpbmVzIGNvbnRhaW4gdGhlIGNvbHVtbiBwb3NpdGlvbnMgb2YgdGhvc2UgYXBwbGVzLCBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSB3aWxsIGZhbGwuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbWFsIGRpc3RhbmNlIHRoYXQgdGhlIGJvYXQgbXVzdCB0cmF2ZWwgaW4gb3JkZXIgdG8gcGljayB1cCBhbGwgdGhlIGFwcGxlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #1 1번