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

문제

상근이는 박스 N개를 로봇을 이용해서 정렬하려고 한다. 박스에는 1부터 N까지 숫자가 겹치지 않게 쓰여 있고, 이 수가 오름차순을 이루도록 박스를 정렬하려고 한다.

상근이가 가지고 있는 로봇에 수열을 입력하면, 위치에 해당하는 박스를 교환하게 된다. 수열에는 같은 위치가 두 번 이상 주어지면 안 된다.

예를 들어, 박스가 지금 [4, 1, 5, 2, 3] 순서로 놓여져 있고, 로봇에 [2, 1, 3] 명령을 내렸다고 해보자. 그럼 두 번째 위치에 있는 박스를 위치 1로 옮기고, 첫 번째 박스는 위치 3으로, 세 번째 박스는 위치 2로 이동하게 된다. 박스의 순서는 [1, 5, 4, 2, 3]이 된다.

명령을 가장 적게 이용해서 박스를 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 박스의 수 N이 주어진다. (2 ≤ N ≤ 1000)

다음 줄에는 박스에 붙어있는 숫자가 순서대로 주어진다. 같은 숫자가 두 번 이상 주어지지 않는다.

출력

첫째 줄에 정렬하는데 사용한 명령의 수 X를 출력한다.

그 다음 X개 줄에는 로봇에게 내린 명령을 순서대로 출력한다. 가장 첫 숫자는 수열의 길이이며, 그 다음에 콜론(:)과 공백을 출력하고, 수열의 각 원소를 출력한다.

예제 입력 1

3
3 2 1

예제 출력 1

1
2: 3 1

예제 입력 2

5
2 3 1 5 4

예제 출력 2

2
3: 1 2 3
2: 5 4

예제 입력 3

5
1 2 3 4 5

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjI4MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTVcdWMyYTQgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYzE1XHVjMmE0IE5cdWFjMWNcdWI5N2MgXHViODVjXHViZDA3XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWI4MmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWMyMThcdWFjMDAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjNjNFx1Yjg1ZCBcdWJjMTVcdWMyYTRcdWI5N2MgXHVjODE1XHViODJjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViODVjXHViZDA3XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NThcdWJhNzQsIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYzE1XHVjMmE0XHViOTdjIFx1YWQ1MFx1ZDY1OFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzIxOFx1YzVmNFx1YzVkMFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjOWMwXHVhZTA4IFs0LCAxLCA1LCAyLCAzXSBcdWMyMWNcdWMxMWNcdWI4NWMgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViODVjXHViZDA3XHVjNWQwIFsyLCAxLCAzXSBcdWJhODVcdWI4MzlcdWM3NDQgXHViMGI0XHViODM4XHViMmU0XHVhY2UwIFx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVhZGY4XHViN2ZjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJjMTVcdWMyYTRcdWI5N2MgXHVjNzA0XHVjZTU4IDFcdWI4NWMgXHVjNjJlXHVhZTMwXHVhY2UwLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmMxNVx1YzJhNFx1YjI5NCBcdWM3MDRcdWNlNTggM1x1YzczY1x1Yjg1YywgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWJjMTVcdWMyYTRcdWIyOTQgXHVjNzA0XHVjZTU4IDJcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViYzE1XHVjMmE0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBbMSwgNSwgNCwgMiwgM11cdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhODVcdWI4MzlcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViYzE1XHVjMmE0XHViOTdjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMTVcdWMyYTRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxNVx1YzJhNFx1YzVkMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWQ1NWMgXHViYTg1XHViODM5XHVjNzU4IFx1YzIxOCBYXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBYXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI4NWNcdWJkMDdcdWM1ZDBcdWFjOGMgXHViMGI0XHViOWIwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjY2FiIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViYTcwLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwIFx1Y2Y1Y1x1Yjg2MCg6KVx1YWNmYyBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNPUlQiLCJkZXNjcmlwdGlvbiI6IjxwPkluIG9yZGVyIHRvIGF1dG9tYXRlIGhpcyB3b3JrbG9hZCBhdCB0aGUgZmFjdG9yeSwgTWlya28gd2FudHMgdG8gcHV0IHVwIHRvIHVzZSBoaXMgb2xkIGJveC1zb3J0aW5nIHJvYm90LiBUaGVyZSBhcmUgTiBib3hlcyBpbiB0aGUgZmFjdG9yeSwgYW5kIGVhY2ggYm94IGlzIGxhYmVsbGVkIHdpdGggYW4gdW5pcXVlIGludGVnZXIgaW4gcmFuZ2UgMSB0byBOLiBNaXJrbyYjMzk7cyB0YXNrIGlzIHRvIHNvcnQgdGhlIGJveGVzIGluIHRoZSBhc2NlbmRpbmcgb3JkZXIgb2YgdGhlaXIgbGFiZWxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Tb3J0aW5nIHJvYm90IGNhbiBvbmx5IHBlcmZvcm0gb25lIHNwZWNpZmljIG9wZXJhdGlvbjogZ2l2ZW4gdGhlIHNlcXVlbmNlIG9mIHBvc2l0aW9ucywgcm9ib3QgY2FuIGRvIGEgY3ljbGljIHN3YXAgb2YgYm94ZXMgYXQgdGhvc2UgcG9zaXRpb25zLiBHaXZlbiBzZXF1ZW5jZSBkb2VzIG5vdCBjb250YWluIGFueSBwb3NpdGlvbiBtb3JlIHRoYW4gb25jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCYjMzk7cyBhc3N1bWUgdGhhdCB0aGUgYm94ZXMgYXJlIGN1cnJlbnRseSBpbiBvcmRlciBbNCwgMSwgNSwgMiwgM10sIGFuZCBNaXJrbyBwcm92aWRlcyBoaXMgcm9ib3Qgd2l0aCB0aGUgc2VxdWVuY2UgWzIsIDEsIDNdLiBSb2JvdCB3aWxsIHRoZW4gcmVhcnJhbmdlIHRoZSBib3hlcyBzbyB0aGF0IHRoZSBzZWNvbmQgYm94IHdpbGwgZ28gdG8gcG9zaXRpb24gMSwgZmlyc3QgYm94IHdpbGwgZ28gdG8gdGhlIHBvc2l0aW9uIDMsIGFuZCB0aGUgdGhpcmQgb25lIHdpbGwgdGFrZSB0aGUgcG9zaXRpb24gMi4gT2J0YWluZWQgc2VxdWVuY2Ugb2YgbGFiZWxzIGlzIFsxLCA1LCA0LCAyLCAzXS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBzb3J0IHRoZSBib3hlcyB1c2luZyB0aGUgbWluaW1hbCBudW1iZXIgb2Ygb3BlcmF0aW9ucy4gRWFjaCBzZXF1ZW5jZSBnaXZlbiB0byB0aGUgcm9ib3QgY2FuIGJlIGFyYml0cmFyeSBsb25nLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIGJveGVzIGluIHRoZSBmYWN0b3J5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycyBpbiByYW5nZSAxIHRvIE4sIGxhYmVscyBvZiBib3hlcyBpbiBvcmRlci4gTm8gaW50ZWdlciBhcHBlYXJzIHR3aWNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHNob3VsZCBjb250YWluIHRoZSBpbnRlZ2VyIFgsIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgcmVxdWlyZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgWCBsaW5lcyBzaG91bGQgY29udGFpbiB0aGUgc2VxdWVuY2VzIGdpdmVuIHRvIHJvYm90LCBvbmUgc2VxdWVuY2UgcGVyIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggbGluZSBzaG91bGQgc3RhcnQgd2l0aCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSwgZm9sbG93ZWQgYnkgYSBjb2xvbiwgYSBzaW5nbGUgd2hpdGUgc3BhY2UsIGFuZCB0aGVuIHNwYWNlIHNlcGVyYXRlZCBzZXF1ZW5jZSBvZiBwb3NpdGlvbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5PVEU6IFRoZXJlIG1heSBiZSBtdWx0aXBsZSBzb2x1dGlvbnMgYW5kIHlvdSBjYW4gb3V0cHV0IGFueSBvZiB0aGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2011 > Croatian Olympiad in Informatics 2011 1번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013