시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 559 147 102 31.677%

문제

a와 b로만 이루어진 문자열 s이 있다. 그룹은 같은 글자로 이루어진 가장 긴 연속 부분 문자열이다. 길이가 2 이상인 s의 모든 그룹 g는 제거할 수(뽑을 수) 있고, 남은 왼쪽 부분과 오른쪽 부분을 연결해서 새 문자열을 만들 수 있다. 이러한 과정은 문자열이 빈 문자열이 되거나, 길이가 2 이상인 그룹이 없을 때 까지 계속한다.

예를 들어, s = babbbaaabb일 때, s에는 그룹이 다섯 개 있다. s는 다음과 같은 단계를 거쳐서 빈 문자열로 바꿀 수 있다. (밑 줄이 그어져 있는 그룹이 뽑히는 그룹)

babbbaaabb → baaaabb → bbb → 빈 문자열

하지만, 아래와 같은 단계를 거친다면, 빈 문자열로 바꿀 수 없다.

babbbaaabb → babbbaaa → baaaa → b

문자열이 주어졌을 때, 적절한 과정을 거쳐 빈 문자로 바꿀 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 a와 b로 이루어진 문자열로 이루어져 있다. 문자열의 길이는 1보다 크거나 같고, 25보다 작거나 같다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문자열을 빈 문자열로 바꿀 수 있으면 1을, 없으면 0을 출력한다. 

예제 입력 1

3
babbbaaabb
aabbaabb
abab

예제 출력 1

1
1
0
W3sicHJvYmxlbV9pZCI6Ijg5MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHViZjUxXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5hXHVjNjQwIGJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCBzXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOGY5XHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWFlMDBcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWYwXHVjMThkIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1YWMwMCAyIFx1Yzc3NFx1YzBjMVx1Yzc3OCBzXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFkZjhcdWI4ZjkgZ1x1YjI5NCBcdWM4MWNcdWFjNzBcdWQ1NjAgXHVjMjE4KFx1YmY1MVx1Yzc0NCBcdWMyMTgpIFx1Yzc4OFx1YWNlMCwgXHViMGE4XHVjNzQwIFx1YzY3Y1x1Y2FiZCBcdWJkODBcdWJkODRcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NzRcdWMxMWMgXHVjMGM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNmY1x1YzgxNVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWI0MThcdWFjNzBcdWIwOTgsIFx1YWUzOFx1Yzc3NFx1YWMwMCAyIFx1Yzc3NFx1YzBjMVx1Yzc3OCBcdWFkZjhcdWI4ZjlcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBzID0gYmFiYmJhYWFiYlx1Yzc3YyBcdWI1NGMsIHNcdWM1ZDBcdWIyOTQgXHVhZGY4XHViOGY5XHVjNzc0IFx1YjJlNFx1YzEyZiBcdWFjMWMgXHVjNzg4XHViMmU0LiBzXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViMmU4XHVhY2M0XHViOTdjIFx1YWM3MFx1Y2NkMFx1YzExYyBcdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHViYzExIFx1YzkwNFx1Yzc3NCBcdWFkZjhcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWRmOFx1YjhmOVx1Yzc3NCBcdWJmNTFcdWQ3ODhcdWIyOTQgXHVhZGY4XHViOGY5KTxcL3A+XHJcblxyXG48cD5iYTx1PmJiYjxcL3U+YWFhYmIgJnJhcnI7IGI8dT5hYWFhPFwvdT5iYiAmcmFycjsgPHU+YmJiPFwvdT4gJnJhcnI7IFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjQ8XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YWNjNFx1Yjk3YyBcdWFjNzBcdWNlNWNcdWIyZTRcdWJhNzQsIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmJhYmJiYWFhPHU+YmI8XC91PiAmcmFycjsgYmE8dT5iYmI8XC91PmFhYSAmcmFycjsgYjx1PmFhYWE8XC91PiAmcmFycjsgYjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjODAxXHVjODA4XHVkNTVjIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNjZDAgXHViZTQ4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBhXHVjNjQwIGJcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjVcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgMVx1Yzc0NCwgXHVjNWM2XHVjNzNjXHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdHJpbmcgUG9wcGluZyIsImRlc2NyaXB0aW9uIjoiPHA+V2UgYXJlIGdpdmVuIGEgc3RyaW5nIHMgb2YgdHdvIGNoYXJhY3RlcnMgJmxzcXVvO2EmcnNxdW87IGFuZCAmbHNxdW87YiZyc3F1bzsuIExldCBhIGdyb3VwIGJlIGEgbWF4aW1hbCBjb25zZWN1dGl2ZSBzdWJzdHJpbmcgb2YgdGhlIHNhbWUgY2hhcmFjdGVyLiBBbnkgZ3JvdXAgZyBvZiBzIG9mIGxlbmd0aCBhdCBsZWFzdCB0d28gY2FuIGJlIHJlbW92ZWQgKG9yIHBvcHBlZCkgYW5kIGEgbmV3IHN0cmluZyBpcyBjb25zdHJ1Y3RlZCBieSBjb25jYXRlbmF0aW5nIHRoZSByZW1haW5pbmcgbGVmdCBhbmQgcmlnaHQgc3Vic3RyaW5ncyBvZiBzLiBXZSByZXBlYXQgdGhpcyBwcm9jZXNzIHVudGlsIGVpdGhlciB0aGUgc3RyaW5nIGJlY29tZXMgdGhlIGVtcHR5IHN0cmluZyBvciB0aGVyZSBpcyBubyBtb3JlIGdyb3VwIG9mIGxlbmd0aCBhdCBsZWFzdCB0d28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBzdHJpbmcgcyA9IGJhYmJiYWFhYmIgaGFzIDUgZ3JvdXBzIGIsIGEsIGJiYiwgYWFhLCBhbmQgYmIuIFRoZSBzdHJpbmcgcyBjYW4gYmUgdHVybmVkIGludG8gdGhlIGVtcHR5IHN0cmluZyBieSBwb3BwaW5nIGdyb3VwcyBpbiB0aGUgZm9sbG93aW5nIHNlcXVlbmNlICh0aGUgdW5kZXJsaW5lZCBncm91cCBpcyB0byBiZSBwb3BwZWQgaW4gdGhlIHNlcXVlbmNlKTo8XC9wPlxyXG5cclxuPHA+YmE8dT5iYmI8XC91PmFhYWJiICZyYXJyOyBiPHU+YWFhYTxcL3U+YmIgJnJhcnI7Jm5ic3A7PHU+YmJiPFwvdT4mbmJzcDsmcmFycjsgZW1wdHkgc3RyaW5nPFwvcD5cclxuXHJcbjxwPkJ1dCB0aGUgZ3JvdXAgbWF5IG5vdCB0dXJuIHRvIGFuIGVtcHR5IHN0cmluZyBieSBhIGRpZmZlcmVudCBzZXF1ZW5jZSBvZiBwb3Agb3BlcmF0aW9uczo8XC9wPlxyXG5cclxuPHA+YmFiYmJhYWE8dT5iYjxcL3U+Jm5ic3A7JnJhcnI7IGJhPHU+YmJiPFwvdT5hYWEgJnJhcnI7IGI8dT5hYWFhPFwvdT4mbmJzcDsmcmFycjsgYjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHN0cmluZywgd3JpdGUgYSBwcm9ncmFtIHRvIGRlY2lkZSB3aGV0aGVyIHRoZSBzdHJpbmcgY2FuIGJlIHR1cm5lZCBpbnRvIHRoZSBlbXB0eSBzdHJpbmcgYnkgc29tZSBzZXF1ZW5jZSBvZiBwb3BwaW5nIG9wZXJhdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHN0cmluZyBvZiB0d28gY2hhcmFjdGVycyAmbHNxdW87YSZyc3F1bzsgYW5kICZsc3F1bztiJnJzcXVvOy4gVGhlIG1pbmltdW0gYW5kIG1heGltdW0gbGVuZ3RoIG9mIHRoZSBzdHJpbmcgaXMgMSBhbmQgMjUsIHJlc3BlY3RpdmVseS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIHNob3VsZCBjb250YWluIDAgb3IgMS4gUHJpbnQgMSBpZiB0aGUgaW5wdXQgc3RyaW5nIGNhbiBiZSB0dXJuZWQgdG8gYW4gZW1wdHkgc3RyaW5nIGJ5IGEgc2VxdWVuY2Ugb2YgcG9wcGluZyBvcGVyYXRpb25zLiBPdGhlcndpc2UgcHJpbnQgMC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2010 B번