시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB3881249131.707%

문제

IOI 2015 개막식이 거의 끝나가고 있다. 개막식이 진행되는 동안, 각 팀은 주최측으로부터 선물상자를 받게 되어 있다. 그러나 모든 자원봉사자들이 개막식에 너무 집중하는 바람에, 선물에 대해서는 완전히 잊고 있었다. 선물을 줘야 한다는 것을 기억하는 사람은 아만 뿐이다. 아만은 열정적인 자원봉사자이며, IOI가 완벽하게 진행되었으면 하는 바램으로 모든 선물을 최소의 시간에 전달하고자 한다.

개막식이 진행되는 곳은 L개의 동일한 구역으로 나뉘어진 원 모양이다. 각 구역은 차례로 0부터 L-1까지 번호가 매겨져 있다. 즉, 0 ≤ i ≤ L-2일 때, 구역 i와 구역 i+1는 서로 인접해 있고, 구역 0과 구역 L-1도 서로 인접해 있다. 개막식에 온 팀들은 모두 N개 팀이다. 각 팀은 이 구역들 중 하나에 앉아 있다. 각 구역에는 임의의 수의 팀들이 있을 수 있다. 어떤 구역에는 팀이 전혀 없을 수도 있다.

선물은 모두 동일하며, 총 N개가 있다. 처음에, 아만과 모든 선물은 구역 0에 있다. 아만은 각 팀에게 선물을 하나씩 주어야 하며, 선물을 다 나눠준 다음에는 구역 0으로 돌아와야 한다. 구역 0에도 팀들이 있을 수 있음에 주의하자.

어떤 순간에도, 아만은 최대 K개의 선물들만을 들 수 있다. 아만은 구역 0에서 선물을 들어야 하고, 드는데는 시간이 들지 않는다. 각각의 선물은 팀에게 전달될 때까지 아만이 들고 있어야 한다. 아만이 하나 이상의 선물을 들고 있고, 아직 선물을 받지 않은 팀(들)이 있는 구역에 도착하면, 아만은 들고 있는 선물을 팀(들)에게 줄 수 있다. 선물을 주는데도 시간이 들지 않는다. 시간이 드는 것은 단지 이동 뿐이다. 아만은 원형인 개막식장에서 양 방향으로 움직일 수 있다. 인접한 구역간을 이동하는데 (시계방향이든 반시계방향이든) 정확히 1초가 걸리며, 선물을 몇 개 들고 있는지와는 관계가 없다.

아만이 모든 선물을 전달하고, 처음 위치로 돌아오는데 필요한 최소의 시간을 구하시오.

이 예제에서 N = 3팀이 있고, 아만은 동시에 최대 K = 2개의 선물을 들 수 있으며, 구역의 수는 L = 8이다. 팀들은 구역 1, 2, 5에 있다.

최적의 해 중 하나가 위 그림에 나와 있다. 처음에 아만은 선물 두 개를 들고, 이를 구역 2에 있는 팀에게 하나를 전달하고, 나머지 하나를 구역 5에 있는 팀에게 준 뒤 구역 0으로 돌아온다. 이 과정은 8초가 걸린다. 다음에 아만은 남은 선물 하나를 구역 1에 있는 팀에게 주고 다시 구역 0으로 돌아온다. 이 과정은 2초가 걸린다. 따라서, 전체 시간은 10초이다.

N, K, L과 모든 팀들의 위치가 주어진다. 아만이 모든 선물을 전달하고 구역 으로 돌아오는데 걸리는 시간의 최솟값을 구하시오.

이를 위하여 delivery 함수를 구현해야 한다:

  • delivery(N, K, L, positions)
    • N: 팀의 수
    • K: 아만이 한 번에 들 수 있는 선물의 최대 개수
    • L: 개막식장의 구역 수
    • positions: 길이 N인 배열. positions[0], ..., positions[N-1]에 각 팀이 있는 구역 번호가 주어진다. positions의 성분들은 감소하지 않는 순서로 주어진다.

이 함수의 리턴값은 아만이 임무를 완수하는데 최소 몇 초가 필요한지이다.

입력

첫째 줄에 N, K, L이 주어진다.

둘째 줄에는 positions[0], ..., positions[N-1]이 주어진다.

출력

delivery(N, K, L, positions)의 리턴값을 출력한다.

서브태스크

번호 배점 제한
1 10

1 ≤ N ≤ 1,000, K = 1, 1 ≤ L ≤ 109

2 10

1 ≤ N ≤ 1,000, K = N, 1 ≤ L ≤ 109

3 15

1 ≤ N ≤ 10, 1 ≤ K ≤ N, 1 ≤ L ≤ 109

4 15

1 ≤ N ≤ 1,000, 1 ≤ K ≤ N, 1 ≤ L ≤ 109

5 20

1 ≤ N ≤ 106, 1 ≤ K ≤ 3,000, 1 ≤ L ≤ 109

6 30

1 ≤ N ≤ 107, 1 ≤ K ≤ N, 1 ≤ L ≤ 109

예제 입력 1

3 2 8
1 2 5

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjEwOTE5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTIwXHViYjNjXHVjMGMxXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5JT0kgMjAxNSBcdWFjMWNcdWI5YzlcdWMyZGRcdWM3NzQgXHVhYzcwXHVjNzU4IFx1YjA1ZFx1YjA5OFx1YWMwMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWMxY1x1YjljOVx1YzJkZFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHViM2Q5XHVjNTQ4LCBcdWFjMDEgXHVkMzAwXHVjNzQwIFx1YzhmY1x1Y2Q1Y1x1Y2UyMVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWMxMjBcdWJiM2NcdWMwYzFcdWM3OTBcdWI5N2MgXHViYzFiXHVhYzhjIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWJhYThcdWI0ZTAgXHVjNzkwXHVjNmQwXHViZDA5XHVjMGFjXHVjNzkwXHViNGU0XHVjNzc0IFx1YWMxY1x1YjljOVx1YzJkZFx1YzVkMCBcdWIxMDhcdWJiMzQgXHVjOWQxXHVjOTExXHVkNTU4XHViMjk0IFx1YmMxNFx1Yjc4Y1x1YzVkMCwgXHVjMTIwXHViYjNjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM2NDRcdWM4MDRcdWQ3ODggXHVjNzhhXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzkxOFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWUzMFx1YzViNVx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNTQ0XHViOWNjIFx1YmZkMFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViOWNjXHVjNzQwIFx1YzVmNFx1YzgxNVx1YzgwMVx1Yzc3OCBcdWM3OTBcdWM2ZDBcdWJkMDlcdWMwYWNcdWM3OTBcdWM3NzRcdWJhNzAsIElPSVx1YWMwMCBcdWM2NDRcdWJjYmRcdWQ1NThcdWFjOGMgXHVjOWM0XHVkNTg5XHViNDE4XHVjNWM4XHVjNzNjXHViYTc0IFx1ZDU1OFx1YjI5NCBcdWJjMTRcdWI3YThcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMmRjXHVhYzA0XHVjNWQwIFx1YzgwNFx1YjJlY1x1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxY1x1YjljOVx1YzJkZFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHVhY2YzXHVjNzQwIExcdWFjMWNcdWM3NTggXHViM2Q5XHVjNzdjXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjRcdWM5YzQgXHVjNmQwIFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YWQ2Y1x1YzVlZFx1Yzc0MCBcdWNjMjhcdWI4NDBcdWI4NWMgMFx1YmQ4MFx1ZDEzMCBMLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgMCAmbGU7IGkgJmxlOyBMLTJcdWM3N2MgXHViNTRjLCBcdWFkNmNcdWM1ZWQgaVx1YzY0MCBcdWFkNmNcdWM1ZWQgaSsxXHViMjk0IFx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHVhY2UwLCBcdWFkNmNcdWM1ZWQgMFx1YWNmYyBcdWFkNmNcdWM1ZWQgTC0xXHViM2M0IFx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMmU0LiBcdWFjMWNcdWI5YzlcdWMyZGRcdWM1ZDAgXHVjNjI4IFx1ZDMwMFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgTlx1YWMxYyBcdWQzMDBcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQzMDBcdWM3NDAgXHVjNzc0IFx1YWQ2Y1x1YzVlZFx1YjRlNCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwIFx1YzU0OVx1YzU0NCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWQzMDBcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVkMzAwXHVjNzc0IFx1YzgwNFx1ZDYwMCBcdWM1YzZcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHViYjNjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIzZDlcdWM3N2NcdWQ1NThcdWJhNzAsIFx1Y2QxZCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwLCBcdWM1NDRcdWI5Y2NcdWFjZmMgXHViYWE4XHViNGUwIFx1YzEyMFx1YmIzY1x1Yzc0MCBcdWFkNmNcdWM1ZWQgMFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWFjMDEgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YjJlNCBcdWIwOThcdWIyMjBcdWM5MDAgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1YWQ2Y1x1YzVlZCAwXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWQ2Y1x1YzVlZCAwXHVjNWQwXHViM2M0IFx1ZDMwMFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0Y1x1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWMyMWNcdWFjMDRcdWM1ZDBcdWIzYzQsIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWNkNWNcdWIzMDAgS1x1YWMxY1x1Yzc1OCBcdWMxMjBcdWJiM2NcdWI0ZTRcdWI5Y2NcdWM3NDQgXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWFkNmNcdWM1ZWQgMFx1YzVkMFx1YzExYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViNGRjXHViMjk0XHViMzcwXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMTIwXHViYjNjXHVjNzQwIFx1ZDMwMFx1YzVkMFx1YWM4YyBcdWM4MDRcdWIyZWNcdWI0MjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YzU0NFx1YjljY1x1Yzc3NCBcdWI0ZTRcdWFjZTAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViOWNjXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjMTIwXHViYjNjXHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1YzljMSBcdWMxMjBcdWJiM2NcdWM3NDQgXHViYzFiXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQzMDAoXHViNGU0KVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3NCwgXHVjNTQ0XHViOWNjXHVjNzQwIFx1YjRlNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzQ0IFx1ZDMwMChcdWI0ZTQpXHVjNWQwXHVhYzhjIFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMxMjBcdWJiM2NcdWM3NDQgXHVjOGZjXHViMjk0XHViMzcwXHViM2M0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWMyZGNcdWFjMDRcdWM3NzQgXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWIyZThcdWM5YzAgXHVjNzc0XHViM2Q5IFx1YmZkMFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViOWNjXHVjNzQwIFx1YzZkMFx1ZDYxNVx1Yzc3OCBcdWFjMWNcdWI5YzlcdWMyZGRcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjNTkxIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc4XHVjODExXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YWMwNFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgKFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjRlMCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3NzRcdWI0ZTApIFx1YzgxNVx1ZDY1NVx1ZDc4OCAxXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjlhY1x1YmE3MCwgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YmE4NyBcdWFjMWMgXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjI5NFx1YzljMFx1YzY0MFx1YjI5NCBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI5Y2NcdWM3NzQgXHViYWE4XHViNGUwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM4MDRcdWIyZWNcdWQ1NThcdWFjZTAsIFx1Y2M5OFx1Yzc0YyBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBOID0gM1x1ZDMwMFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjZDVjXHViMzAwIEsgPSAyXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YzIxOFx1YjI5NCBMID0gOFx1Yzc3NFx1YjJlNC4gXHVkMzAwXHViNGU0XHVjNzQwIFx1YWQ2Y1x1YzVlZCAxLCAyLCA1XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEwOTE5XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwNXB4OyB3aWR0aDo2NTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWM4MDFcdWM3NTggXHVkNTc0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWFjMDAgXHVjNzA0IFx1YWRmOFx1YjliY1x1YzVkMCBcdWIwOThcdWM2NDAgXHVjNzg4XHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDAgXHVjNTQ0XHViOWNjXHVjNzQwIFx1YzEyMFx1YmIzYyBcdWI0NTAgXHVhYzFjXHViOTdjIFx1YjRlNFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1YWQ2Y1x1YzVlZCAyXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMDBcdWM1ZDBcdWFjOGMgXHVkNTU4XHViMDk4XHViOTdjIFx1YzgwNFx1YjJlY1x1ZDU1OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFkNmNcdWM1ZWQgNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YzkwMCBcdWI0YTQgXHVhZDZjXHVjNWVkIDBcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhY2ZjXHVjODE1XHVjNzQwIDhcdWNkMDhcdWFjMDAgXHVhYzc4XHViOWIwXHViMmU0LiBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjNTQ0XHViOWNjXHVjNzQwIFx1YjBhOFx1Yzc0MCBcdWMxMjBcdWJiM2MgXHVkNTU4XHViMDk4XHViOTdjIFx1YWQ2Y1x1YzVlZCAxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMDBcdWM1ZDBcdWFjOGMgXHVjOGZjXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWFkNmNcdWM1ZWQgMFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjhcdWIyZTQuIFx1Yzc3NCBcdWFjZmNcdWM4MTVcdWM3NDAgMlx1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjODA0XHVjY2I0IFx1YzJkY1x1YWMwNFx1Yzc0MCAxMFx1Y2QwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+TiwgSywgTFx1YWNmYyBcdWJhYThcdWI0ZTAgXHVkMzAwXHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzU0NFx1YjljY1x1Yzc3NCBcdWJhYThcdWI0ZTAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzgwNFx1YjJlY1x1ZDU1OFx1YWNlMCBcdWFkNmNcdWM1ZWQgXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NThcdWM1ZWMgPGNvZGU+ZGVsaXZlcnk8XC9jb2RlPiBcdWQ1NjhcdWMyMThcdWI5N2MgXHVhZDZjXHVkNjA0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT5kZWxpdmVyeShOLCBLLCBMLCBwb3NpdGlvbnMpPFwvY29kZT5cclxuXHJcblx0PHVsPlxyXG5cdFx0PGxpPjxjb2RlPk48XC9jb2RlPjogXHVkMzAwXHVjNzU4IFx1YzIxODxcL2xpPlxyXG5cdFx0PGxpPjxjb2RlPks8XC9jb2RlPjogXHVjNTQ0XHViOWNjXHVjNzc0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMTg8XC9saT5cclxuXHRcdDxsaT48Y29kZT5MPFwvY29kZT46IFx1YWMxY1x1YjljOVx1YzJkZFx1YzdhNVx1Yzc1OCBcdWFkNmNcdWM1ZWQgXHVjMjE4PFwvbGk+XHJcblx0XHQ8bGk+PGNvZGU+cG9zaXRpb25zPFwvY29kZT46IFx1YWUzOFx1Yzc3NCBOXHVjNzc4IFx1YmMzMFx1YzVmNC4gPGNvZGU+cG9zaXRpb25zWzBdPFwvY29kZT4sIC4uLiwgPGNvZGU+cG9zaXRpb25zW04tMV08XC9jb2RlPlx1YzVkMCBcdWFjMDEgXHVkMzAwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM1ZWQgXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gPGNvZGU+cG9zaXRpb25zPFwvY29kZT5cdWM3NTggXHVjMTMxXHViZDg0XHViNGU0XHVjNzQwIFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzQgXHVkNTY4XHVjMjE4XHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0MCBcdWM1NDRcdWI5Y2NcdWM3NzQgXHVjNzg0XHViYjM0XHViOTdjIFx1YzY0NFx1YzIxOFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1Y2QwOFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NWNcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDxjb2RlPk48XC9jb2RlPiwgPGNvZGU+SzxcL2NvZGU+LCA8Y29kZT5MPFwvY29kZT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7PGNvZGU+cG9zaXRpb25zWzBdPFwvY29kZT4sIC4uLiwmbmJzcDs8Y29kZT5wb3NpdGlvbnNbTi0xXTxcL2NvZGU+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD48Y29kZT5kZWxpdmVyeShOLCBLLCBMLCBwb3NpdGlvbnMpPFwvY29kZT5cdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzdWJ0YXNrMSI6IjxwPjEgJmxlOyBOICZsZTsgMSwwMDAsIEsgPSAxLCAxICZsZTsgTCAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+MSAmbGU7IE4gJmxlOyAxLDAwMCwgSyA9IE4sIDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4xICZsZTsgTiAmbGU7IDEwLCAxICZsZTsgSyAmbGU7IE4sIDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvcD5cclxuIiwic3VidGFzazQiOiI8cD4xICZsZTsgTiAmbGU7IDEsMDAwLCAxICZsZTsgSyAmbGU7IE4sIDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvcD5cclxuIiwic3VidGFzazUiOiI8cD4xICZsZTsgTiAmbGU7IDEwPHN1cD42PFwvc3VwPiwgMSAmbGU7IEsgJmxlOyAzLDAwMCwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4iLCJzdWJ0YXNrNiI6IjxwPjEgJmxlOyBOICZsZTsgMTA8c3VwPjc8XC9zdXA+LCAxICZsZTsgSyAmbGU7IE4sIDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTA5MTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCb3hlcyB3aXRoIHNvdXZlbmlycyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGxhc3QgYWN0IG9mIHRoZSBJT0kgMjAxNSBvcGVuaW5nIGNlcmVtb255IGlzIGluIHByb2dyZXNzLiBEdXJpbmcgdGhlIG9wZW5pbmcgY2VyZW1vbnksIGVhY2ggdGVhbSB3YXMgc3VwcG9zZWQgdG8gcmVjZWl2ZSBhIGJveCB3aXRoIGEgc291dmVuaXIgZnJvbSB0aGUgaG9zdC4gSG93ZXZlciwgYWxsIHZvbHVudGVlcnMgYXJlIHNvIGZhc2NpbmF0ZWQgYnkgdGhlIGNlcmVtb255IHRoYXQgdGhleSBjb21wbGV0ZWx5IGZvcmdvdCBhYm91dCB0aGUgc291dmVuaXJzLiBUaGUgb25seSBwZXJzb24gd2hvIHJlbWVtYmVycyBhYm91dCB0aGUgc291dmVuaXJzIGlzIEFtYW4uIEhlIGlzIGFuIGVudGh1c2lhc3RpYyB2b2x1bnRlZXIgYW5kIGhlIHdhbnRzIHRoZSBJT0kgdG8gYmUgcGVyZmVjdCwgc28gaGUgd2FudHMgdG8gZGVsaXZlciBhbGwgdGhlIHNvdXZlbmlycyBpbiB0aGUgbGVhc3QgYW1vdW50IG9mIHRpbWUuPFwvcD5cclxuXHJcbjxwPlRoZSB2ZW51ZSBvZiB0aGUgb3BlbmluZyBjZXJlbW9ueSBpcyBhIGNpcmNsZSBkaXZpZGVkIGludG8gTCBpZGVudGljYWwgc2VjdGlvbnMuIFRoZSBzZWN0aW9ucyBhcm91bmQgdGhlIGNpcmNsZSBhcmUgbnVtYmVyZWQgY29uc2VjdXRpdmVseSBmcm9tIDAgdG8gTC0xLiBUaGF0IGlzLCBmb3IgMCAmbGU7IGkgJmxlOyBMLTIsIHNlY3Rpb25zIGkgYW5kIGkrMSBhcmUgYWRqYWNlbnQsIGFuZCBhbHNvIHNlY3Rpb25zIDAgYW5kIEwtMSBhcmUgYWRqYWNlbnQuIFRoZXJlIGFyZSBOIHRlYW1zIGF0IHRoZSB2ZW51ZS4gRWFjaCB0ZWFtIGlzIHNpdHRpbmcgaW4gb25lIG9mIHRoZSBzZWN0aW9ucy4gRWFjaCBzZWN0aW9uIG1heSBjb250YWluIGFyYml0cmFyaWx5IG1hbnkgdGVhbXMuIFNvbWUgc2VjdGlvbnMgbWF5IGV2ZW4gYmUgZW1wdHkuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIGlkZW50aWNhbCBzb3V2ZW5pcnMuIEluaXRpYWxseSwgYm90aCBBbWFuIGFuZCBhbGwgb2YgdGhlIHNvdXZlbmlycyBhcmUgaW4gc2VjdGlvbiAwLiBBbWFuIHNob3VsZCBnaXZlIG9uZSBzb3V2ZW5pciB0byBlYWNoIHRlYW0sIGFuZCBhZnRlciBkZWxpdmVyaW5nIHRoZSBsYXN0IHNvdXZlbmlyIGhlIG11c3QgcmV0dXJuIHRvIHNlY3Rpb24gMC4gTm90ZSB0aGF0IHNvbWUgdGVhbXMgbWF5IGJlIHNpdHRpbmcgaW4gc2VjdGlvbiAwLjxcL3A+XHJcblxyXG48cD5BdCBhbnkgbW9tZW50LCBBbWFuIGNhbiBvbmx5IGNhcnJ5IGF0IG1vc3QgSyBzb3V2ZW5pcnMuIEFtYW4gbXVzdCBwaWNrIHVwIHNvdXZlbmlycyBpbiBzZWN0aW9uIDAsIGFuZCB0aGlzIHRha2VzIGhpbSBubyB0aW1lLiBFYWNoIHNvdXZlbmlyIG11c3QgYmUgY2FycmllZCB1bnRpbCBpdCBpcyBkZWxpdmVyZWQgdG8gb25lIG9mIHRoZSB0ZWFtcy4gV2hlbmV2ZXIgQW1hbiBjYXJyaWVzIG9uZSBvciBtb3JlIHNvdXZlbmlycyBhbmQgcmVhY2hlcyBhIHNlY3Rpb24gd2l0aCBhIHRlYW0gdGhhdCBoYXMgbm90IHJlY2VpdmVkIGEgc291dmVuaXIgeWV0LCBoZSBtYXkgZ2l2ZSB0aGF0IHRlYW0gb25lIG9mIHRoZSBzb3V2ZW5pcnMgaGUgY2Fycmllcy4gVGhpcyBhbHNvIGhhcHBlbnMgaW5zdGFudGx5LiBUaGUgb25seSB0aGluZyB0aGF0IHRha2VzIHRpbWUgaXMgbW92ZW1lbnQuIEFtYW4gY2FuIG1vdmUgYXJvdW5kIHRoZSBjaXJjdWxhciB2ZW51ZSBpbiBib3RoIGRpcmVjdGlvbnMuIE1vdmluZyB0byBhbiBhZGphY2VudCBzZWN0aW9uIChlaXRoZXIgY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2UpIHRha2VzIGhpbSBleGFjdGx5IG9uZSBzZWNvbmQsIHJlZ2FyZGxlc3Mgb2YgaG93IG1hbnkgc291dmVuaXJzIGhlIGNhcnJpZXMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Ygc2Vjb25kcyBBbWFuIG5lZWRzIHRvIGRlbGl2ZXIgYWxsIHNvdXZlbmlycyBhbmQgdGhlbiByZXR1cm4gdG8gaGlzIGluaXRpYWwgcG9zaXRpb24uPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgZXhhbXBsZSB3ZSBoYXZlIE4gPSAzIHRlYW1zLCBBbWFuJnJzcXVvO3MgY2FycnlpbmcgY2FwYWNpdHkgaXMgSyA9IDIsIGFuZCB0aGUgbnVtYmVyIG9mIHNlY3Rpb25zIGlzIEwgPSA4LiBUaGUgdGVhbXMgYXJlIGxvY2F0ZWQgaW4gc2VjdGlvbnMgMSwgMiwgYW5kIDUuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEwOTE5XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwNXB4OyB3aWR0aDo2NTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5PbmUgb2YgdGhlIG9wdGltYWwgc29sdXRpb25zIGlzIHNob3duIGluIHRoZSBwaWN0dXJlIGFib3ZlLiBJbiBoaXMgZmlyc3QgdHJpcCBBbWFuIHRha2VzIHR3byBzb3V2ZW5pcnMsIGRlbGl2ZXJzIG9uZSB0byB0aGUgdGVhbSBpbiBzZWN0aW9uIDIsIHRoZW4gdGhlIG90aGVyIHRvIHRoZSB0ZWFtIGluIHNlY3Rpb24gNSwgYW5kIGZpbmFsbHkgaGUgcmV0dXJucyB0byBzZWN0aW9uIDAuIFRoaXMgdHJpcCB0YWtlcyA4IHNlY29uZHMuIEluIGhpcyBzZWNvbmQgdHJpcCBBbWFuIGJyaW5ncyB0aGUgcmVtYWluaW5nIHNvdXZlbmlyIHRvIHRoZSB0ZWFtIGluIHNlY3Rpb24gMSBhbmQgdGhlbiByZXR1cm5zIHRvIHNlY3Rpb24gMC4gSGUgbmVlZHMgYW5vdGhlciAyIHNlY29uZHMgdG8gZG8gdGhpcy4gVGh1cywgdGhlIHRvdGFsIHRpbWUgaXMgMTAgc2Vjb25kcy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBOLCBLLCBMLCBhbmQgdGhlIHBvc2l0aW9ucyBvZiBhbGwgdGVhbXMuIENvbXB1dGUgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBzZWNvbmRzIEFtYW4gbmVlZHMgdG8gZGVsaXZlciBhbGwgdGhlIHNvdXZlbmlycyBhbmQgdG8gcmV0dXJuIHRvIHNlY3Rpb24gMC4gWW91IG5lZWQgdG8gaW1wbGVtZW50IHRoZSBmdW5jdGlvbiA8Y29kZT5kZWxpdmVyeTxcL2NvZGU+OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPmRlbGl2ZXJ5KE4sIEssIEwsIHBvc2l0aW9ucyk8XC9jb2RlPiAmbWRhc2g7IFRoaXMgZnVuY3Rpb24gd2lsbCBiZSBjYWxsZWQgYnkgdGhlIGdyYWRlciBleGFjdGx5IG9uY2UuXHJcblxyXG5cdDx1bD5cclxuXHRcdDxsaT48Y29kZT5OPFwvY29kZT46IHRoZSBudW1iZXIgb2YgdGVhbXMuPFwvbGk+XHJcblx0XHQ8bGk+PGNvZGU+SzxcL2NvZGU+OiB0aGUgbWF4aW11bSBudW1iZXIgb2Ygc291dmVuaXJzIEFtYW4gY2FuIGNhcnJ5IGF0IHRoZSBzYW1lIHRpbWUuPFwvbGk+XHJcblx0XHQ8bGk+PGNvZGU+TDxcL2NvZGU+OiB0aGUgbnVtYmVyIG9mIHNlY3Rpb25zIGluIHRoZSB2ZW51ZSBvZiB0aGUgb3BlbmluZyBjZXJlbW9ueS48XC9saT5cclxuXHRcdDxsaT48Y29kZT5wb3NpdGlvbnM8XC9jb2RlPjogYW4gYXJyYXkgb2YgbGVuZ3RoIE4uIDxjb2RlPnBvc2l0aW9uc1swXTxcL2NvZGU+LCAuLi4sIDxjb2RlPnBvc2l0aW9uc1tOLTFdPFwvY29kZT4gZ2l2ZSB0aGUgc2VjdGlvbiBudW1iZXIgb2YgYWxsIHRlYW1zLiBUaGUgZWxlbWVudHMgb2YgcG9zaXRpb25zIGFyZSBpbiBub24tZGVjcmVhc2luZyBvcmRlci48XC9saT5cclxuXHRcdDxsaT5UaGUgZnVuY3Rpb24gc2hvdWxkIHJldHVybiB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHNlY29uZHMgaW4gd2hpY2ggQW1hbiBjYW4gY29tcGxldGUgaGlzIHRhc2suPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+bGluZSAxOiA8Y29kZT5OPFwvY29kZT4gPGNvZGU+SzxcL2NvZGU+IDxjb2RlPkw8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5saW5lIDI6IDxjb2RlPnBvc2l0aW9uc1swXTxcL2NvZGU+ICZoZWxsaXA7IDxjb2RlPnBvc2l0aW9uc1tOLTFdPFwvY29kZT48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50cyB0aGUgcmV0dXJuIHZhbHVlIG9mIDxjb2RlPmRlbGl2ZXJ5PFwvY29kZT4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInN1YnRhc2sxIjoiPHA+MSAmbGU7IE4gJmxlOyAxLDAwMCwgSyA9IDEsIDEgJmxlOyBMICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4xICZsZTsgTiAmbGU7IDEsMDAwLCBLID0gTiwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPjEgJmxlOyBOICZsZTsgMTAsIDEgJmxlOyBLICZsZTsgTiwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPjEgJmxlOyBOICZsZTsgMSwwMDAsIDEgJmxlOyBLICZsZTsgTiwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4iLCJzdWJ0YXNrNSI6IjxwPjEgJmxlOyBOICZsZTsgMTA8c3VwPjY8XC9zdXA+LCAxICZsZTsgSyAmbGU7IDMsMDAwLCAxICZsZTsgTCAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL3A+XHJcbiIsInN1YnRhc2s2IjoiPHA+MSAmbGU7IE4gJmxlOyAxMDxzdXA+NzxcL3N1cD4sIDEgJmxlOyBLICZsZTsgTiwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4ifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2015 > Day 1 1번

  • 데이터를 추가한 사람: cgiosy
  • 문제의 오타를 찾은 사람: ntopia

채점 및 기타 정보

  • 예제는 채점하지 않는다.