TJANDRAS - Tjandra 19th birthday (EASY)

This day (7 February 2013) is my 19th birthday Laughing So, I want to celebrate it on SPOJ by making this EASY puzzle problem.

This game/puzzle is about matches, given n matches, your task is to arrange the matches (not necessarily all) such that number of rectangle (any size) is maximum.

Input

First line there is an integer T100 then T lines follow, each line contain an integer n<1.000.000.000.

Output

For each test case, output required answer (maximum number of rectangles)

Example

Input:
5
3
4
8
12
15

Output:
0
1
3
9
12

Explanation

-->First test case: No rectangle can be formed with only 3 matches

-->Second test case: Only one rectangle can be formed with 4 mathes

-->Third test case:

there are max 3 rectangles (2 size 1x1, 1 size 2x1) can be formed with number of matches<=8, here is one of the mathes formation:

Case 3

-->Fourth test case:

there are max 9 rectangles (4 size 1x1, 2 size 2x1, 2 size 1x2, 1 size 2x2) can be formed with number of matches <=12, here is one of the formation:

case 4

-->Fifth test case:

there are max 12 rectangles (5 size 1x1, 3 size 2x1, 1 size 3x1, 2 size 1x2, 1 size 2x2) can be formed with number of matches <=15, here is one of the formation:

case 5

Information

Time limit≈150x my program speed, Enjoy this birthday party game, I set this problem such that semi naive solution will pass..

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-02-07
Time limit:3.263s
Source limit:19000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Just Watch This Video! I Uploaded it 1 year ago

hide comments
2013-05-29 06:17:45 Mostafa 36a2
another discussion can break the problem by using the 0.5*0.5 rectangles and so on
assume 6 sticks ... you can form 9 rectangles ...
take 10 sticks ---they can make 100 rectangles using 0.25*0.25 squares !!
So What Do you think about it?
may be you should concentrate the problem on (no any size) an 1*1 at least
2013-05-28 15:19:01 Mostafa 36a2
Before Try to Submit i have a question
is the answer for 13 is 10 ?
i hope so, else there is a little mistake in the problem.

Last edit: 2013-05-29 15:30:07
2013-05-18 20:26:29 abdou_93
please any test caes ..!!
@Tjandra..any small test case..to found my wrong .
Ans: Check for all n<1000 with brute-force program, there are some error in some cases (answer is incorrect because it's not optimal/maximum, there's other formation with more number of rectangles)

@Tjandra.Thank you very much..:D

Last edit: 2013-05-19 17:51:59
2013-05-18 19:51:44 abdou_93
please @Tjandra ..can you look at my submission (id->9294435)...
thanks :D
Ans: Be careful using fast I/O like putchar, Time limit is not strict, you can use regular I/O first.. Here is your first 5 lines of your output:
ÿùú÷÷ø0ûüÿ
ÿùø0ûýÿþøú
þ0÷÷0ûü÷þù
1827174587
ÿý÷÷0üþþü

@Tjandra..still wrong ..please .. now what is the wrong?(id>>9294509)

Ans: your output is wrong for some test case (also small test case).. so I recommend to build brute-force program and compare the result for small output ;-)

Last edit: 2013-05-18 20:50:09
2013-04-14 21:44:37 Hardik Rakholiya
it says wrong answer though for all the no i entered i feel it gave right output on my computer... i used long long int for all the variables... so plz help!!
Ans: Your logic is wrong..

Last edit: 2013-04-15 11:38:04
2013-02-11 07:10:36 Goldie
Happy Birthday bro :) :) .. Will try ur birthday puzzle ;)
2013-02-11 05:19:30 Kevin Sebastian
will long long int suffice
Ans: Yes of course..

Last edit: 2013-02-11 06:09:37
2013-02-09 19:33:22 :C++:
Happy b'dy... Tjandra
2013-02-09 16:01:16 Francky
Python3 feasible check : OK.
Good problem ;-) Thanks for it.
2013-02-09 08:28:24 Thotsaphon Thanatipanonda
Happy Birthday, Tjandra!!
and also Happy Chinese New Year too :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.