시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 60 27 18 41.860%

문제

스도쿠가 세계적으로 유행이 된 이후에, 비슷한 퍼즐이 매우 많이 나왔다. 게임 매거진 2009년 7월호에는 스도쿠와 도미노를 혼합한 게임인 스도미노쿠가 소개되었다. 

이 퍼즐은 스도쿠 규칙을 따른다. 스도쿠는 9×9 크기의 그리드를 1부터 9까지 숫자를 이용해서 채워야 한다. 스도쿠는 다음과 같은 조건을 만족하게 숫자를 채워야 한다.

  • 각 행에는 1부터 9까지 숫자가 하나씩 있어야 한다.
  • 각 열에는 1부터 9까지 숫자가 하나씩 있어야 한다.
  • 3×3크기의 정사각형에는 1부터 9가지 숫자가 하나씩 있어야 한다.

스도미노쿠의 그리드에는 1부터 9까지 숫자가 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 한다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 가능한 쌍이 모두 포함되어 있다. (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 1+2와 2+1은 같은 타일이기 때문에, 따로 구분하지 않는다. 도미노 타일은 회전 시킬 수 있다. 또, 3×3 크기의 정사각형의 경계에 걸쳐서 놓여질 수도 있다.

왼쪽 그림은 퍼즐의 초기 상태를 나타내고, 오른쪽은 퍼즐을 푼 상태이다.

스도미노쿠의 퍼즐의 초기 상태가 주어졌을 때, 퍼즐을 푸는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 주어진다. U는 도미노에 써 있는 한 숫자이고, LU는 길이가 2인 문자열로 U의 위치를 나타낸다. V와 LV는 도미노에 써 있는 다른 숫자를 나타낸다. 도미노의 위치는 문제에 나와있는 그림을 참고한다. 입력으로 주어지는 도미노의 각 숫자 위치는 항상 인접해 있다.

N개의 도미노의 정보가 주어진 다음 줄에는 채워져 있는 숫자의 위치가 주어진다. 위치는 도미노의 위치를 나타낸 방법과 같은 방법으로 주어진다.

모든 도미노와 숫자가 겹치는 경우는 없다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 퍼즐에 대해서, 스도쿠를 푼 결과를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

예제 입력 1

10
6 B2 1 B3
2 C4 9 C3
6 D3 8 E3
7 E1 4 F1
8 B7 4 B8
3 F5 2 F6
7 F7 6 F8
5 G4 9 G5 
7 I8 8 I9
7 C9 2 B9
C5 A3 D9 I4 A9 E5 A2 C6 I1
11
5 I9 2 H9
6 A5 7 A6
4 B8 6 C8
3 B5 8 B4
3 C3 2 D3
9 D2 8 E2
3 G2 5 H2
1 A2 8 A1
1 H8 3 I8
8 I3 7 I4
4 I6 9 I7
I5 E6 D1 F2 B3 G9 H7 C9 E5
0

예제 출력 1

Puzzle 1
872643195
361975842
549218637
126754983
738169254
495832761
284597316
657381429
913426578
Puzzle 2
814267593
965831247
273945168
392176854
586492371
741358629
137529486
459683712
628714935

힌트

W3sicHJvYmxlbV9pZCI6IjQ1NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWIzYzRcdWJiZjhcdWIxNzhcdWNmZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJhNFx1YjNjNFx1Y2ZlMFx1YWMwMCBcdWMxMzhcdWFjYzRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzIwXHVkNTg5XHVjNzc0IFx1YjQxYyBcdWM3NzRcdWQ2YzRcdWM1ZDAsIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWQzN2NcdWM5OTBcdWM3NzQgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc3NCBcdWIwOThcdWM2NTRcdWIyZTQuIFx1YWM4Y1x1Yzc4NCBcdWI5ZTRcdWFjNzBcdWM5YzQgMjAwOVx1YjE0NCA3XHVjNmQ0XHVkNjM4XHVjNWQwXHViMjk0IFx1YzJhNFx1YjNjNFx1Y2ZlMFx1YzY0MCBcdWIzYzRcdWJiZjhcdWIxNzhcdWI5N2MgXHVkNjNjXHVkNTY5XHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc3OCBcdWMyYTRcdWIzYzRcdWJiZjhcdWIxNzhcdWNmZTBcdWFjMDAgXHVjMThjXHVhYzFjXHViNDE4XHVjNWM4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVkMzdjXHVjOTkwXHVjNzQwIFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViNTMwXHViOTc4XHViMmU0LiBcdWMyYTRcdWIzYzRcdWNmZTBcdWIyOTQgOSZ0aW1lczs5IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI5N2MgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjYzQ0XHVjNmNjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMmE0XHViM2M0XHVjZmUwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjYzQ0XHVjNmNjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVkNTg5XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMSBcdWM1ZjRcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+MyZ0aW1lczszXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YjI5NCAxXHViZDgwXHVkMTMwIDlcdWFjMDBcdWM5YzAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzJhNFx1YjNjNFx1YmJmOFx1YjE3OFx1Y2ZlMFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM0ZjBcdWM1ZWNcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgNzJcdWNlNzhcdWM3NDAgXHViM2M0XHViYmY4XHViMTc4IFx1ZDBjMFx1Yzc3YyAzNlx1YWMxY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIzYzRcdWJiZjhcdWIxNzggXHVkMGMwXHVjNzdjXHVjNzQwIDFcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMzBkXHVjNzc0IFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiAoMSsyLCAxKzMsIDErNCwgMSs1LCAxKzYsIDErNywgMSs4LCAxKzksIDIrMywgMis0LCAyKzUsIC4uLikgMSsyXHVjNjQwIDIrMVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVkMGMwXHVjNzdjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNTMwXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjNjNFx1YmJmOFx1YjE3OCBcdWQwYzBcdWM3N2NcdWM3NDAgXHVkNjhjXHVjODA0IFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIDMmdGltZXM7MyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWNiZFx1YWNjNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViMTkzXHVjNWVjXHVjOWM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3YyBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZXhhbXBsZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzUycHg7IHdpZHRoOjM1MnB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9leGFtcGxlMS1zb2xuLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM1MnB4OyB3aWR0aDozNTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMyYTRcdWIzYzRcdWJiZjhcdWIxNzhcdWNmZTBcdWM3NTggXHVkMzdjXHVjOTkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ3OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHViM2M0XHViYmY4XHViMTc4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEwICZsZTsgTiAmbGU7IDM1KSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViYmY4XHViMTc4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgVSBMVSBWIExWXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gVVx1YjI5NCBcdWIzYzRcdWJiZjhcdWIxNzhcdWM1ZDAgXHVjMzY4IFx1Yzc4OFx1YjI5NCBcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzc0XHVhY2UwLCBMVVx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgMlx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgVVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBWXHVjNjQwIExWXHViMjk0IFx1YjNjNFx1YmJmOFx1YjE3OFx1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWIzYzRcdWJiZjhcdWIxNzhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHVhZGY4XHViOWJjXHVjNzQ0IFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWIzYzRcdWJiZjhcdWIxNzhcdWM3NTggXHVhYzAxIFx1YzIyYlx1Yzc5MCBcdWM3MDRcdWNlNThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViM2M0XHViYmY4XHViMTc4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjNDRcdWM2Y2NcdWM4MzggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3MDRcdWNlNThcdWIyOTQgXHViM2M0XHViYmY4XHViMTc4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjggXHViYzI5XHViYzk1XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHViM2M0XHViYmY4XHViMTc4XHVjNjQwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjYjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQzN2NcdWM5OTBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDdjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ1NzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdS1kb21pbm8ta3UiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIGlmIHRoZXJlIHdlcmUgbm90IGFscmVhZHkgZW5vdWdoIHN1ZG9rdS1saWtlIHB1enpsZXMsIHRoZSBKdWx5IDIwMDkgaXNzdWUgb2YgR2FtZXMgTWFnYXppbmUgZGVzY3JpYmVzIHRoZSBmb2xsb3dpbmcgdmFyaWFudCB0aGF0IGNvbWJpbmVzIGZhY2V0cyBvZiBib3RoIHN1ZG9rdSBhbmQgZG9taW5vcy4gVGhlIHB1enpsZSBpcyBhIGZvcm0gb2YgYSBzdGFuZGFyZCBzdWRva3UsIGluIHdoaWNoIHRoZXJlIGlzIGEgbmluZS1ieS1uaW5lIGdyaWQgdGhhdCBtdXN0IGJlIGZpbGxlZCBpbiB1c2luZyBvbmx5IGRpZ2l0cyAxIHRocm91Z2ggOS4gSW4gYSBzdWNjZXNzZnVsIHNvbHV0aW9uOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggcm93IG11c3QgY29udGFpbiBlYWNoIG9mIHRoZSBkaWdpdHMgMSB0aHJvdWdoIDkuPFwvbGk+XHJcblx0PGxpPkVhY2ggY29sdW1uIG11c3QgY29udGFpbiBlYWNoIG9mIHRoZSBkaWdpdHMgMSB0aHJvdWdoIDkuPFwvbGk+XHJcblx0PGxpPkVhY2ggb2YgdGhlIGluZGljYXRlZCB0aHJlZS1ieS10aHJlZSBzcXVhcmVzIG11c3QgY29udGFpbiBlYWNoIG9mIHRoZSBkaWdpdHMgMSB0aHJvdWdoIDkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGEgc3UtZG9taW5vLWt1LCBuaW5lIGFyYml0cmFyeSBjZWxscyBhcmUgaW5pdGlhbGl6ZWQgd2l0aCB0aGUgbnVtYmVycyAxIHRvIDkuIFRoaXMgbGVhdmVzIDcyIHJlbWFpbmluZyBjZWxscy4gVGhvc2UgbXVzdCBiZSBmaWxsZWQgYnkgbWFraW5nIHVzZSBvZiB0aGUgZm9sbG93aW5nIHNldCBvZiAzNiBkb21pbm8gdGlsZXMuIFRoZSB0aWxlIHNldCBpbmNsdWRlcyBvbmUgZG9taW5vIGZvciBlYWNoIHBvc3NpYmxlIHBhaXIgb2YgdW5pcXVlIG51bWJlcnMgZnJvbSAxIHRvIDkgKGUuZy4sIDErMiwgMSszLCAxKzQsIDErNSwgMSs2LCAxKzcsIDErOCwgMSs5LCAyKzMsIDIrNCwgMis1LCAuLi4pLiBOb3RlIHdlbGwgdGhhdCB0aGVyZSBhcmUgbm90IHNlcGFyYXRlIDErMiBhbmQgMisxIHRpbGVzIGluIHRoZSBzZXQ7IHRoZSBzaW5nbGUgc3VjaCBkb21pbm8gY2FuIGJlIHJvdGF0ZWQgdG8gcHJvdmlkZSBlaXRoZXIgb3JpZW50YXRpb24uIEFsc28sIG5vdGUgdGhhdCBkb21pbm9zIG1heSBjcm9zcyB0aGUgYm91bmRhcnkgb2YgdGhlIHRocmVlLWJ5LXRocmVlIHNxdWFyZXMgKGFzIGRvZXMgdGhlIDIrOSBkb21pbm8gaW4gb3VyIGNvbWluZyBleGFtcGxlKS48XC9wPlxyXG5cclxuPHA+VG8gaGVscCB5b3Ugb3V0LCB3ZSB3aWxsIGJlZ2luIGVhY2ggcHV6emxlIGJ5IGlkZW50aWZ5aW5nIHRoZSBsb2NhdGlvbiBvZiBzb21lIG9mIHRoZSBkb21pbm9zLiBGb3IgZXhhbXBsZSwgRmlndXJlIDEgc2hvd3MgYSBzYW1wbGUgcHV6emxlIGluIGl0cyBpbml0aWFsIHN0YXRlLiBGaWd1cmUgMiBzaG93cyB0aGUgdW5pcXVlIHdheSB0byBjb21wbGV0ZSB0aGF0IHB1enpsZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9leGFtcGxlMS5wbmdcIiBzdHlsZT1cImhlaWdodDozNTJweDsgb3BhY2l0eTowLjk7IHdpZHRoOjM1MnB4XCIgXC8+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9leGFtcGxlMS1zb2xuLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM1MnB4OyB3aWR0aDozNTJweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBwdXp6bGUgZGVzY3JpcHRpb24gYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOLCBmb3IgMTAgJmxlOyBOICZsZTsgMzUsIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGRvbWlub3MgdGhhdCBhcmUgaW5pdGlhbGx5IHBsYWNlZCBpbiB0aGUgc3RhcnRpbmcgY29uZmlndXJhdGlvbi4gRm9sbG93aW5nIHRoYXQgYXJlIE4gbGluZXMsIGVhY2ggZGVzY3JpYmluZyBhIHNpbmdsZSBkb21pbm8gYXMgVSBMVSBWIExWLiBWYWx1ZSBVIGlzIG9uZSBvZiB0aGUgbnVtYmVycyBvbiB0aGUgZG9taW5vLCBhbmQgTFUgaXMgYSB0d28tY2hhcmFjdGVyIHN0cmluZyByZXByZXNlbnRpbmcgdGhlIGxvY2F0aW9uIG9mIHZhbHVlIFUgb24gdGhlIGJvYXJkIGJhc2VkIG9uIHRoZSBncmlkIHN5c3RlbSBkaWFncmFtbWVkIGluIEZpZ3VyZSAxLiBUaGUgdmFyaWFibGVzIFYgYW5kIExWIHJlcHJlc2VudGluZyB0aGUgcmVzcGVjdGl2ZSB2YWx1ZSBhbmQgbG9jYXRpb24gb2YgdGhlIG90aGVyIGhhbGYgb2YgdGhlIGRvbWluby4gRm9yIGV4YW1wbGUsIG91ciBmaXJzdCBzYW1wbGUgaW5wdXQgYmVpbmdzIHdpdGggYSBkb21pbm8gZGVzY3JpYmVkIGFzIDYgQjIgMSBCMy4gVGhpcyBjb3JyZXNwb25kcyB0byB0aGUgZG9taW5vIHdpdGggdmFsdWVzIDYrMSBiZWluZyBwbGFjZWQgb24gdGhlIGJvYXJkIHN1Y2ggdGhhdCB2YWx1ZSA2IGlzIGluIHJvdyBCLCBjb2x1bW4gMiBhbmQgdmFsdWUgMSBpbiByb3cgQiwgY29sdW1uIDMuIFRoZSB0d28gbG9jYXRpb25zIGZvciBhIGdpdmVuIGRvbWlubyB3aWxsIGFsd2F5cyBiZSBuZWlnaGJvcmluZy48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhlIHNwZWNpZmljYXRpb24gb2YgdGhlIE4gZG9taW5vcyB3aWxsIGJlIGEgZmluYWwgbGluZSB0aGF0IGRlc2NyaWJlcyB0aGUgaW5pdGlhbCBsb2NhdGlvbnMgb2YgdGhlIGlzb2xhdGVkIG51bWJlcnMsIG9yZGVyZWQgZnJvbSAxIHRvIDksIHVzaW5nIHRoZSBzYW1lIHJvdy1jb2x1bW4gY29udmVudGlvbnMgZm9yIGRlc2NyaWJpbmcgbG9jYXRpb25zIG9uIHRoZSBib2FyZC4gQWxsIGluaXRpYWwgbnVtYmVycyBhbmQgZG9taW5vcyB3aWxsIGJlIGF0IHVuaXF1ZSBsb2NhdGlvbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBmaWxlIGVuZHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHB1enpsZSwgb3V0cHV0IGFuIGluaXRpYWwgbGluZSBpZGVudGlmeWluZyB0aGUgcHV6emxlIG51bWJlciwgYXMgc2hvd24gYmVsb3cuIEZvbGxvd2luZyB0aGF0LCBvdXRwdXQgdGhlIDl4OSBzdWRva3UgYm9hcmQgdGhhdCBjYW4gYmUgZm9ybWVkIHdpdGggdGhlIHNldCBvZiBkb21pbm9zLiBUaGVyZSB3aWxsIGJlIGEgdW5pcXVlIHNvbHV0aW9uIGZvciBlYWNoIHB1enpsZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > North America > Mid-Central Regional > 2011 Mid-Central Regional Programming Contest D번

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