시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 543 296 258 55.365%

문제

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 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
W3sicHJvYmxlbV9pZCI6IjI4MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWFjZmMgXHViMmY0XHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzYyNFx1Yjc3ZFx1YzJlNFx1YzVkMFx1YzExYyBcdWJjMTRcdWFkNmNcdWIyYzhcdWI5N2MgXHVjNjJlXHVhZTMwXHViMjk0IFx1YzYyNFx1Yjc5OFx1YjQxYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWMyYTRcdWQwNmNcdWI5YjBcdWM3NDAgTlx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyYTRcdWQwNmNcdWI5YjBcdWM3NTggXHVjNTQ0XHViNzk4XHVjYWJkXHVjNWQwXHViMjk0IE1cdWNlNzhcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTU4XHViMjk0IFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YWMwMCBcdWM3ODhcdWIyZTQuIChNJmx0O04pIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViMjk0IFx1YzkxMVx1YzVkMCBcdWJjMTRcdWFkNmNcdWIyYzhcdWI5N2MgXHVjNjdjXHVjYWJkXHVjNzc0XHViMDk4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJjMTRcdWFkNmNcdWIyYzhcdWIyOTQgXHVjMmE0XHVkMDZjXHViOWIwXHVjNzU4IFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YjI5NCBcdWM2N2NcdWNhYmQgTVx1Y2U3OFx1Yzc0NCBcdWNjMjhcdWM5YzBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYTRcdWQwNmNcdWI5YjBcdWM3NTggXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzBhY1x1YWNmYyBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVhYzAwIFx1YjVhOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzBhY1x1YWNmY1x1YjI5NCBOXHVjZTc4XHVjOTExIFx1ZDU1YyBcdWNlNzhcdWM3NTggXHVjMGMxXHViMmU4XHVjNWQwXHVjMTFjIFx1YjVhOFx1YzViNFx1YzljMFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzAsIFx1YzJhNFx1ZDA2Y1x1YjliMFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHViMmZmXHVjNzQ0XHViNTRjXHVhZTRjXHVjOWMwIFx1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU1YyBcdWMwYWNcdWFjZmNcdWFjMDAgXHViYzE0XHViMmU1XHVjNWQwIFx1YjJmZlx1YjI5NCBcdWM5ODlcdWMyZGMsIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWFjZmNcdWFjMDAgXHViNWE4XHVjNWI0XHVjOWMwXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzE0XHVhZDZjXHViMmM4XHVhYzAwIFx1YzBhY1x1YWNmY1x1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1Y2MyOFx1YzljMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YjI5NCBcdWFkZjggXHVjMGFjXHVhY2ZjXHVhYzAwIFx1YmMxNFx1YjJlNVx1YzVkMCBcdWIyZmZcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWFjZmNcdWI5N2MgXHViMmY0XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwYWNcdWFjZmNcdWI5N2MgXHViYWE4XHViNDUwIFx1YjJmNFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmMxNFx1YWQ2Y1x1YjJjOFx1Yzc1OCBcdWM3NzRcdWIzZDkgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBNICZsdDsgTiAmbGU7IDEwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWM3NTggXHVhYzFjXHVjMjE4IEpcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEogJmxlOyAyMCkgXHViMmU0XHVjNzRjIEpcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YWNmY1x1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYWE4XHViNGUwIFx1YzBhY1x1YWNmY1x1Yjk3YyBcdWIyZjRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmMxNFx1YWQ2Y1x1YjJjOFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKQUJVS0UiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyByZWNlbnRseSBkaXNjb3ZlcmVkIGFuIG9sZCB2aWRlbyBnYW1lLiBUaGUgc2NyZWVuIG9mIHRoaXMgZ2FtZSBpcyBkaXZpZGVkIGludG8gTiBjb2x1bW5zLiBBdCB0aGUgYm90dG9tIG9mIHRoZSBzY3JlZW4sIHRoZXJlIGlzIGFuIE0tY29sdW1ucy13aWRlIGJvYXQgKE0gJmx0OyBOKS4gVGhlIHBsYXllciBjYW4gbW92ZSB0aGlzIGJvYXQgbGVmdCBvciByaWdodCBkdXJpbmcgdGhlIGdhbWUsIGJ1dCB0aGUgYm9hdCBtdXN0IHJlbWFpbiBjb21wbGV0ZWx5IHdpdGhpbiB0aGUgc2NyZWVuIGF0IGFsbCB0aW1lcy4gVGhlIGJvYXQgaW5pdGlhbGx5IG9jY3VwaWVzIHRoZSBsZWZ0bW9zdCBNIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFwcGxlcyBhcmUgYmVpbmcgZHJvcHBlZCBmcm9tIHRoZSB0b3Agb2YgdGhlIHNjcmVlbi4gRWFjaCBhcHBsZSBzdGFydHMgaXRzIGZhbGwgYXQgdGhlIHRvcCBvZiBvbmUgb2YgdGhlIE4gY29sdW1ucywgZmFsbGluZyBzdHJhaWdodCBkb3duIHVudGlsIGl0IHJlYWNoZXMgdGhlIGJvdHRvbSBvZiB0aGUgc2NyZWVuLiBUaGUgbmV4dCBhcHBsZSBzdGFydHMgaXRzIGZhbGwganVzdCBhZnRlciB0aGUgY3VycmVudCBvbmUgaGFzIHJlYWNoZWQgdGhlIGJvdHRvbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW4gYXBwbGUgaXMgc2FpZCB0byBiZSBwaWNrZWQgdXAgaWYgdGhlIGJvYXQgaXMgcGxhY2VkIHNvIHRoYXQgaXQgb2NjdXBpZXMgdGhlIGNvbHVtbiBkb3duIHdoaWNoIHRoZSBhcHBsZSBpcyBmYWxsaW5nIHdoZW4gaXQgcmVhY2hlcyB0aGUgYm90dG9tLiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBpcyB0byBwaWNrIHVwIGFsbCBvZiB0aGUgYXBwbGVzLCBpbiBhIHdheSB0aGF0IG1pbmltaXplcyB0aGUgZGlzdGFuY2UgdGhhdCB0aGUgYm9hdCBtdXN0IHRyYXZlbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMgTiBhbmQgTSAoMSAmbGU7IE0gJmx0OyBOICZsZTsgMTApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBKICgxICZsZTsgSiAmbGU7IDIwKSwgdGhlIG51bWJlciBvZiBmYWxsaW5nIGFwcGxlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBKIGxpbmVzIGNvbnRhaW4gdGhlIGNvbHVtbiBwb3NpdGlvbnMgb2YgdGhvc2UgYXBwbGVzLCBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSB3aWxsIGZhbGwuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbWFsIGRpc3RhbmNlIHRoYXQgdGhlIGJvYXQgbXVzdCB0cmF2ZWwgaW4gb3JkZXIgdG8gcGljayB1cCBhbGwgdGhlIGFwcGxlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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