시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 43 12 12 32.432%

문제

상근이는 박스 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
W3sicHJvYmxlbV9pZCI6IjI4MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTVcdWMyYTQgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYzE1XHVjMmE0IE5cdWFjMWNcdWI5N2MgXHViODVjXHViZDA3XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWI4MmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWMyMThcdWFjMDAgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjNjNFx1Yjg1ZCBcdWJjMTVcdWMyYTRcdWI5N2MgXHVjODE1XHViODJjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViODVjXHViZDA3XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NThcdWJhNzQsIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYzE1XHVjMmE0XHViOTdjIFx1YWQ1MFx1ZDY1OFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzIxOFx1YzVmNFx1YzVkMFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWM5YzBcdWFlMDggWzQsIDEsIDUsIDIsIDNdIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWI4NWNcdWJkMDdcdWM1ZDAgWzIsIDEsIDNdIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWIwYjRcdWI4MzhcdWIyZTRcdWFjZTAgXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWFkZjhcdWI3ZmMgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmMxNVx1YzJhNFx1Yjk3YyBcdWM3MDRcdWNlNTggMVx1Yjg1YyBcdWM2MmVcdWFlMzBcdWFjZTAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYzE1XHVjMmE0XHViMjk0IFx1YzcwNFx1Y2U1OCAzXHVjNzNjXHViODVjLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YmMxNVx1YzJhNFx1YjI5NCBcdWM3MDRcdWNlNTggMlx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWJjMTVcdWMyYTRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFsxLCA1LCA0LCAyLCAzXVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE4NVx1YjgzOVx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVjODAxXHVhYzhjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjMTVcdWMyYTRcdWI5N2MgXHVjODE1XHViODJjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzE1XHVjMmE0XHVjNWQwIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHViODJjXHVkNTU4XHViMjk0XHViMzcwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWJhODVcdWI4MzlcdWM3NTggXHVjMjE4IFhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFhcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yjg1Y1x1YmQwN1x1YzVkMFx1YWM4YyBcdWIwYjRcdWI5YjAgXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWNjYWIgXHVjMjJiXHVjNzkwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzRcdWJhNzAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjZjVjXHViODYwKDopXHVhY2ZjIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU09SVCIsImRlc2NyaXB0aW9uIjoiPHA+SW4gb3JkZXIgdG8gYXV0b21hdGUgaGlzIHdvcmtsb2FkIGF0IHRoZSBmYWN0b3J5LCBNaXJrbyB3YW50cyB0byBwdXQgdXAgdG8gdXNlIGhpcyBvbGQgYm94LXNvcnRpbmcgcm9ib3QuIFRoZXJlIGFyZSBOIGJveGVzIGluIHRoZSBmYWN0b3J5LCBhbmQgZWFjaCBib3ggaXMgbGFiZWxsZWQgd2l0aCBhbiB1bmlxdWUgaW50ZWdlciBpbiByYW5nZSAxIHRvIE4uIE1pcmtvJiMzOTtzIHRhc2sgaXMgdG8gc29ydCB0aGUgYm94ZXMgaW4gdGhlIGFzY2VuZGluZyBvcmRlciBvZiB0aGVpciBsYWJlbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvcnRpbmcgcm9ib3QgY2FuIG9ubHkgcGVyZm9ybSBvbmUgc3BlY2lmaWMgb3BlcmF0aW9uOiBnaXZlbiB0aGUgc2VxdWVuY2Ugb2YgcG9zaXRpb25zLCByb2JvdCBjYW4gZG8gYSBjeWNsaWMgc3dhcCBvZiBib3hlcyBhdCB0aG9zZSBwb3NpdGlvbnMuIEdpdmVuIHNlcXVlbmNlIGRvZXMgbm90IGNvbnRhaW4gYW55IHBvc2l0aW9uIG1vcmUgdGhhbiBvbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgbGV0JiMzOTtzIGFzc3VtZSB0aGF0IHRoZSBib3hlcyBhcmUgY3VycmVudGx5IGluIG9yZGVyIFs0LCAxLCA1LCAyLCAzXSwgYW5kIE1pcmtvIHByb3ZpZGVzIGhpcyByb2JvdCB3aXRoIHRoZSBzZXF1ZW5jZSBbMiwgMSwgM10uIFJvYm90IHdpbGwgdGhlbiByZWFycmFuZ2UgdGhlIGJveGVzIHNvIHRoYXQgdGhlIHNlY29uZCBib3ggd2lsbCBnbyB0byBwb3NpdGlvbiAxLCBmaXJzdCBib3ggd2lsbCBnbyB0byB0aGUgcG9zaXRpb24gMywgYW5kIHRoZSB0aGlyZCBvbmUgd2lsbCB0YWtlIHRoZSBwb3NpdGlvbiAyLiBPYnRhaW5lZCBzZXF1ZW5jZSBvZiBsYWJlbHMgaXMgWzEsIDUsIDQsIDIsIDNdLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIHNvcnQgdGhlIGJveGVzIHVzaW5nIHRoZSBtaW5pbWFsIG51bWJlciBvZiBvcGVyYXRpb25zLiBFYWNoIHNlcXVlbmNlIGdpdmVuIHRvIHRoZSByb2JvdCBjYW4gYmUgYXJiaXRyYXJ5IGxvbmcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2YgYm94ZXMgaW4gdGhlIGZhY3RvcnkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBOIGludGVnZXJzIGluIHJhbmdlIDEgdG8gTiwgbGFiZWxzIG9mIGJveGVzIGluIG9yZGVyLiBObyBpbnRlZ2VyIGFwcGVhcnMgdHdpY2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIGludGVnZXIgWCwgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyByZXF1aXJlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBYIGxpbmVzIHNob3VsZCBjb250YWluIHRoZSBzZXF1ZW5jZXMgZ2l2ZW4gdG8gcm9ib3QsIG9uZSBzZXF1ZW5jZSBwZXIgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBsaW5lIHNob3VsZCBzdGFydCB3aXRoIHRoZSBsZW5ndGggb2YgdGhlIHNlcXVlbmNlLCBmb2xsb3dlZCBieSBhIGNvbG9uLCBhIHNpbmdsZSB3aGl0ZSBzcGFjZSwgYW5kIHRoZW4gc3BhY2Ugc2VwZXJhdGVkIHNlcXVlbmNlIG9mIHBvc2l0aW9ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tk9URTogVGhlcmUgbWF5IGJlIG11bHRpcGxlIHNvbHV0aW9ucyBhbmQgeW91IGNhbiBvdXRwdXQgYW55IG9mIHRoZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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