Submit | All submissions | Best solutions | Back to list |
TJANDRAS - Tjandra 19th birthday (EASY) |
This day (7 February 2013) is my 19th birthday 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 T≤100 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:
-->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:
-->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:
Information
Time limit≈150x my program speed, Enjoy this birthday party game, I set this problem such that semi naive solution will pass..
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 :) |