시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 552 488 455 90.099%

문제

동전게임은 주로 두 사람이 함께 즐기는 게임이다. 이 중 3-동전게임은 여러 명이 할 수 있는 게임이다. 각 사람은 각각 3-동전수열 중 하나를 선택한다. 3-동전수열이란 앞 뒤 앞과 같은 수열이고, 8가지(뒤뒤뒤,뒤뒤앞,뒤앞뒤,뒤앞앞,앞뒤뒤,앞뒤앞,앞앞뒤,앞앞앞)가 있다.

이제 심판은 동전 1개를 40번 던진다. 그 다음 심판은 동전이 앞인지 뒤인지를 던진 순서대로 종이에 적는다. 그 다음 3-동전수열이 각각 몇 번씩 나왔는지 기록한다. 가장 많이 나온 수열을 선택한 사람이 이긴다.

동전 40번 던진 결과가 주어졌을 때, 3-동전수열이 각각 몇 번 나왔는지를 출력하는 프로그램을 작성하시오. 예를 들어, 40개의 동전이 모두 앞면일 경우 앞앞앞은 38번 나타난다.

입력

첫째 줄에 테스트 케이스의 개수 P(1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 동전을 40번 던진 결과가 주어진다. 이때, 앞면은 H로, 뒷면은 T로 표현한다. 

출력

각 테스트 케이스마다 3-동전수열이 몇 번 나타났는지를 출력한다. 뒤뒤뒤, 뒤뒤앞, 뒤앞뒤, 뒤앞앞, 앞뒤뒤, 앞뒤앞, 앞앞뒤, 앞앞앞 순서대로 공백으로 구분해서 출력한다.

예제 입력 1

4
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
HHTTTHHTTTHTHHTHHTTHTTTHHHTHTTHTTHTTTHTH
HTHTHHHTHHHTHTHHHHTTTHTTTTTHHTTTTHTHHHHT

예제 출력 1

0 0 0 0 0 0 0 38
38 0 0 0 0 0 0 0
4 7 6 4 7 4 5 1
6 3 4 5 3 6 5 6
W3sicHJvYmxlbV9pZCI6IjI2ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWM4MDQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWM4MDRcdWFjOGNcdWM3ODRcdWM3NDAgXHVjOGZjXHViODVjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVkNTY4XHVhZWQ4IFx1Yzk5MFx1YWUzMFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWM5MTEgMy1cdWIzZDlcdWM4MDRcdWFjOGNcdWM3ODRcdWM3NDAgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc3NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NDAgXHVhYzAxXHVhYzAxIDMtXHViM2Q5XHVjODA0XHVjMjE4XHVjNWY0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiAzLVx1YjNkOVx1YzgwNFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc4MCZuYnNwO1x1YzU1ZSBcdWI0YTQgXHVjNTVlXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NzRcdWFjZTAsIDhcdWFjMDBcdWM5YzAoXHViNGE0XHViNGE0XHViNGE0LFx1YjRhNFx1YjRhNFx1YzU1ZSxcdWI0YTRcdWM1NWVcdWI0YTQsXHViNGE0XHVjNTVlXHVjNTVlLFx1YzU1ZVx1YjRhNFx1YjRhNCxcdWM1NWVcdWI0YTRcdWM1NWUsXHVjNTVlXHVjNTVlXHViNGE0LFx1YzU1ZVx1YzU1ZVx1YzU1ZSlcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVjMmVjXHVkMzEwXHVjNzQwIFx1YjNkOVx1YzgwNCAxXHVhYzFjXHViOTdjIDQwXHViYzg4IFx1YjM1OFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMyZWNcdWQzMTBcdWM3NDAgXHViM2Q5XHVjODA0XHVjNzc0IFx1YzU1ZVx1Yzc3OFx1YzljMCBcdWI0YTRcdWM3NzhcdWM5YzBcdWI5N2MgXHViMzU4XHVjOWM0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIDMtXHViM2Q5XHVjODA0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YWMwMVx1YWMwMSBcdWJhODcgXHViYzg4XHVjNTI5IFx1YjA5OFx1YzY1NFx1YjI5NFx1YzljMCBcdWFlMzBcdWI4NWRcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NzQgXHViMDk4XHVjNjI4IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1Yzc3NFx1YWUzNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVjODA0IDQwXHViYzg4IFx1YjM1OFx1YzljNCBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgMy1cdWIzZDlcdWM4MDRcdWMyMThcdWM1ZjRcdWM3NzQgXHVhYzAxXHVhYzAxIFx1YmE4NyBcdWJjODggXHViMDk4XHVjNjU0XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA0MFx1YWMxY1x1Yzc1OCBcdWIzZDlcdWM4MDRcdWM3NzQgXHViYWE4XHViNDUwIFx1YzU1ZVx1YmE3NFx1Yzc3YyBcdWFjYmRcdWM2YjAgXHVjNTVlXHVjNTVlXHVjNTVlXHVjNzQwIDM4XHViYzg4IFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggUCgxICZsZTsgUCAmbGU7IDEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWIzZDlcdWM4MDRcdWM3NDQgNDBcdWJjODggXHViMzU4XHVjOWM0IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNTVlXHViYTc0XHVjNzQwIEhcdWI4NWMsIFx1YjRiN1x1YmE3NFx1Yzc0MCBUXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAzLVx1YjNkOVx1YzgwNFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWJhODcgXHViYzg4IFx1YjA5OFx1ZDBjMFx1YjBhY1x1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjRhNFx1YjRhNFx1YjRhNCwgXHViNGE0XHViNGE0XHVjNTVlLCBcdWI0YTRcdWM1NWVcdWI0YTQsIFx1YjRhNFx1YzU1ZVx1YzU1ZSwgXHVjNTVlXHViNGE0XHViNGE0LCBcdWM1NWVcdWI0YTRcdWM1NWUsIFx1YzU1ZVx1YzU1ZVx1YjRhNCwgXHVjNTVlXHVjNTVlXHVjNTVlIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVubmV5IEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlBlbm5leSZyc3F1bztzIGdhbWUgaXMgYSBzaW1wbGUgZ2FtZSB0eXBpY2FsbHkgcGxheWVkIGJ5IHR3byBwbGF5ZXJzLiBPbmUgdmVyc2lvbiBvZiB0aGUgZ2FtZSBjYWxscyBmb3IgZWFjaCBwbGF5ZXIgdG8gY2hvb3NlIGEgdW5pcXVlIHRocmVlLWNvaW4gc2VxdWVuY2Ugc3VjaCBhcyBIRUFEUyBUQUlMUyBIRUFEUyAoSFRIKS4gQSBmYWlyIGNvaW4gaXMgdG9zc2VkIHNlcXVlbnRpYWxseSBzb21lIG51bWJlciBvZiB0aW1lcyB1bnRpbCBvbmUgb2YgdGhlIHR3byBzZXF1ZW5jZXMgYXBwZWFycy4gVGhlIHBsYXllciB3aG8gY2hvc2UgdGhlIGZpcnN0IHNlcXVlbmNlIHRvIGFwcGVhciB3aW5zIHRoZSBnYW1lLjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCB5b3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdGhhdCBpbXBsZW1lbnRzIGEgdmFyaWF0aW9uIG9uIHRoZSBQZW5uZXkgR2FtZS4gWW91IHdpbGwgcmVhZCBhIHNlcXVlbmNlIG9mIDQwIGNvaW4gdG9zc2VzIGFuZCBkZXRlcm1pbmUgaG93IG1hbnkgdGltZXMgZWFjaCB0aHJlZS1jb2luIHNlcXVlbmNlIGFwcGVhcnMuIE9idmlvdXNseSB0aGVyZSBhcmUgZWlnaHQgc3VjaCB0aHJlZS1jb2luIHNlcXVlbmNlczogVFRULCBUVEgsIFRIVCwgVEhILCBIVFQsIEhUSCwgSEhUIGFuZCBISEguIFNlcXVlbmNlcyBtYXkgb3ZlcmxhcC4gRm9yIGV4YW1wbGUsIGlmIGFsbCA0MCBjb2luIHRvc3NlcyBhcmUgaGVhZHMsIHRoZW4gdGhlIHNlcXVlbmNlIEhISCBhcHBlYXJzIDM4IHRpbWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgMiBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciBOLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIHNlcXVlbmNlIG9mIDQwIGNvaW4gdG9zc2VzLiBFYWNoIHRvc3MgaXMgcmVwcmVzZW50ZWQgYXMgYW4gdXBwZXIgY2FzZSBIIG9yIGFuIHVwcGVyIGNhc2UgVCwgZm9yIGhlYWRzIG9yIHRhaWxzLCByZXNwZWN0aXZlbHkuIFRoZXJlIHdpbGwgYmUgbm8gc3BhY2VzIG9uIGFueSBpbnB1dCBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIG51bWJlciBvZiBvY2N1cnJlbmNlcyBvZiBlYWNoIHRocmVlLWNvaW4gc2VxdWVuY2UsIGluIHRoZSBvcmRlciBzaG93biBhYm92ZSwgd2l0aCBhIHNwYWNlIGJldHdlZW4gZWFjaCBvbmUuIFRoZXJlIHNob3VsZCBiZSBhIHRvdGFsIG9mIDkgc3BhY2Ugc2VwYXJhdGVkIGRlY2ltYWwgaW50ZWdlcnMgb24gZWFjaCBvdXRwdXQgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > Regionals > North America > Greater New York Region > 2010 Greater New York Programming Contest A번