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

문제

이 퍼즐은 m개의 검은색 원판과, n개의 흰색 원판으로 이루어진 임의의 수열(sequence)이 타원형 모양의 트랙에 배치되어 있는 구조입니다. 또 이 게임에서는 플립(flip)이라는 동작을 할 수 있는 디스크를 이용할 수 있습니다. 플립은 임의의 세 연속된 디스크를 골라 그림과 같이 회전시켜서, 가운데 디스크는 그대로고 양 끝 디스크들의 위치를 바꾸는 동작을 말합니다. (Figure 1 참고) 플립을 할 때에는 트랙 위 어느 디스크를 중심으로도 회전시킬 수 있습니다.

 

fns.png

fns2.png

m개의 검은색 원판과 n개의 흰색 원판으로 이루어진 수열이 주어질 때, 플립을 유한 번 수행하여 (Figure 2처럼) 검은색 원판은 검은색 원판끼리, 흰색 원판은 흰색 원판끼리 한 곳에 연속적으로 모여 있는 상태를 만들 수 있을지 없을지 판단하는 프로그램을 작성하세요.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스는 한 줄로 이루어져 있습니다. 처음 주어진 수는 수열의 길이(10 ≤ m+n ≤ 30)이고, 그 다음 m개의 0(흰색 디스크)과 n개의 1(검은색 디스크)로 이루어진 수열이 주어집니다.  m+n 은 10 이상 30 미만입니다. 또한 각각의 수는 공백으로 구분됩니다.

출력

각 테스트 케이스마다, 흰색과 검은색 디스크들을 분리해 낼 수 있으면 YES를, 아니면 NO를 한 줄에 출력합니다.

예제 입력 1

2
18 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1
14 1 1 0 0 1 1 1 0 0 1 1 0 1 0

예제 출력 1

YES
NO
W3sicHJvYmxlbV9pZCI6IjczNDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MGNcdWI5YmRcdWFjZmMgXHVjMmRjXHVkNTA0XHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzQgXHVkMzdjXHVjOTkwXHVjNzQwIG1cdWFjMWNcdWM3NTggXHVhYzgwXHVjNzQwXHVjMGM5IFx1YzZkMFx1ZDMxMFx1YWNmYywgblx1YWMxY1x1Yzc1OCBcdWQ3NzBcdWMwYzkgXHVjNmQwXHVkMzEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM3ODRcdWM3NThcdWM3NTggXHVjMjE4XHVjNWY0KHNlcXVlbmNlKVx1Yzc3NCBcdWQwYzBcdWM2ZDBcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1ZDJiOFx1Yjc5OVx1YzVkMCBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1Yzg3MFx1Yzc4NVx1YjJjOFx1YjJlNC4gXHViNjEwIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWNcdWIyOTQmbmJzcDtcdWQ1MGNcdWI5YmQoZmxpcClcdWM3NzRcdWI3N2NcdWIyOTQgXHViM2Q5XHVjNzkxXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVkNTBjXHViOWJkXHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMxMzggXHVjNWYwXHVjMThkXHViNDFjIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWFjZThcdWI3N2MgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWNmMWNcdWMxMWMsIFx1YWMwMFx1YzZiNFx1YjM3MCBcdWI1MTRcdWMyYTRcdWQwNmNcdWIyOTQgXHVhZGY4XHViMzAwXHViODVjXHVhY2UwIFx1YzU5MSBcdWIwNWQgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHViM2Q5XHVjNzkxXHVjNzQ0IFx1YjlkMFx1ZDU2OVx1YjJjOFx1YjJlNC4gKEZpZ3VyZSAxIFx1Y2MzOFx1YWNlMCkgXHVkNTBjXHViOWJkXHVjNzQ0IFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQmbmJzcDtcdWQyYjhcdWI3OTkgXHVjNzA0IFx1YzViNFx1YjI5MCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI5N2MgXHVjOTExXHVjMmVjXHVjNzNjXHViODVjXHViM2M0IFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJmbnMucG5nXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTJkNzM0NTctNzcxYi00YmI3LWExNTctOGQ3YTQyNDJhYjRiXC8tXC9wcmV2aWV3XC9cIiBcLz48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJmbnMyLnBuZ1wiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2NjNGM1OWMyLTg0NDYtNDU3Yy05Yjk1LTcwNGYxZTAyNmNiYVwvLVwvcHJldmlld1wvXCIgXC8+PFwvcD5cclxuXHJcbjxwPm1cdWFjMWNcdWM3NTggXHVhYzgwXHVjNzQwXHVjMGM5IFx1YzZkMFx1ZDMxMFx1YWNmYyBuXHVhYzFjXHVjNzU4IFx1ZDc3MFx1YzBjOSBcdWM2ZDBcdWQzMTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWQ1MGNcdWI5YmRcdWM3NDQgXHVjNzIwXHVkNTVjIFx1YmM4OCBcdWMyMThcdWQ1ODlcdWQ1NThcdWM1ZWMgKEZpZ3VyZSAyXHVjYzk4XHViN2ZjKSBcdWFjODBcdWM3NDBcdWMwYzkgXHVjNmQwXHVkMzEwXHVjNzQwIFx1YWM4MFx1Yzc0MFx1YzBjOSBcdWM2ZDBcdWQzMTBcdWIwN2NcdWI5YWMsIFx1ZDc3MFx1YzBjOSBcdWM2ZDBcdWQzMTBcdWM3NDAgXHVkNzcwXHVjMGM5IFx1YzZkMFx1ZDMxMFx1YjA3Y1x1YjlhYyBcdWQ1NWMgXHVhY2YzXHVjNWQwIFx1YzVmMFx1YzE4ZFx1YzgwMVx1YzczY1x1Yjg1YyBcdWJhYThcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YzljMCBcdWM1YzZcdWM3NDRcdWM5YzAgXHVkMzEwXHViMmU4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Y2M5OFx1Yzc0YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQoMTAgJmxlOyBtK24gJmxlOyAzMClcdWM3NzRcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCAwKFx1ZDc3MFx1YzBjOSBcdWI1MTRcdWMyYTRcdWQwNmMpXHVhY2ZjIG5cdWFjMWNcdWM3NTggMShcdWFjODBcdWM3NDBcdWMwYzkgXHViNTE0XHVjMmE0XHVkMDZjKVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4mbmJzcDsgbStuIFx1Yzc0MCAxMCBcdWM3NzRcdWMwYzEgMzAgXHViYmY4XHViOWNjXHVjNzg1XHViMmM4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDI5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWQ3NzBcdWMwYzlcdWFjZmMgXHVhYzgwXHVjNzQwXHVjMGM5IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1YjRlNFx1Yzc0NCBcdWJkODRcdWI5YWNcdWQ1NzQgXHViMGJjIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgWUVTXHViOTdjLCBcdWM1NDRcdWIyYzhcdWJhNzQgTk9cdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNzM0NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZsaXAgYW5kIFNoaWZ0IiwiZGVzY3JpcHRpb24iOiI8cD5UaGlzIHB1enpsZSBjb25zaXN0cyBvZiBhIHJhbmRvbSBzZXF1ZW5jZSBvZiBtIGJsYWNrIGRpc2tzIGFuZCBuIHdoaXRlIGRpc2tzIG9uIGFuIG92YWwtc2hhcGVkIHRyYWNrLCB3aXRoIGEgdHVybnN0aWxlIGNhcGFibGUgb2YgZmxpcHBpbmcgKGkuZS4sIHJldmVyc2luZykgdGhyZWUgY29uc2VjdXRpdmUgZGlza3MuIEluIEZpZ3VyZSAxLCB0aGVyZSBhcmUgOCBibGFjayBkaXNrcyBhbmQgMTAgd2hpdGUgZGlza3Mgb24gdGhlIHRyYWNrLiBZb3UgbWF5IHNwaW4gdGhlIHR1cm5zdGlsZSB0byBmbGlwIHRoZSB0aHJlZSBkaXNrcyBpbiBpdCBvciBzaGlmdCBvbmUgcG9zaXRpb24gY2xvY2t3aXNlIGZvciBlYWNoIG9mIHRoZSBkaXNrcyBvbiB0aGUgdHJhY2sgKEZpZ3VyZSAxKS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mbnMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzU2cHg7IHdpZHRoOjU4N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBnb2FsIG9mIHRoaXMgcHV6emxlIGlzIHRvIGdhdGhlciB0aGUgZGlza3Mgb2YgdGhlIHNhbWUgY29sb3IgaW4gYWRqYWNlbnQgcG9zaXRpb25zIHVzaW5nIGZsaXBzIGFuZCBzaGlmdHMuIChGaWd1cmUgMik8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mbnMyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxNnB4OyB3aWR0aDozMDJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBkZWNpZGVzIHdoZXRoZXIgYSBnaXZlbiBzZXF1ZW5jZSBjYW4gcmVhY2ggYSBnb2FsIG9yIG5vdC4gSWYgYSBnb2FsIGlzIHJlYWNoYWJsZSwgdGhlbiB3cml0ZSBhIG1lc3NhZ2UgJmxkcXVvO1lFUyZyZHF1bzs7IG90aGVyd2lzZSwgd3JpdGUgYSBtZXNzYWdlICZsZHF1bztOTyZyZHF1bzsuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKFQpIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIG9mIHRoZSBuZXh0IFQgbGluZXMgZ2l2ZXMgYSB0ZXN0IGNhc2UuIEEgdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGFuIGludGVnZXIsIHJlcHJlc2VudGluZyB0aGUgc3VtIG9mIG0gYW5kIG4sIGFuZCBhIHNlcXVlbmNlIG9mIG0rbiAwcyBhbmQgMXMsIHJlcHJlc2VudGluZyBhbiBpbml0aWFsIHNlcXVlbmNlLiBBIDAgZGVub3RlcyBhIHdoaXRlIGRpc2sgYW5kIGEgMSBkZW5vdGVzIGEgYmxhY2sgZGlzay4gVGhlIHN1bSBvZiBtIGFuZCBuIGlzIGF0IGxlYXN0IDEwIGFuZCBkb2VzIG5vdCBleGNlZWQgMzAuIFRoZXJlIGlzIGEgc3BhY2UgYmV0d2VlbiBudW1iZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIHByaW50IGVpdGhlciAmbGRxdW87WUVTJnJkcXVvOyBvciAmbGRxdW87Tk8mcmRxdW87IGZvciBlYWNoIHRlc3QgY2FzZSwgb25lIHBlciBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 E번