시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 8 8 47.059%

문제

1 × 4N 크기의 격자의 맨 오른쪽 2N개의 칸에 블록이 놓여있다.

당신은 격자에 있는 연속한 두 개의 블록을 집어서 빈 칸에 놓을 수 있다. 이때 블록의 순서는 바뀌면 안 되며 블록을 놓을 때도 연속한 두 개의 빈 칸에 놓아야 한다.

위 그림에서, 첫 번째 그림은 맨 처음 상태에서 한 번 블록을 옮겨서 나올 수 있는 형태이고, 두 번째 그림은 그렇지 않은 형태이다.

당신은 블록을 최소한으로 옮겨서 N개의 'A' 블록과 N개의 'B' 블록이 연속하게 붙은 형태로 만들려고 한다. 즉, 마지막 상태는 아래와 같은 형태 중 한 가지 모습이여야 한다.

(가능한 마지막 상태는 위 두 경우를 포함해서 총 9가지이다.)

'A' 블록의 개수가 주어질 때 블록을 어떻게 옮겨야 하는지 구하는 프로그램을 작성하여라. 단, 반드시 최소 횟수로 옮겨야 함에 유의하여라.

입력

첫 번째 줄에 N이 주어진다. (3 ≤ N ≤ 100)

출력

몇 개의 줄에 블록을 옮기는 과정을 'X to Y' 형식으로 출력한다. 'X to Y'는, X, X+1번 칸의 블록을 Y, Y+1번 칸으로 옮기는 것을 의미한다. (-2N+1 ≤ X, Y ≤ 2N-1, X ≠ Y)

답이 여러 개이면 그중 아무거나 출력해도 된다.

예제 입력 1

5

예제 출력 1

8 to -1
3 to 8
6 to 3
0 to 6
9 to 0
W3sicHJvYmxlbV9pZCI6IjEwMDUwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZTE0XHViODVkIiwiZGVzY3JpcHRpb24iOiI8cD4xICZ0aW1lczsgNE4gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWI5ZTggXHVjNjI0XHViOTc4XHVjYWJkIDJOXHVhYzFjXHVjNzU4IFx1Y2U3OFx1YzVkMCBcdWJlMTRcdWI4NWRcdWM3NzQgXHViMTkzXHVjNWVjXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIHNyYz1cIlwvdXNlcnVwbG9hZFwvZnVuY3Rpb254XC8yMDE1MTFcLzYwZWUyMDdjMTg4MDNjZTFhMGM5MWJhOTVhOGUyNDc5LnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVhY2E5XHVjNzkwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjOWQxXHVjNWI0XHVjMTFjIFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWJlMTRcdWI4NWRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YmMxNFx1YjAwY1x1YmE3NCBcdWM1NDggXHViNDE4XHViYTcwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWIxOTNcdWM3NDQgXHViNTRjXHViM2M0IFx1YzVmMFx1YzE4ZFx1ZDU1YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBzcmM9XCJcL3VzZXJ1cGxvYWRcL2Z1bmN0aW9ueFwvMjAxNTExXC80NmMzOTNiMGRhMmQ4YTgyNTA0NDRiMDUyNGFjMWMwZC5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYywgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViOWU4IFx1Y2M5OFx1Yzc0YyBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMgXHVkNTVjIFx1YmM4OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjNjJlXHVhY2E4XHVjMTFjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQ2MTVcdWQwZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzNjXHViODVjIFx1YzYyZVx1YWNhOFx1YzExYyBOXHVhYzFjXHVjNzU4ICYjMzk7QSYjMzk7IFx1YmUxNFx1Yjg1ZFx1YWNmYyBOXHVhYzFjXHVjNzU4ICYjMzk7QiYjMzk7IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWFjOGMgXHViZDk5XHVjNzQwIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YjljOFx1YzljMFx1YjljOSBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWQwZGMgXHVjOTExIFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHViYWE4XHVjMmI1XHVjNzc0XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBzcmM9XCJcL3VzZXJ1cGxvYWRcL2Z1bmN0aW9ueFwvMjAxNTExXC9lMmI3Y2RmYzFjMDE4NzM0Njk5YTYyOWExNDQ1ZWEyZS5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+KFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjMGMxXHVkMGRjXHViMjk0IFx1YzcwNCBcdWI0NTAgXHVhY2JkXHVjNmIwXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyBcdWNkMWQgOVx1YWMwMFx1YzljMFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPiYjMzk7QSYjMzk7IFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzYyZVx1YWNhOFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuIFx1YjJlOCwgXHViYzE4XHViNGRjXHVjMmRjIFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI4NWMgXHVjNjJlXHVhY2E4XHVjNTdjIFx1ZDU2OFx1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmE4NyBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWM2MmVcdWFlMzBcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNzQ0ICYjMzk7WCB0byBZJiMzOTsgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJiMzOTtYIHRvIFkmIzM5O1x1YjI5NCwgWCwgWCsxXHViYzg4IFx1Y2U3OFx1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NDQgWSwgWSsxXHViYzg4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKC0yTisxICZsZTsgWCwgWSAmbGU7IDJOLTEsIFggJm5lOyBZKTxcL3A+XHJcblxyXG48cD5cdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3NFx1YmE3NCBcdWFkZjhcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwNTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWdnYWdlIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBhaXJsaW5lIGhhcyB0d28gZmxpZ2h0cyBsZWF2aW5nIGF0IGFib3V0IHRoZSBzYW1lIHRpbWUgZnJvbSBJQ1BDaXR5LCBvbmUgdG8gY2l0eSBCIGFuZCBvbmUgdG8gY2l0eSBBLiBUaGUgYWlybGluZSBhbHNvIGhhcyBuIGNvdW50ZXJzIHdoZXJlIHBhc3NlbmdlcnMgY2hlY2sgdGhlaXIgYmFnZ2FnZS4gQXQgZWFjaCBjb3VudGVyIHRoZXJlIGlzIGEgcGFpciBvZiBpZGVudGljYWwgYmFnZ2FnZSBiaW5zLCBvbmUgZm9yIGNpdHkgQiBhbmQgb25lIGZvciBjaXR5IEEuPFwvcD5cclxuXHJcbjxwPkp1c3QgYmVmb3JlIHRoZSBmbGlnaHRzIGRlcGFydCwgZWFjaCBwYWlyIG9mIGJhZ2dhZ2UgYmlucyBpcyBtb3ZlZCBieSBhIG1vdG9yaXplZCBjYXJ0IHRvIGEgc29ydGluZyBhcmVhLiBUaGUgY2FydCBhbHdheXMgbW92ZXMgdHdvIGJpbnMgYXQgYSB0aW1lLCBvbmUgZm9yIGNpdHkgQiBhbmQgb25lIGZvciBjaXR5IEEuIEFmdGVyIGFsbCB0aGUgYmlucyBoYXZlIGJlZW4gbW92ZWQsIHRoZXkgbGluZSB1cCBpbiB0aGUgc29ydGluZyBhcmVhIGxpa2UgdGhpczo8XC9wPlxyXG5cclxuPHA+QiBBIEIgQSBCIEEgLi4uIEIgQTxcL3A+XHJcblxyXG48cD5UaGF0IGlzLCB0aGVyZSBhcmUgMm4gYmFnZ2FnZSBiaW5zIGluIGEgcm93LCBzdGFydGluZyB3aXRoIGEgYmluIGZvciBjaXR5IEIsIHRoZW4gb25lIGZvciBjaXR5IEEsIGFuZCBzbyBmb3J0aC4gVGhlIHRhc2sgbm93IGlzIHRvIHJlb3JkZXIgdGhlbSBzbyBhbGwgdGhlIGJhZ2dhZ2UgYmlucyBmb3IgY2l0eSBBIHByZWNlZGUgdGhlIGJhZ2dhZ2UgYmlucyBmb3IgY2l0eSBCLiBUaGVuIHRoZSBiaW5zIGNhbiBiZSBsb2FkZWQgb24gdGhlIGFwcHJvcHJpYXRlIGFpcmNyYWZ0LjxcL3A+XHJcblxyXG48cD5UaGUgcmVvcmRlcmluZyBpcyBkb25lIGJ5IG1vdmluZyBwYWlycyBvZiBhZGphY2VudCBiYWdnYWdlIGJpbnMgKG5vdCBuZWNlc3NhcmlseSBCIHRoZW4gQSksIGFnYWluIHZpYSB0aGUgbW90b3JpemVkIGNhcnQuIEZvciBwcm9wZXIgYmFsYW5jZSwgdGhlIGNhcnQgbXVzdCBhbHdheXMgY2FycnkgdHdvIGJpbnMsIG5ldmVyIGp1c3Qgb25lLiBBIHBhaXIgb2YgYmlucyBtdXN0IGFsd2F5cyBiZSBtb3ZlZCB0byBhbiBlbXB0eSBzcGFjZSB0aGF0IGlzIGF0IGxlYXN0IHR3byBiaW5zIHdpZGUuIE9uIHRoZSBsZWZ0IG9mIHRoZSBmaXJzdCBiaW4gYXJlIHNvbWUgZW1wdHkgc3BhY2VzIHRoYXQgY2FuIGJlIHVzZWQgYXMgbmVlZGVkIGR1cmluZyB0aGUgcmVvcmRlcmluZy48XC9wPlxyXG5cclxuPHA+V2hlbiB0aGUgcmVvcmRlcmluZyBwcm9jZXNzIGJlZ2lucywgdGhlIGJpbiBsb2NhdGlvbnMgYXJlIG51bWJlcmVkIGZyb20gMSAoaW5pdGlhbGx5IGNvbnRhaW5pbmcgdGhlIGxlZnRtb3N0IEIgYmFnZ2FnZSBiaW4pIHRvIDJuIChpbml0aWFsbHkgY29udGFpbmluZyB0aGUgcmlnaHRtb3N0IEEgYmFnZ2FnZSBiaW4pLiBUaGVyZSBhcmUgMm4gaW5pdGlhbGx5IGVtcHR5IHNwYWNlcyB0byB0aGUgbGVmdCBvZiB0aGUgYmlucywgbnVtYmVyZWQgZnJvbSAwIHRvICZtaW51czsybiArIDEsIGFzIHNob3duIGluIEZpZ3VyZSBBLjEgZm9yIHRoZSBjYXNlIG4gPSA0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9iYWdnYWdlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjU2cHg7IHdpZHRoOjU0M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5GaWd1cmUgQS4xOiBJbml0aWFsIGNvbmZpZ3VyYXRpb24gb2YgYmlucyBhbmQgZW1wdHkgc3BhY2VzIGZvciBuID0gNDxcL3A+XHJcblxyXG48cD5HaXZlbiBuLCBmaW5kIGEgc2hvcnRlc3Qgc2VxdWVuY2Ugb2YgbW92ZXMgdGhhdCB3aWxsIHJlb3JkZXIgdGhlIGJpbnMgc28gdGhhdCBhbGwgdGhlIEEgYmlucyBhcmUgdG8gdGhlIGxlZnQgb2YgYWxsIHRoZSBCIGJpbnMuIEF0IHRoZSBlbmQgb2YgdGhlIHByb2Nlc3MsIGl0IGlzIHBvc3NpYmxlIHRoYXQgdGhlIGxlZnRtb3N0IEEgYmluIGlzIGF0IHNvbWUgbG9jYXRpb24gb3RoZXIgdGhhbiAxLCBidXQgdGhlIGJpbnMgbXVzdCBiZSBhZGphY2VudCBpbiBhIHNlcXVlbmNlIG9mIDJuIGxvY2F0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNpbmdsZSB0ZXN0IGNhc2UsIHdoaWNoIGNvbnNpc3RzIG9mIHRoZSBpbnRlZ2VyIG4gKDMgJmxlOyBuICZsZTsgMTAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5EaXNwbGF5IGEgc2hvcnRlc3Qgc2VxdWVuY2Ugb2YgbW92ZXMgdGhhdCB3aWxsIGNvcnJlY3RseSByZW9yZGVyIHRoZSBiaW5zLiBFYWNoIG1vdmUgaXMgb2YgdGhlIGZvcm0gJmxkcXVvO2YgdG8gdCZyZHF1bzssIHdoZXJlIGYgYW5kIHQgYXJlIGludGVnZXJzIHJlcHJlc2VudGluZyB0aGUgbW92ZW1lbnQgb2YgdGhlIGJpbnMgaW4gbG9jYXRpb25zIGYgYW5kIGYgKyAxIHRvIGxvY2F0aW9ucyB0IGFuZCB0ICsgMS4gSWYgbXVsdGlwbGUgc29sdXRpb25zIGFyZSBwb3NzaWJsZSwgZGlzcGxheSBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > World Finals > 2014 World Finals A번