SPOJ.com - Problem TRICOUNT

TRICOUNT - Counting Triangles

#ad-hoc-1

We define the LEVEL of a triangle as in the following illustrative image:

Task: Your task is very easy. All you have to do is to count all triangles in the biggest one (Level N).

Input

The first line of the input contains an integer T (T ≤ 10000) - the number of test cases and T lines follow. Each line contains an integer N (1 ≤ N ≤ 10⁶) which is the level of the triangle in that test case.

Output

For each test case, you should write a seperate line: the number of triangles in the biggest one (Level N). (All answers will fit within the range of a 64-bit integer)

Example

Input:
3
1
2
3

Output:
1
5
13

Source limit is 500 bytes.

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	archit4077sh: 2018-05-23 22:25:16 Hey i just derived a recurrence for this f(n) = 3* (f(n-1)-f(n-2)) + f(n-3) + 2 if n is even f(n) = 3* (f(n-1)-f(n-2)) + f(n-3) + 1 if n is odd with base cases f(1)=1 , f(2)=5 ,f(3)=13 Hint: Use principle of inclusion and exclusion... Last edit: 2018-05-23 22:28:19
	summer_2: 2018-05-23 19:14:11 explain the solution please? I want to know how that formula comes? Last edit: 2018-05-23 19:15:31
	shubham31: 2018-05-11 12:08:29 (n^2) + [ (n(n-1)/2] * [(3+(2*n - 1))/6], shows wrong answer... cross checked it. still no success. n(n+2)(2n+1)/8 works but obviously on calculation for n=3 gives a wrong value. (bad test cases)
	riyadhrazzaq: 2018-03-24 18:25:35 There's two version of the formula. One uses floor function , another uses odd-even condition. I've used both of them and only got AC for odd-even condition. Can anybody explain that ?
	kkislay20: 2018-03-10 08:58:48 Use the direct formula...and long long int and you are good to go.
	bradyawn: 2018-01-24 00:15:38 For those who are wondering why n = 3 is not 9, it is because triangle of not size 1 also count
	srjsunny: 2018-01-23 14:37:20 use P and C you will get triangles=n(n+2)(2n+1)/8
	vikramvarun: 2018-01-12 11:07:58 SPOJ is the worst platform to practice coding. Gives TLE in R for simple operations as well. Do the admins/moderators do any work at all? Can't they see that time limit should be adjusted according to language.
	arul_verman: 2017-12-27 10:23:03 use long long int and the formula! Perfect AC ;)
	imshreyas: 2017-12-24 13:14:16 Please make use of long long int to avoid a WA even after using the correct formula

Submit solution!

Added by:	nha.duong
Date:	2007-08-05
Time limit:	1s
Source limit:	500B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 ERL JS-RHINO NODEJS OBJC PERL6 SQLITE VB.NET
Resource:	Trần Huy Hưng