시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 371 123 89 41.395%

문제

시흠이는 최근에 레스토랑 "삼각형"을 오픈했고, 시흠이는 레스토랑을 상징하는 네온 사인을 주문했다.

네온 사인은 총 N개의 꼭지점이 원의 둘레를 따라 찍혀져 있다. 그리고, 총 N * (N-1)개의 야광 튜브가 꼭지점을 연결하고 있다. 야광 튜브는 두 가지 색(빨간색과 파란색)이 있다.

시흠이는 한 번에 한 삼각형만 불을 밝히려고 한다. 이 때, 삼각형의 모든 변은 색상이 같아야 하고, 꼭지점이 서로 이어져 있어야 한다. 그는 이러한 단색 삼각형의 개수를 알려고 한다.

예를 들어, 아래 네온 사인에는 단색 삼각형이 두 개 있다. (1, 3, 5)와 (2, 3, 4)

네온 사인의 꼭지점의 수와 각 야광 튜브의 색상이 주어졌을 때, 단색 삼각형의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭지점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 다음 N-1개의 각 야광 튜브의 색이 주어진다. 이 줄의 i번째 줄에는 꼭지점 i와 연결된 튜브의 색상이 i+1번 꼭지점과 연결된 튜브부터 N번까지 순서대로 주어진다. 빨간색은 1, 파란색은 0으로 주어진다.

출력

각 테스트 케이스에 대해서 단색 삼각형의 개수를 출력한다.

예제 입력 1

2
5
1 1 0 1
0 0 0
0 1
1
5
1 1 1 1
0 0 1
0 1
1

예제 출력 1

2
4
W3sicHJvYmxlbV9pZCI6Ijg5MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxMjRcdWM2MjggXHVjMGFjXHVjNzc4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyZGNcdWQ3NjBcdWM3NzRcdWIyOTQgXHVjZDVjXHVhZGZjXHVjNWQwIFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MSAmcXVvdDtcdWMwYmNcdWFjMDFcdWQ2MTUmcXVvdDtcdWM3NDQgXHVjNjI0XHVkNTA4XHVkNTg4XHVhY2UwLCBcdWMyZGNcdWQ3NjBcdWM3NzRcdWIyOTQgXHViODA4XHVjMmE0XHVkMWEwXHViNzkxXHVjNzQ0IFx1YzBjMVx1YzlkNVx1ZDU1OFx1YjI5NCBcdWIxMjRcdWM2MjggXHVjMGFjXHVjNzc4XHVjNzQ0IFx1YzhmY1x1YmIzOFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTI0XHVjNjI4IFx1YzBhY1x1Yzc3OFx1Yzc0MCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NzQgXHVjNmQwXHVjNzU4IFx1YjQ1OFx1YjgwOFx1Yjk3YyBcdWI1MzBcdWI3N2MgXHVjYzBkXHVkNjAwXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWNkMWQgTiAqIChOLTEpXHVhYzFjXHVjNzU4IFx1YzU3Y1x1YWQxMSBcdWQyOWNcdWJlMGNcdWFjMDAgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzU3Y1x1YWQxMSBcdWQyOWNcdWJlMGNcdWIyOTQgXHViNDUwIFx1YWMwMFx1YzljMCBcdWMwYzkoXHViZTY4XHVhYzA0XHVjMGM5XHVhY2ZjIFx1ZDMwY1x1Yjc4MFx1YzBjOSlcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWQ3NjBcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWQ1NWMgXHVjMGJjXHVhYzAxXHVkNjE1XHViOWNjIFx1YmQ4OFx1Yzc0NCBcdWJjMWRcdWQ3ODhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHViYWE4XHViNGUwIFx1YmNjMFx1Yzc0MCBcdWMwYzlcdWMwYzFcdWM3NzQgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM3NzRcdWM1YjRcdWM4MzggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViMjk0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWIyZThcdWMwYzkgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM1NGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OTggXHViMTI0XHVjNjI4IFx1YzBhY1x1Yzc3OFx1YzVkMFx1YjI5NCBcdWIyZThcdWMwYzkgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjNzg4XHViMmU0LiAoMSwgMywgNSlcdWM2NDAgKDIsIDMsIDQpPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbmVvbnNpZ24ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzEycHg7IHdpZHRoOjM0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjEyNFx1YzYyOCBcdWMwYWNcdWM3NzhcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFjMDEgXHVjNTdjXHVhZDExIFx1ZDI5Y1x1YmUwY1x1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmU4XHVjMGM5IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTigzICZsZTsgTiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOLTFcdWFjMWNcdWM3NTggXHVhYzAxIFx1YzU3Y1x1YWQxMSBcdWQyOWNcdWJlMGNcdWM3NTggXHVjMGM5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFmMmRcdWM5YzBcdWM4MTAgaVx1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkMjljXHViZTBjXHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc3NCBpKzFcdWJjODggXHVhZjJkXHVjOWMwXHVjODEwXHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWQyOWNcdWJlMGNcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJlNjhcdWFjMDRcdWMwYzlcdWM3NDAgMSwgXHVkMzBjXHViNzgwXHVjMGM5XHVjNzQwIDBcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWIyZThcdWMwYzkgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODkwNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5lb24gU2lnbiIsImRlc2NyaXB0aW9uIjoiPHA+SnVuZ0hldW0gcmVjZW50bHkgb3BlbmVkIGEgcmVzdGF1cmFudCBjYWxsZWQgJiMzOTtUcmlhbmdsZSYjMzk7IGFuZCBoYXMgb3JkZXJlZCB0aGUgZm9sbG93aW5nIG5lb24gc2lnbiBmb3IgaGlzIHJlc3RhdXJhbnQuIFRoZSBuZW9uIHNpZ24gaGFzIE4gY29ybmVycyBwb3NpdGlvbmVkIG9uIHRoZSBjaXJjdW1mZXJlbmNlIG9mIGEgY2lyY2xlLCBhbmQgTiooTi0xKVwvMiBsdW1pbm91cyB0dWJlcyB0aGF0IGNvbm5lY3QgdGhlIGNvcm5lcnMuIFRoZXJlIGFyZSBvbmx5IHR3byBjb2xvcnMgZm9yIGx1bWlub3VzIHR1YmVzLCByZWQgYW5kIGJsdWUuPFwvcD5cclxuXHJcbjxwPkp1bmdIZXVtIHdhbnRzIHRoZSBzaWduIHRvIHNob3cgb25seSBvbmUgc2hhcGUgb2YgYSB0cmlhbmdsZSBhdCBhIHRpbWUsIHdob3NlIGx1bWlub3VzIHR1YmVzIGNvbG9ycyBhcmUgc2FtZSwgY29udGludW91c2x5LiBIZW5jZSwgaGUgd2FudHMgdG8ga25vdyB0aGUgbnVtYmVyIG9mIHVuaS1jb2xvciB0cmlhbmdsZXMuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgZm9sbG93aW5nIG5lb24gc2lnbiBoYXMgb25seSB0d28gdW5pLWNvbG9yIHRyaWFuZ2xlcyAoMSwgMywgNSkgYW5kICgyLCAzLCA0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9uZW9uc2lnbi5wbmdcIiBzdHlsZT1cImhlaWdodDozMTJweDsgd2lkdGg6MzQ0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG51bWJlciBvZiBjb3JuZXJzIG9mIHRoZSBuZW9uIHNpZ24gYW5kIHRoZSBjb2xvcnMgb2YgdGhlIGx1bWlub3VzIHR1YmVzIGluIHRoZSBzaWduLCB3cml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgbnVtYmVyIG9mIHVuaS1jb2xvciB0cmlhbmdsZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgTiAoMyAmbGU7Jm5ic3A7TiAmbGU7Jm5ic3A7MSwwMDApLCB3aGljaCByZXByZXNlbnRzIHRoZSBudW1iZXIgb2YgY29ybmVycyBvZiB0aGUgbmVvbiBzaWduLiBJbiB0aGUgZm9sbG93aW5nIE4tMSBsaW5lcywgdGhlIGluZm9ybWF0aW9uIGFib3V0IHRoZSBjb2xvciBvZiB0aGUgbHVtaW5vdXMgdHViZXMgYXJlIGdpdmVuLiBGb3IgdGhlIGktdGggbGluZSBvZiB0aGVzZSBsaW5lcywgdGhlIGNvbG9yIGluZm9ybWF0aW9uIG9mIHRoZSBsdW1pbm91cyB0dWJlcyB0aGF0IGNvbm5lY3QgY29ybmVyIGkgdG8gY29ybmVycyBmcm9tIGNvcm5lciBpKzEgdG8gTiBhcmUgZ2l2ZW4uIE5vdGUgdGhhdCB0aGUgY29sb3IgcmVkIGlzIHJlcHJlc2VudGVkIGFzIDEgYW5kIHRoZSBjb2xvciBibHVlIGlzIHJlcHJlc2VudGVkIGFzIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgdW5pLWNvbG9yIHRyaWFuZ2xlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 H번