시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 415 143 104 41.600%

문제

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

네온 사인은 총 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+XHViMTI0XHVjNjI4IFx1YzBhY1x1Yzc3OFx1Yzc0MCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVjNmQwXHVjNzU4IFx1YjQ1OFx1YjgwOFx1Yjk3YyBcdWI1MzBcdWI3N2MgXHVjYzBkXHVkNjAwXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWNkMWQgTiAqIChOLTEpXHVhYzFjXHVjNzU4IFx1YzU3Y1x1YWQxMSBcdWQyOWNcdWJlMGNcdWFjMDAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzU3Y1x1YWQxMSBcdWQyOWNcdWJlMGNcdWIyOTQgXHViNDUwIFx1YWMwMFx1YzljMCBcdWMwYzkoXHViZTY4XHVhYzA0XHVjMGM5XHVhY2ZjIFx1ZDMwY1x1Yjc4MFx1YzBjOSlcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWQ3NjBcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWQ1NWMgXHVjMGJjXHVhYzAxXHVkNjE1XHViOWNjIFx1YmQ4OFx1Yzc0NCBcdWJjMWRcdWQ3ODhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViY2MwXHVjNzQwIFx1YzBjOVx1YzBjMVx1Yzc3NCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVjMTFjXHViODVjIFx1Yzc3NFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YjJlOFx1YzBjOSBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzU0Y1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OCBcdWIxMjRcdWM2MjggXHVjMGFjXHVjNzc4XHVjNWQwXHViMjk0IFx1YjJlOFx1YzBjOSBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM3ODhcdWIyZTQuICgxLCAzLCA1KVx1YzY0MCAoMiwgMywgNCk8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9uZW9uc2lnbi5wbmdcIiBzdHlsZT1cImhlaWdodDozMTJweDsgd2lkdGg6MzQ0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMTI0XHVjNjI4IFx1YzBhY1x1Yzc3OFx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjMjE4XHVjNjQwIFx1YWMwMSBcdWM1N2NcdWFkMTEgXHVkMjljXHViZTBjXHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIyZThcdWMwYzkgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDMgJmxlOyBOICZsZTsgMSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE4tMVx1YWMxY1x1Yzc1OCBcdWFjMDEgXHVjNTdjXHVhZDExIFx1ZDI5Y1x1YmUwY1x1Yzc1OCBcdWMwYzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjOTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWYyZFx1YzlkM1x1YzgxMCBpXHVjNjQwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWQyOWNcdWJlMGNcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzc0IGkrMVx1YmM4OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWFjZmMgXHVjNWYwXHVhY2IwXHViNDFjIFx1ZDI5Y1x1YmUwY1x1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmU2OFx1YWMwNFx1YzBjOVx1Yzc0MCAxLCBcdWQzMGNcdWI3ODBcdWMwYzlcdWM3NDAgMFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjJlOFx1YzBjOSBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTmVvbiBTaWduIiwiZGVzY3JpcHRpb24iOiI8cD5KdW5nSGV1bSByZWNlbnRseSBvcGVuZWQgYSByZXN0YXVyYW50IGNhbGxlZCAmIzM5O1RyaWFuZ2xlJiMzOTsgYW5kIGhhcyBvcmRlcmVkIHRoZSBmb2xsb3dpbmcgbmVvbiBzaWduIGZvciBoaXMgcmVzdGF1cmFudC4gVGhlIG5lb24gc2lnbiBoYXMgTiBjb3JuZXJzIHBvc2l0aW9uZWQgb24gdGhlIGNpcmN1bWZlcmVuY2Ugb2YgYSBjaXJjbGUsIGFuZCBOKihOLTEpXC8yIGx1bWlub3VzIHR1YmVzIHRoYXQgY29ubmVjdCB0aGUgY29ybmVycy4gVGhlcmUgYXJlIG9ubHkgdHdvIGNvbG9ycyBmb3IgbHVtaW5vdXMgdHViZXMsIHJlZCBhbmQgYmx1ZS48XC9wPlxyXG5cclxuPHA+SnVuZ0hldW0gd2FudHMgdGhlIHNpZ24gdG8gc2hvdyBvbmx5IG9uZSBzaGFwZSBvZiBhIHRyaWFuZ2xlIGF0IGEgdGltZSwgd2hvc2UgbHVtaW5vdXMgdHViZXMgY29sb3JzIGFyZSBzYW1lLCBjb250aW51b3VzbHkuIEhlbmNlLCBoZSB3YW50cyB0byBrbm93IHRoZSBudW1iZXIgb2YgdW5pLWNvbG9yIHRyaWFuZ2xlcy48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBmb2xsb3dpbmcgbmVvbiBzaWduIGhhcyBvbmx5IHR3byB1bmktY29sb3IgdHJpYW5nbGVzICgxLCAzLCA1KSBhbmQgKDIsIDMsIDQpLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL25lb25zaWduLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMxMnB4OyB3aWR0aDozNDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbnVtYmVyIG9mIGNvcm5lcnMgb2YgdGhlIG5lb24gc2lnbiBhbmQgdGhlIGNvbG9ycyBvZiB0aGUgbHVtaW5vdXMgdHViZXMgaW4gdGhlIHNpZ24sIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBudW1iZXIgb2YgdW5pLWNvbG9yIHRyaWFuZ2xlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYW4gaW50ZWdlciBOICgzICZsZTsmbmJzcDtOICZsZTsmbmJzcDsxLDAwMCksIHdoaWNoIHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiBjb3JuZXJzIG9mIHRoZSBuZW9uIHNpZ24uIEluIHRoZSBmb2xsb3dpbmcgTi0xIGxpbmVzLCB0aGUgaW5mb3JtYXRpb24gYWJvdXQgdGhlIGNvbG9yIG9mIHRoZSBsdW1pbm91cyB0dWJlcyBhcmUgZ2l2ZW4uIEZvciB0aGUgaS10aCBsaW5lIG9mIHRoZXNlIGxpbmVzLCB0aGUgY29sb3IgaW5mb3JtYXRpb24gb2YgdGhlIGx1bWlub3VzIHR1YmVzIHRoYXQgY29ubmVjdCBjb3JuZXIgaSB0byBjb3JuZXJzIGZyb20gY29ybmVyIGkrMSB0byBOIGFyZSBnaXZlbi4gTm90ZSB0aGF0IHRoZSBjb2xvciByZWQgaXMgcmVwcmVzZW50ZWQgYXMgMSBhbmQgdGhlIGNvbG9yIGJsdWUgaXMgcmVwcmVzZW50ZWQgYXMgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiB1bmktY29sb3IgdHJpYW5nbGVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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