시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 417 159 105 42.169%

문제

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

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

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

예를 들어, 아래 네온 사인에는 단색 삼각형이 두 개 있다. (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+XHViMTI0XHVjNjI4IFx1YzBhY1x1Yzc3OFx1Yzc0MCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NzQgXHVjNmQwXHVjNzU4IFx1YjQ1OFx1YjgwOFx1Yjk3YyBcdWI1MzBcdWI3N2MgXHVjYzBkXHVkNjAwXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWNkMWQgTiAqIChOLTEpIFwvIDJcdWFjMWNcdWM3NTggXHVjNTdjXHVhZDExIFx1ZDI5Y1x1YmUwY1x1YWMwMCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNTdjXHVhZDExIFx1ZDI5Y1x1YmUwY1x1YjI5NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YzBjOShcdWJlNjhcdWFjMDRcdWMwYzlcdWFjZmMgXHVkMzBjXHViNzgwXHVjMGM5KVx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1ZDc2MFx1Yzc3NFx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1ZDU1YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWI5Y2MgXHViZDg4XHVjNzQ0IFx1YmMxZFx1ZDc4OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjYzBcdWM3NDAgXHVjMGM5XHVjMGMxXHVjNzc0IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViMmU4XHVjMGM5IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjNTRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNTQ0XHViNzk4IFx1YjEyNFx1YzYyOCBcdWMwYWNcdWM3NzhcdWM1ZDBcdWIyOTQgXHViMmU4XHVjMGM5IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1Yzc4OFx1YjJlNC4gKDEsIDMsIDUpXHVjNjQwICgyLCAzLCA0KTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL25lb25zaWduLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMxMnB4OyB3aWR0aDozNDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWIxMjRcdWM2MjggXHVjMGFjXHVjNzc4XHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWMyMThcdWM2NDAgXHVhYzAxIFx1YzU3Y1x1YWQxMSBcdWQyOWNcdWJlMGNcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjJlOFx1YzBjOSBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE4oMyAmbGU7IE4gJmxlOyAxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTi0xXHVhYzFjXHVjNzU4IFx1YWMwMSBcdWM1N2NcdWFkMTEgXHVkMjljXHViZTBjXHVjNzU4IFx1YzBjOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MDRcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwIGlcdWM2NDAgXHVjNWYwXHVhY2IwXHViNDFjIFx1ZDI5Y1x1YmUwY1x1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzQgaSsxXHViYzg4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkMjljXHViZTBjXHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZTY4XHVhYzA0XHVjMGM5XHVjNzQwIDEsIFx1ZDMwY1x1Yjc4MFx1YzBjOVx1Yzc0MCAwXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViMmU4XHVjMGM5IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5MDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZW9uIFNpZ24iLCJkZXNjcmlwdGlvbiI6IjxwPkp1bmdIZXVtIHJlY2VudGx5IG9wZW5lZCBhIHJlc3RhdXJhbnQgY2FsbGVkICYjMzk7VHJpYW5nbGUmIzM5OyBhbmQgaGFzIG9yZGVyZWQgdGhlIGZvbGxvd2luZyBuZW9uIHNpZ24gZm9yIGhpcyByZXN0YXVyYW50LiBUaGUgbmVvbiBzaWduIGhhcyBOIGNvcm5lcnMgcG9zaXRpb25lZCBvbiB0aGUgY2lyY3VtZmVyZW5jZSBvZiBhIGNpcmNsZSwgYW5kIE4qKE4tMSlcLzIgbHVtaW5vdXMgdHViZXMgdGhhdCBjb25uZWN0IHRoZSBjb3JuZXJzLiBUaGVyZSBhcmUgb25seSB0d28gY29sb3JzIGZvciBsdW1pbm91cyB0dWJlcywgcmVkIGFuZCBibHVlLjxcL3A+XHJcblxyXG48cD5KdW5nSGV1bSB3YW50cyB0aGUgc2lnbiB0byBzaG93IG9ubHkgb25lIHNoYXBlIG9mIGEgdHJpYW5nbGUgYXQgYSB0aW1lLCB3aG9zZSBsdW1pbm91cyB0dWJlcyBjb2xvcnMgYXJlIHNhbWUsIGNvbnRpbnVvdXNseS4gSGVuY2UsIGhlIHdhbnRzIHRvIGtub3cgdGhlIG51bWJlciBvZiB1bmktY29sb3IgdHJpYW5nbGVzLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyBuZW9uIHNpZ24gaGFzIG9ubHkgdHdvIHVuaS1jb2xvciB0cmlhbmdsZXMgKDEsIDMsIDUpIGFuZCAoMiwgMywgNCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbmVvbnNpZ24ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzEycHg7IHdpZHRoOjM0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBudW1iZXIgb2YgY29ybmVycyBvZiB0aGUgbmVvbiBzaWduIGFuZCB0aGUgY29sb3JzIG9mIHRoZSBsdW1pbm91cyB0dWJlcyBpbiB0aGUgc2lnbiwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIG51bWJlciBvZiB1bmktY29sb3IgdHJpYW5nbGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIE4gKDMgJmxlOyZuYnNwO04gJmxlOyZuYnNwOzEsMDAwKSwgd2hpY2ggcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIGNvcm5lcnMgb2YgdGhlIG5lb24gc2lnbi4gSW4gdGhlIGZvbGxvd2luZyBOLTEgbGluZXMsIHRoZSBpbmZvcm1hdGlvbiBhYm91dCB0aGUgY29sb3Igb2YgdGhlIGx1bWlub3VzIHR1YmVzIGFyZSBnaXZlbi4gRm9yIHRoZSBpLXRoIGxpbmUgb2YgdGhlc2UgbGluZXMsIHRoZSBjb2xvciBpbmZvcm1hdGlvbiBvZiB0aGUgbHVtaW5vdXMgdHViZXMgdGhhdCBjb25uZWN0IGNvcm5lciBpIHRvIGNvcm5lcnMgZnJvbSBjb3JuZXIgaSsxIHRvIE4gYXJlIGdpdmVuLiBOb3RlIHRoYXQgdGhlIGNvbG9yIHJlZCBpcyByZXByZXNlbnRlZCBhcyAxIGFuZCB0aGUgY29sb3IgYmx1ZSBpcyByZXByZXNlbnRlZCBhcyAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHVuaS1jb2xvciB0cmlhbmdsZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: cs71107