시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 134 56 42 38.182%

문제

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]이 주어진다.

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

출력

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

예제 입력 1

3 2 8
1 2 5

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjEwOTE5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTIwXHViYjNjXHVjMGMxXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5JT0kgMjAxNSBcdWFjMWNcdWI5YzlcdWMyZGRcdWM3NzQgXHVhYzcwXHVjNzU4IFx1YjA1ZFx1YjA5OFx1YWMwMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWMxY1x1YjljOVx1YzJkZFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHViM2Q5XHVjNTQ4LCBcdWFjMDEgXHVkMzAwXHVjNzQwIFx1YzhmY1x1Y2Q1Y1x1Y2UyMVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWMxMjBcdWJiM2NcdWMwYzFcdWM3OTBcdWI5N2MgXHViYzFiXHVhYzhjIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWJhYThcdWI0ZTAgXHVjNzkwXHVjNmQwXHViZDA5XHVjMGFjXHVjNzkwXHViNGU0XHVjNzc0IFx1YWMxY1x1YjljOVx1YzJkZFx1YzVkMCBcdWIxMDhcdWJiMzQgXHVjOWQxXHVjOTExXHVkNTU4XHViMjk0IFx1YmMxNFx1Yjc4Y1x1YzVkMCwgXHVjMTIwXHViYjNjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM2NDRcdWM4MDRcdWQ3ODggXHVjNzhhXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzkxOFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWUzMFx1YzViNVx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNTQ0XHViOWNjIFx1YmZkMFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViOWNjXHVjNzQwIFx1YzVmNFx1YzgxNVx1YzgwMVx1Yzc3OCBcdWM3OTBcdWM2ZDBcdWJkMDlcdWMwYWNcdWM3OTBcdWM3NzRcdWJhNzAsIElPSVx1YWMwMCBcdWM2NDRcdWJjYmRcdWQ1NThcdWFjOGMgXHVjOWM0XHVkNTg5XHViNDE4XHVjNWM4XHVjNzNjXHViYTc0IFx1ZDU1OFx1YjI5NCBcdWJjMTRcdWI3YThcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMmRjXHVhYzA0XHVjNWQwIFx1YzgwNFx1YjJlY1x1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxY1x1YjljOVx1YzJkZFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHVhY2YzXHVjNzQwIExcdWFjMWNcdWM3NTggXHViM2Q5XHVjNzdjXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjRcdWM5YzQgXHVjNmQwIFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YWQ2Y1x1YzVlZFx1Yzc0MCBcdWNjMjhcdWI4NDBcdWI4NWMgMFx1YmQ4MFx1ZDEzMCBMLTFcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgMCAmbGU7IGkgJmxlOyBMLTJcdWM3N2MgXHViNTRjLCBcdWFkNmNcdWM1ZWQgaVx1YzY0MCBcdWFkNmNcdWM1ZWQgaSsxXHViMjk0IFx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHVhY2UwLCBcdWFkNmNcdWM1ZWQgMFx1YWNmYyBcdWFkNmNcdWM1ZWQgTC0xXHViM2M0IFx1YzExY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHViMmU0LiBcdWFjMWNcdWI5YzlcdWMyZGRcdWM1ZDAgXHVjNjI4IFx1ZDMwMFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgTlx1YWMxYyBcdWQzMDBcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQzMDBcdWM3NDAgXHVjNzc0IFx1YWQ2Y1x1YzVlZFx1YjRlNCBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNWQwIFx1YzU0OVx1YzU0NCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWQzMDBcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVkMzAwXHVjNzc0IFx1YzgwNFx1ZDYwMCBcdWM1YzZcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHViYjNjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIzZDlcdWM3N2NcdWQ1NThcdWJhNzAsIFx1Y2QxZCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwLCBcdWM1NDRcdWI5Y2NcdWFjZmMgXHViYWE4XHViNGUwIFx1YzEyMFx1YmIzY1x1Yzc0MCBcdWFkNmNcdWM1ZWQgMFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWFjMDEgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YjJlNCBcdWIwOThcdWIyMjBcdWM5MDAgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1YWQ2Y1x1YzVlZCAwXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWQ2Y1x1YzVlZCAwXHVjNWQwXHViM2M0IFx1ZDMwMFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0Y1x1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWMyMWNcdWFjMDRcdWM1ZDBcdWIzYzQsIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWNkNWNcdWIzMDAgS1x1YWMxY1x1Yzc1OCBcdWMxMjBcdWJiM2NcdWI0ZTRcdWI5Y2NcdWM3NDQgXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWFkNmNcdWM1ZWQgMFx1YzVkMFx1YzExYyBcdWMxMjBcdWJiM2NcdWM3NDQgXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViNGRjXHViMjk0XHViMzcwXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMTIwXHViYjNjXHVjNzQwIFx1ZDMwMFx1YzVkMFx1YWM4YyBcdWM4MDRcdWIyZWNcdWI0MjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YzU0NFx1YjljY1x1Yzc3NCBcdWI0ZTRcdWFjZTAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViOWNjXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjMTIwXHViYjNjXHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1YzljMSBcdWMxMjBcdWJiM2NcdWM3NDQgXHViYzFiXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQzMDAoXHViNGU0KVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjNWVkXHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3NCwgXHVjNTQ0XHViOWNjXHVjNzQwIFx1YjRlNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzQ0IFx1ZDMwMChcdWI0ZTQpXHVjNWQwXHVhYzhjIFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMxMjBcdWJiM2NcdWM3NDQgXHVjOGZjXHViMjk0XHViMzcwXHViM2M0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0ZTRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWMyZGNcdWFjMDRcdWM3NzQgXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWIyZThcdWM5YzAgXHVjNzc0XHViM2Q5IFx1YmZkMFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViOWNjXHVjNzQwIFx1YzZkMFx1ZDYxNVx1Yzc3OCBcdWFjMWNcdWI5YzlcdWMyZGRcdWM3YTVcdWM1ZDBcdWMxMWMgXHVjNTkxIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc4XHVjODExXHVkNTVjIFx1YWQ2Y1x1YzVlZFx1YWMwNFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgKFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1Yzc3NFx1YjRlMCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3NzRcdWI0ZTApIFx1YzgxNVx1ZDY1NVx1ZDc4OCAxXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjlhY1x1YmE3MCwgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YmE4NyBcdWFjMWMgXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjI5NFx1YzljMFx1YzY0MFx1YjI5NCBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI5Y2NcdWM3NzQgXHViYWE4XHViNGUwIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM4MDRcdWIyZWNcdWQ1NThcdWFjZTAsIFx1Y2M5OFx1Yzc0YyBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBOID0gM1x1ZDMwMFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1YjljY1x1Yzc0MCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjZDVjXHViMzAwIEsgPSAyXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YzIxOFx1YjI5NCBMID0gOFx1Yzc3NFx1YjJlNC4gXHVkMzAwXHViNGU0XHVjNzQwIFx1YWQ2Y1x1YzVlZCAxLCAyLCA1XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEwOTE5XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwNXB4OyB3aWR0aDo2NTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWM4MDFcdWM3NTggXHVkNTc0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWFjMDAgXHVjNzA0IFx1YWRmOFx1YjliY1x1YzVkMCBcdWIwOThcdWM2NDAgXHVjNzg4XHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDAgXHVjNTQ0XHViOWNjXHVjNzQwIFx1YzEyMFx1YmIzYyBcdWI0NTAgXHVhYzFjXHViOTdjIFx1YjRlNFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1YWQ2Y1x1YzVlZCAyXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMDBcdWM1ZDBcdWFjOGMgXHVkNTU4XHViMDk4XHViOTdjIFx1YzgwNFx1YjJlY1x1ZDU1OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFkNmNcdWM1ZWQgNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMzAwXHVjNWQwXHVhYzhjIFx1YzkwMCBcdWI0YTQgXHVhZDZjXHVjNWVkIDBcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhY2ZjXHVjODE1XHVjNzQwIDhcdWNkMDhcdWFjMDAgXHVhYzc4XHViOWIwXHViMmU0LiBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjNTQ0XHViOWNjXHVjNzQwIFx1YjBhOFx1Yzc0MCBcdWMxMjBcdWJiM2MgXHVkNTU4XHViMDk4XHViOTdjIFx1YWQ2Y1x1YzVlZCAxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMDBcdWM1ZDBcdWFjOGMgXHVjOGZjXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWFkNmNcdWM1ZWQgMFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjhcdWIyZTQuIFx1Yzc3NCBcdWFjZmNcdWM4MTVcdWM3NDAgMlx1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjODA0XHVjY2I0IFx1YzJkY1x1YWMwNFx1Yzc0MCAxMFx1Y2QwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+TiwgSywgTFx1YWNmYyBcdWJhYThcdWI0ZTAgXHVkMzAwXHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzU0NFx1YjljY1x1Yzc3NCBcdWJhYThcdWI0ZTAgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzgwNFx1YjJlY1x1ZDU1OFx1YWNlMCBcdWFkNmNcdWM1ZWQgXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NThcdWM1ZWMgPGNvZGU+ZGVsaXZlcnk8XC9jb2RlPiBcdWQ1NjhcdWMyMThcdWI5N2MgXHVhZDZjXHVkNjA0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT5kZWxpdmVyeShOLCBLLCBMLCBwb3NpdGlvbnMpPFwvY29kZT5cclxuXHJcblx0PHVsPlxyXG5cdFx0PGxpPjxjb2RlPk48XC9jb2RlPjogXHVkMzAwXHVjNzU4IFx1YzIxODxcL2xpPlxyXG5cdFx0PGxpPjxjb2RlPks8XC9jb2RlPjogXHVjNTQ0XHViOWNjXHVjNzc0IFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMTg8XC9saT5cclxuXHRcdDxsaT48Y29kZT5MPFwvY29kZT46IFx1YWMxY1x1YjljOVx1YzJkZFx1YzdhNVx1Yzc1OCBcdWFkNmNcdWM1ZWQgXHVjMjE4PFwvbGk+XHJcblx0XHQ8bGk+PGNvZGU+cG9zaXRpb25zPFwvY29kZT46IFx1YWUzOFx1Yzc3NCBOXHVjNzc4IFx1YmMzMFx1YzVmNC4gPGNvZGU+cG9zaXRpb25zWzBdPFwvY29kZT4sIC4uLiwgPGNvZGU+cG9zaXRpb25zW04tMV08XC9jb2RlPlx1YzVkMCBcdWFjMDEgXHVkMzAwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWM1ZWQgXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gPGNvZGU+cG9zaXRpb25zPFwvY29kZT5cdWM3NTggXHVjMTMxXHViZDg0XHViNGU0XHVjNzQwIFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzQgXHVkNTY4XHVjMjE4XHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0MCBcdWM1NDRcdWI5Y2NcdWM3NzQgXHVjNzg0XHViYjM0XHViOTdjIFx1YzY0NFx1YzIxOFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1Y2QwOFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NWNcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDxjb2RlPk48XC9jb2RlPiwgPGNvZGU+SzxcL2NvZGU+LCA8Y29kZT5MPFwvY29kZT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7PGNvZGU+cG9zaXRpb25zWzBdPFwvY29kZT4sIC4uLiwmbmJzcDs8Y29kZT5wb3NpdGlvbnNbTi0xXTxcL2NvZGU+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MSAmbGU7IE4gJmxlOyAxMDxzdXA+NzxcL3N1cD4sIDEgJmxlOyBLICZsZTsgTiwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD48Y29kZT5kZWxpdmVyeShOLCBLLCBMLCBwb3NpdGlvbnMpPFwvY29kZT5cdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDkxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJveGVzIHdpdGggc291dmVuaXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbGFzdCBhY3Qgb2YgdGhlIElPSSAyMDE1IG9wZW5pbmcgY2VyZW1vbnkgaXMgaW4gcHJvZ3Jlc3MuIER1cmluZyB0aGUgb3BlbmluZyBjZXJlbW9ueSwgZWFjaCB0ZWFtIHdhcyBzdXBwb3NlZCB0byByZWNlaXZlIGEgYm94IHdpdGggYSBzb3V2ZW5pciBmcm9tIHRoZSBob3N0LiBIb3dldmVyLCBhbGwgdm9sdW50ZWVycyBhcmUgc28gZmFzY2luYXRlZCBieSB0aGUgY2VyZW1vbnkgdGhhdCB0aGV5IGNvbXBsZXRlbHkgZm9yZ290IGFib3V0IHRoZSBzb3V2ZW5pcnMuIFRoZSBvbmx5IHBlcnNvbiB3aG8gcmVtZW1iZXJzIGFib3V0IHRoZSBzb3V2ZW5pcnMgaXMgQW1hbi4gSGUgaXMgYW4gZW50aHVzaWFzdGljIHZvbHVudGVlciBhbmQgaGUgd2FudHMgdGhlIElPSSB0byBiZSBwZXJmZWN0LCBzbyBoZSB3YW50cyB0byBkZWxpdmVyIGFsbCB0aGUgc291dmVuaXJzIGluIHRoZSBsZWFzdCBhbW91bnQgb2YgdGltZS48XC9wPlxyXG5cclxuPHA+VGhlIHZlbnVlIG9mIHRoZSBvcGVuaW5nIGNlcmVtb255IGlzIGEgY2lyY2xlIGRpdmlkZWQgaW50byBMIGlkZW50aWNhbCBzZWN0aW9ucy4gVGhlIHNlY3Rpb25zIGFyb3VuZCB0aGUgY2lyY2xlIGFyZSBudW1iZXJlZCBjb25zZWN1dGl2ZWx5IGZyb20gMCB0byBMLTEuIFRoYXQgaXMsIGZvciAwICZsZTsgaSAmbGU7IEwtMiwgc2VjdGlvbnMgaSBhbmQgaSsxIGFyZSBhZGphY2VudCwgYW5kIGFsc28gc2VjdGlvbnMgMCBhbmQgTC0xIGFyZSBhZGphY2VudC4gVGhlcmUgYXJlIE4gdGVhbXMgYXQgdGhlIHZlbnVlLiBFYWNoIHRlYW0gaXMgc2l0dGluZyBpbiBvbmUgb2YgdGhlIHNlY3Rpb25zLiBFYWNoIHNlY3Rpb24gbWF5IGNvbnRhaW4gYXJiaXRyYXJpbHkgbWFueSB0ZWFtcy4gU29tZSBzZWN0aW9ucyBtYXkgZXZlbiBiZSBlbXB0eS48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gaWRlbnRpY2FsIHNvdXZlbmlycy4gSW5pdGlhbGx5LCBib3RoIEFtYW4gYW5kIGFsbCBvZiB0aGUgc291dmVuaXJzIGFyZSBpbiBzZWN0aW9uIDAuIEFtYW4gc2hvdWxkIGdpdmUgb25lIHNvdXZlbmlyIHRvIGVhY2ggdGVhbSwgYW5kIGFmdGVyIGRlbGl2ZXJpbmcgdGhlIGxhc3Qgc291dmVuaXIgaGUgbXVzdCByZXR1cm4gdG8gc2VjdGlvbiAwLiBOb3RlIHRoYXQgc29tZSB0ZWFtcyBtYXkgYmUgc2l0dGluZyBpbiBzZWN0aW9uIDAuPFwvcD5cclxuXHJcbjxwPkF0IGFueSBtb21lbnQsIEFtYW4gY2FuIG9ubHkgY2FycnkgYXQgbW9zdCBLIHNvdXZlbmlycy4gQW1hbiBtdXN0IHBpY2sgdXAgc291dmVuaXJzIGluIHNlY3Rpb24gMCwgYW5kIHRoaXMgdGFrZXMgaGltIG5vIHRpbWUuIEVhY2ggc291dmVuaXIgbXVzdCBiZSBjYXJyaWVkIHVudGlsIGl0IGlzIGRlbGl2ZXJlZCB0byBvbmUgb2YgdGhlIHRlYW1zLiBXaGVuZXZlciBBbWFuIGNhcnJpZXMgb25lIG9yIG1vcmUgc291dmVuaXJzIGFuZCByZWFjaGVzIGEgc2VjdGlvbiB3aXRoIGEgdGVhbSB0aGF0IGhhcyBub3QgcmVjZWl2ZWQgYSBzb3V2ZW5pciB5ZXQsIGhlIG1heSBnaXZlIHRoYXQgdGVhbSBvbmUgb2YgdGhlIHNvdXZlbmlycyBoZSBjYXJyaWVzLiBUaGlzIGFsc28gaGFwcGVucyBpbnN0YW50bHkuIFRoZSBvbmx5IHRoaW5nIHRoYXQgdGFrZXMgdGltZSBpcyBtb3ZlbWVudC4gQW1hbiBjYW4gbW92ZSBhcm91bmQgdGhlIGNpcmN1bGFyIHZlbnVlIGluIGJvdGggZGlyZWN0aW9ucy4gTW92aW5nIHRvIGFuIGFkamFjZW50IHNlY3Rpb24gKGVpdGhlciBjbG9ja3dpc2Ugb3IgY291bnRlcmNsb2Nrd2lzZSkgdGFrZXMgaGltIGV4YWN0bHkgb25lIHNlY29uZCwgcmVnYXJkbGVzcyBvZiBob3cgbWFueSBzb3V2ZW5pcnMgaGUgY2Fycmllcy48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBzZWNvbmRzIEFtYW4gbmVlZHMgdG8gZGVsaXZlciBhbGwgc291dmVuaXJzIGFuZCB0aGVuIHJldHVybiB0byBoaXMgaW5pdGlhbCBwb3NpdGlvbi48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBleGFtcGxlIHdlIGhhdmUgTiA9IDMgdGVhbXMsIEFtYW4mcnNxdW87cyBjYXJyeWluZyBjYXBhY2l0eSBpcyBLID0gMiwgYW5kIHRoZSBudW1iZXIgb2Ygc2VjdGlvbnMgaXMgTCA9IDguIFRoZSB0ZWFtcyBhcmUgbG9jYXRlZCBpbiBzZWN0aW9ucyAxLCAyLCBhbmQgNS48XC9wPlxyXG5cclxuPHA+cm1mbGE8XC9wPlxyXG5cclxuPHA+T25lIG9mIHRoZSBvcHRpbWFsIHNvbHV0aW9ucyBpcyBzaG93biBpbiB0aGUgcGljdHVyZSBhYm92ZS4gSW4gaGlzIGZpcnN0IHRyaXAgQW1hbiB0YWtlcyB0d28gc291dmVuaXJzLCBkZWxpdmVycyBvbmUgdG8gdGhlIHRlYW0gaW4gc2VjdGlvbiAyLCB0aGVuIHRoZSBvdGhlciB0byB0aGUgdGVhbSBpbiBzZWN0aW9uIDUsIGFuZCBmaW5hbGx5IGhlIHJldHVybnMgdG8gc2VjdGlvbiAwLiBUaGlzIHRyaXAgdGFrZXMgOCBzZWNvbmRzLiBJbiBoaXMgc2Vjb25kIHRyaXAgQW1hbiBicmluZ3MgdGhlIHJlbWFpbmluZyBzb3V2ZW5pciB0byB0aGUgdGVhbSBpbiBzZWN0aW9uIDEgYW5kIHRoZW4gcmV0dXJucyB0byBzZWN0aW9uIDAuIEhlIG5lZWRzIGFub3RoZXIgMiBzZWNvbmRzIHRvIGRvIHRoaXMuIFRodXMsIHRoZSB0b3RhbCB0aW1lIGlzIDEwIHNlY29uZHMuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gTiwgSywgTCwgYW5kIHRoZSBwb3NpdGlvbnMgb2YgYWxsIHRlYW1zLiBDb21wdXRlIHRoZSBzbWFsbGVzdCBudW1iZXIgb2Ygc2Vjb25kcyBBbWFuIG5lZWRzIHRvIGRlbGl2ZXIgYWxsIHRoZSBzb3V2ZW5pcnMgYW5kIHRvIHJldHVybiB0byBzZWN0aW9uIDAuIFlvdSBuZWVkIHRvIGltcGxlbWVudCB0aGUgZnVuY3Rpb24gPGNvZGU+ZGVsaXZlcnk8XC9jb2RlPjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT5kZWxpdmVyeShOLCBLLCBMLCBwb3NpdGlvbnMpPFwvY29kZT4gJm1kYXNoOyBUaGlzIGZ1bmN0aW9uIHdpbGwgYmUgY2FsbGVkIGJ5IHRoZSBncmFkZXIgZXhhY3RseSBvbmNlLlxyXG5cclxuXHQ8dWw+XHJcblx0XHQ8bGk+PGNvZGU+TjxcL2NvZGU+OiB0aGUgbnVtYmVyIG9mIHRlYW1zLjxcL2xpPlxyXG5cdFx0PGxpPjxjb2RlPks8XC9jb2RlPjogdGhlIG1heGltdW0gbnVtYmVyIG9mIHNvdXZlbmlycyBBbWFuIGNhbiBjYXJyeSBhdCB0aGUgc2FtZSB0aW1lLjxcL2xpPlxyXG5cdFx0PGxpPjxjb2RlPkw8XC9jb2RlPjogdGhlIG51bWJlciBvZiBzZWN0aW9ucyBpbiB0aGUgdmVudWUgb2YgdGhlIG9wZW5pbmcgY2VyZW1vbnkuPFwvbGk+XHJcblx0XHQ8bGk+PGNvZGU+cG9zaXRpb25zPFwvY29kZT46IGFuIGFycmF5IG9mIGxlbmd0aCBOLiA8Y29kZT5wb3NpdGlvbnNbMF08XC9jb2RlPiwgLi4uLCA8Y29kZT5wb3NpdGlvbnNbTi0xXTxcL2NvZGU+IGdpdmUgdGhlIHNlY3Rpb24gbnVtYmVyIG9mIGFsbCB0ZWFtcy4gVGhlIGVsZW1lbnRzIG9mIHBvc2l0aW9ucyBhcmUgaW4gbm9uLWRlY3JlYXNpbmcgb3JkZXIuPFwvbGk+XHJcblx0XHQ8bGk+VGhlIGZ1bmN0aW9uIHNob3VsZCByZXR1cm4gdGhlIHNtYWxsZXN0IG51bWJlciBvZiBzZWNvbmRzIGluIHdoaWNoIEFtYW4gY2FuIGNvbXBsZXRlIGhpcyB0YXNrLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPmxpbmUgMTogPGNvZGU+TjxcL2NvZGU+IDxjb2RlPks8XC9jb2RlPiA8Y29kZT5MPFwvY29kZT48XC9saT5cclxuXHQ8bGk+bGluZSAyOiA8Y29kZT5wb3NpdGlvbnNbMF08XC9jb2RlPiAmaGVsbGlwOyA8Y29kZT5wb3NpdGlvbnNbTi0xXTxcL2NvZGU+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+MSAmbGU7IE4gJmxlOyAxMDxzdXA+NzxcL3N1cD4sIDEgJmxlOyBLICZsZTsgTiwgMSAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludHMgdGhlIHJldHVybiB2YWx1ZSBvZiA8Y29kZT5kZWxpdmVyeTxcL2NvZGU+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 2015 1번

  • 문제의 오타를 찾은 사람: ntopia