comkiwer- 삼각형만들기2 > 문제은행 : 정보올림피아드&알고리즘



3278 : 삼각형만들기2

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
6 회   
시도횟수
17 회   

문제

길이가 일정한 성냥개비 N개가 주어질 때 이를 이용하여 만들수 있는 삼각형의 개수는 모두 몇가지일까?

 

"jungol 3277 삼각형 만들기1"를 힘들게 해결한 정원이에게 이제 더 어려운 문제가 주어졌다.

 

성냥개비의 개수가 무려 2 * 10​10 (2백억)개 까지 입력된다고 한다.

너무 어렵다고 느껴진 정원이가 여러분에게 도움을 요청하고 있다.

정원이를 도와 문제를 해결해 보자.

 

[제약 사항]

1. 주어진 N개의 성냥개비를 모두 사용해야만 한다.

2. 만들어진 삼각형을 회전하거나 뒤집었을때 이전의 모양과 같다면 한 가지 경우로 본다.

3. 문제당 1 ~ 100개의 테스트 케이스가 주어진다.​

입력형식

첫 행에 테스트 케이스의 수 T( 1 ≤ T ≤ 100)가 입력된다. 이어서 T개의 행에 성냥개비의 수 N 이 입력된다. ( 1≤ N≤ 20,000,000,000)

출력형식

T개의 행에 각 케이스에 대한 답을 출력한다.

입력 예

5
4
17
123
5138
923456

출력 예

0
8
331
549980
17766062165

출처

comkiwer

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP