TJANDRAS - Tjandra 19th birthday (EASY)

no tags 

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


hide comments
champion812r: 2019-05-03 20:40:08

Tjandra can you help me? I dont understand why my code doesnt work. For first 30 numbers it works.

(Tjandra Satria Gunawan)(曾毅昆): 2014-06-03 20:36:49

@VenkateshP: Your solution isn't optimal, there are better configuration..

ybbkrishna: 2014-06-03 10:54:54

GREEN finally :D

VenkateshP: 2014-06-02 20:53:57

Hi @Tjandra I'm getting Wrong Answer, Can you please check at my submission(id 11692407)

Mostafa 36a2: 2013-06-01 21:44:02

YESSSS Finally GREEEN green green!!

Ashish Lavania: 2013-05-31 23:18:14

this problem is humungously tough without paper.... with a pen and paper takes a few minutes. I now truly understand the EASY tag, Tjandra

Mostafa 36a2: 2013-05-29 15:32:45

Thanks Mitch..
its clear now thet there is more than the typical arrangement .
Sorry For the spoiler .. i deleted the other wrong values;

Mitch Schwartz: 2013-05-29 14:48:46

Ok, it sounded like maybe you were questioning the wording of this problem, rather than just suggesting a new related problem.

Providing answers for test cases not given in the problem statement is (generally) a spoiler. But for your debugging, the answer you gave for 13 is correct and the other answers are too low.

Last edit: 2013-05-29 14:51:00
Mostafa 36a2: 2013-05-29 14:11:14

there is two ways to arrange
the one gives 9 rectangles for 13 sticks
and the other gives 10 .
of course i'll not try 0.25*0.25 squares
,it's just an idea.

Mitch Schwartz: 2013-05-29 09:30:54

I think it's clear from the explanation what we are meant to count, and what kinds of arrangements are allowed.

Last edit: 2013-05-29 09:44:20

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