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

문제

민승이는 정문이에게 미션을 주면서 즐기고 있다. 정문이는 눈에 헤드밴드를 썼기 때문에 앞을 볼 수 없다.

미션은 1부터 N까지 번호가 붙어진 N개의 컵으로 진행된다. 처음에 민승이는 이 N개의 컵 중 한 컵에 공을 넣는다. (당연히 정문이는 어디에 넣은지 알 수 없다) 그 다음부터 정문이는 매 단계마다 'A' 또는 'B' 문자를 부르고 이에 따라 민승이는 공을 꺼내서 다른 컵으로 넣는다. (꺼내서 다시 동일한 컵에 넣을 수도 있다.) 단 민승이가 공을 꺼내서 넣는 컵은 현재 컵의 위치와 정문이가 부른 알파벳에 의해서만 결정된다.

만약에 현재 공이 K번째 컵에 있다면 이 컵은 정문이가 부른 알파벳에 의해서 Ak(정문이가 'A'를 불렀을 경우) 또는 Bk(정문이가 'B'를 불렀을 경우)번째 컵으로 이동하게 된다.

정문이의 미션은 처음에 민승이가 공을 어떤 컵에 넣든지간에 최종적으로 이 공이 컵 1로 들어가게 하는 것이다. 우리는 이런 정문이를 도와 공이 컵 1로 들어가기 위해 정문이가 불러야할 알파벳 문자열을 찾는것이다. 단, 이 문자열은 10,000보다 작아야 한다.

입력

첫 번째 줄에 컵의 개수 N (1 ≤ N ≤ 500)이 주어진다. 그 다음 N개의 줄에는 한 컵에 대한 Ak와 Bk가 공백으로 구분되어 주어진다. (두 번째 줄에 A1과 B1, 다음 줄에 A2와 B2 등이 주어진다는 뜻이다)

출력

정문이가 불러야할 A또는 B로 구성된 문자열을 출력한다. (여러 해가 존재할 경우에는 그 중 하나만 출력되면 되고 항상 답이 존재하는 입력만 주어진다고 하자.) 문자열의 길이는 10,000보다 작거나 같아야 한다.

예제 입력 1

4
1 2
1 3
3 1
1 4

예제 출력 1

ABA

예제 입력 2

10
4 9
5 3
1 8
6 1
3 8
9 1
10 1
6 3
2 3
8 1

예제 출력 2

BABAABAB
W3sicHJvYmxlbV9pZCI6IjE3MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZjUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmJmY1x1YzJiOVx1Yzc3NFx1YjI5NCBcdWM4MTVcdWJiMzhcdWM3NzRcdWM1ZDBcdWFjOGMgXHViYmY4XHVjMTU4XHVjNzQ0IFx1YzhmY1x1YmE3NFx1YzExYyBcdWM5OTBcdWFlMzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM4MTVcdWJiMzhcdWM3NzRcdWIyOTQgXHViMjA4XHVjNWQwIFx1ZDVlNFx1YjRkY1x1YmMzNFx1YjRkY1x1Yjk3YyBcdWMzN2NcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzU1ZVx1Yzc0NCBcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmY4XHVjMTU4XHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0XHVjOWM0IE5cdWFjMWNcdWM3NTggXHVjZWY1XHVjNzNjXHViODVjIFx1YzljNFx1ZDU4OVx1YjQxY1x1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwIFx1YmJmY1x1YzJiOVx1Yzc3NFx1YjI5NCBcdWM3NzQgTlx1YWMxY1x1Yzc1OCBcdWNlZjUgXHVjOTExIFx1ZDU1YyBcdWNlZjVcdWM1ZDAgXHVhY2Y1XHVjNzQ0IFx1YjEyM1x1YjI5NFx1YjJlNC4gKFx1YjJmOVx1YzVmMFx1ZDc4OCBcdWM4MTVcdWJiMzhcdWM3NzRcdWIyOTQgXHVjNWI0XHViNTE0XHVjNWQwIFx1YjEyM1x1Yzc0MFx1YzljMCBcdWM1NGMgXHVjMjE4IFx1YzVjNlx1YjJlNCkgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YmQ4MFx1ZDEzMCBcdWM4MTVcdWJiMzhcdWM3NzRcdWIyOTQgXHViOWU0IFx1YjJlOFx1YWNjNFx1YjljOFx1YjJlNCAmIzM5O0EmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTtCJiMzOTsgXHViYjM4XHVjNzkwXHViOTdjIFx1YmQ4MFx1Yjk3NFx1YWNlMCBcdWM3NzRcdWM1ZDAgXHViNTMwXHViNzdjIFx1YmJmY1x1YzJiOVx1Yzc3NFx1YjI5NCBcdWFjZjVcdWM3NDQgXHVhZWJjXHViMGI0XHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWNlZjVcdWM3M2NcdWI4NWMgXHViMTIzXHViMjk0XHViMmU0LiAoXHVhZWJjXHViMGI0XHVjMTFjIFx1YjJlNFx1YzJkYyBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjZWY1XHVjNWQwIFx1YjEyM1x1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LikgXHViMmU4IFx1YmJmY1x1YzJiOVx1Yzc3NFx1YWMwMCBcdWFjZjVcdWM3NDQgXHVhZWJjXHViMGI0XHVjMTFjIFx1YjEyM1x1YjI5NCBcdWNlZjVcdWM3NDAgXHVkNjA0XHVjN2FjIFx1Y2VmNVx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVjODE1XHViYjM4XHVjNzc0XHVhYzAwIFx1YmQ4MFx1Yjk3OCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM1ZDAgXHVjNzU4XHVkNTc0XHVjMTFjXHViOWNjIFx1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkXHVjNWQwIFx1ZDYwNFx1YzdhYyBcdWFjZjVcdWM3NzQgS1x1YmM4OFx1YzlmOCBcdWNlZjVcdWM1ZDAgXHVjNzg4XHViMmU0XHViYTc0IFx1Yzc3NCBcdWNlZjVcdWM3NDAgXHVjODE1XHViYjM4XHVjNzc0XHVhYzAwIFx1YmQ4MFx1Yjk3OCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM1ZDAgXHVjNzU4XHVkNTc0XHVjMTFjIEE8c3ViPms8XC9zdWI+KFx1YzgxNVx1YmIzOFx1Yzc3NFx1YWMwMCAmIzM5O0EmIzM5O1x1Yjk3YyBcdWJkODhcdWI4MDBcdWM3NDQgXHVhY2JkXHVjNmIwKSBcdWI2MTBcdWIyOTQgQjxzdWI+azxcL3N1Yj4oXHVjODE1XHViYjM4XHVjNzc0XHVhYzAwICYjMzk7QiYjMzk7XHViOTdjIFx1YmQ4OFx1YjgwMFx1Yzc0NCBcdWFjYmRcdWM2YjApXHViYzg4XHVjOWY4IFx1Y2VmNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWJiMzhcdWM3NzRcdWM3NTggXHViYmY4XHVjMTU4XHVjNzQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJiZmNcdWMyYjlcdWM3NzRcdWFjMDAgXHVhY2Y1XHVjNzQ0IFx1YzViNFx1YjVhNCBcdWNlZjVcdWM1ZDAgXHViMTIzXHViNGUwXHVjOWMwXHVhYzA0XHVjNWQwIFx1Y2Q1Y1x1Yzg4NVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM3NzQgXHVhY2Y1XHVjNzc0IFx1Y2VmNSAxXHViODVjIFx1YjRlNFx1YzViNFx1YWMwMFx1YWM4YyBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0XHViN2YwIFx1YzgxNVx1YmIzOFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVhY2Y1XHVjNzc0IFx1Y2VmNSAxXHViODVjIFx1YjRlNFx1YzViNFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODE1XHViYjM4XHVjNzc0XHVhYzAwIFx1YmQ4OFx1YjdlY1x1YzU3Y1x1ZDU2MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2MzZVx1YjI5NFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViMmU4LCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZWY1XHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDUwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWNlZjVcdWM1ZDAgXHViMzAwXHVkNTVjIEE8c3ViPms8XC9zdWI+XHVjNjQwIEI8c3ViPms8XC9zdWI+XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgQTxzdWI+MTxcL3N1Yj5cdWFjZmMgQjxzdWI+MTxcL3N1Yj4sIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgQTxzdWI+MjxcL3N1Yj5cdWM2NDAmbmJzcDtCPHN1Yj4yPFwvc3ViPiBcdWI0ZjFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MTVcdWJiMzhcdWM3NzRcdWFjMDAgXHViZDg4XHViN2VjXHVjNTdjXHVkNTYwIEFcdWI2MTBcdWIyOTQgQlx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YzVlY1x1YjdlYyBcdWQ1NzRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTYwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWNkOWNcdWI4MjVcdWI0MThcdWJhNzQgXHViNDE4XHVhY2UwIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLikgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTcwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPVkVaIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBwbGF5aW5nIGEgZ2FtZS4gTWlya28gaXMgdGhlIGdhbWUgbWFzdGVyLCBhbmQgU2xhdmtvIGlzIHRoZSBwbGF5ZXIuIFNsYXZrbyBoYXMgYSBoZWFkYmFuZCBvdmVyIGhpcyBleWVzLCBzbyBoZSBkb2VzbiZyc3F1bzt0IHNlZSB3aGF0IE1pcmtvIGlzIGRvaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBpcyBwbGF5ZWQgd2l0aCBOIGN1cHMgbnVtYmVyZWQgMSB0aHJvdWdoIE4uIEF0IHRoZSBzdGFydCBvZiB0aGUgZ2FtZSBNaXJrbyBwdXRzIGEgYmFsbCBpbiBvbmUgb2YgdGhlIGN1cHMgKFNsYXZrbyBkb2VzbiZyc3F1bzt0IGtub3cgd2hpY2ggb25lKS4gVGhlbiwgaW4gb25lIHN0ZXAsIFNsYXZrbyBzYXlzIGEgbGV0dGVyLCAmIzM5O0EmIzM5OyBvciAmIzM5O0ImIzM5Oy4gRWFjaCB0aW1lIFNsYXZrbyBzYXlzIGEgbGV0dGVyLCBNaXJrbyB0YWtlcyB0aGUgYmFsbCBhbmQgcHV0cyBpdCBpbiBvbmUgY3VwIChwb3NzaWJseSB0aGUgc2FtZSBjdXAgaGUgdG9vayBpdCBmcm9tKS4gVGhlIGN1cCBpbnRvIHdoaWNoIE1pcmtvIHB1dHMgdGhlIGJhbGwgaXMgdW5pcXVlbHkgZGV0ZXJtaW5lZCBieSB0aGUgY3VycmVudCBwb3NpdGlvbiBvZiB0aGUgY3VwIGFuZCB0aGUgU2xhdmtvJnJzcXVvO3MgbGV0dGVyLiBUaGF0IGlzLCBpZiB0aGUgYmFsbCBpcyBpbiB0aGUgY3VwIEssIGl0IGlzIG1vdmVkIHRvIGVpdGhlciBjdXAgQTxzdWI+azxcL3N1Yj4gb3IgQjxzdWI+azxcL3N1Yj4gKHRoZXNlIG51bWJlcnMgYXJlIHByZWRldGVybWluZWQgYW5kIFNsYXZrbyBrbm93cyB0aGVtKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2xhdmtvJiMzOTtzIHRhc2sgaXMgdG8gbW92ZSB0aGUgYmFsbCBpbnRvIGN1cCAxLCByZWdhcmRsZXNzIG9mIHdoZXJlIE1pcmtvIHB1dCB0aGUgYmFsbCBpbml0aWFsbHkuIFdyaXRlIGEgcHJvZ3JhbSB3aGljaCBmaW5kcyBhbnkgc2VxdWVuY2Ugb2YgbGV0dGVycyB0aGF0IFNsYXZrbyBoYXMgdG8gc2F5IGluIG9yZGVyIHRvIG1vdmUgdGhlIGJhbGwgaW50byBjdXAgMS4gVGhlIHNlcXVlbmNlIG11c3QgYmUgc2hvcnRlciB0aGFuIDEwIDAwMCBsZXR0ZXJzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyA1MDApLCB0aGUgbnVtYmVyIG9mIGN1cHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgdGhlIG51bWJlcnMgQTxzdWI+azxcL3N1Yj4gYW5kIEI8c3ViPms8XC9zdWI+IGZvciBvbmUgY3VwLiBUaGUgZmlyc3Qgb2YgdGhlc2UgbGluZXMgY29udGFpbnMgQTxzdWI+MTxcL3N1Yj4gYW5kIEI8c3ViPjE8XC9zdWI+LCB0aGUgc2Vjb25kIEE8c3ViPjI8XC9zdWI+IGFuZCBCPHN1Yj4yPFwvc3ViPiBldGMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IGZvciBpbnB1dCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IHRoZSBzb2x1dGlvbiwgYWx0aG91Z2ggcG9zc2libHkgbm90IHVuaXF1ZSwgd2lsbCBleGlzdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNlcXVlbmNlIG9mIEEmIzM5O3MgYW5kIEImIzM5O3MgU2xhdmtvIHNob3VsZCBzYXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Final Exam #1 2번

  • 문제를 번역한 사람: author6
  • 빠진 조건을 찾은 사람: koosaga