{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eThis day (7 February 2013) is my 19th birthday \u003cimg title\u003d\"Laughing\" src\u003d\"CDN_BASE_URL/cecf0d34cc96ae353e52d28814cd3a7b?v\u003d1715151830\" border\u003d\"0\" alt\u003d\"Laughing\"\u003e\u0026nbsp;So, I want to celebrate\u0026nbsp;it on SPOJ by making this EASY puzzle problem.\u003c/p\u003e\r\n\u003cp\u003eThis game/puzzle is about matches, given \u003cstrong\u003en\u003c/strong\u003e matches, your task is to arrange the matches (not necessarily all) such that number of rectangle (any size) is maximum.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line there is an integer \u003cstrong\u003eT\u003c/strong\u003e\u003cspan style\u003d\"color: #222222; font-family: arial, sans-serif; font-size: small; line-height: 16px;\"\u003e≤\u003c/span\u003e100 then \u003cstrong\u003eT\u003c/strong\u003e lines follow, each line contain an integer \u003cstrong\u003en\u003c/strong\u003e\u0026lt;1.000.000.000.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case, output required answer (maximum number of rectangles)\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n3\r\n4\r\n8\r\n12\r\n15\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n1\r\n3\r\n9\r\n12\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003e--\u0026gt;First test case: No rectangle can be formed with only 3 matches\u003c/p\u003e\r\n\u003cp\u003e--\u0026gt;Second test case: Only one rectangle can be formed with 4 mathes\u003c/p\u003e\r\n\u003cp\u003e--\u0026gt;Third test case:\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"white-space:pre\"\u003e \u003c/span\u003ethere are max 3 rectangles (2 size 1x1, 1 size 2x1) can be formed with number of matches\u0026lt;\u003d8, here is one of the mathes formation:\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"white-space:pre\"\u003e \u003c/span\u003e\u003cimg title\u003d\"Case 3\" src\u003d\"CDN_BASE_URL/03cb3d94df77c32cf0fe9965ec107050?v\u003d1715151830\" alt\u003d\"Case 3\" width\u003d\"251\" height\u003d\"133\"\u003e\u003c/p\u003e\r\n\u003cp\u003e--\u0026gt;Fourth test case:\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"white-space:pre\"\u003e \u003c/span\u003ethere are max 9 rectangles (4 size 1x1, 2 size 2x1, 2 size 1x2, 1 size 2x2) can be formed with number of matches \u0026lt;\u003d12, here is one of the formation:\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"white-space:pre\"\u003e \u003c/span\u003e\u003cimg title\u003d\"case 4\" src\u003d\"CDN_BASE_URL/c4d11a5da13989157b37849aa963e93e?v\u003d1715151830\" alt\u003d\"case 4\" width\u003d\"250\" height\u003d\"254\"\u003e\u003c/p\u003e\r\n\u003cp\u003e--\u0026gt;Fifth test case:\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"white-space:pre\"\u003e \u003c/span\u003ethere 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 \u0026lt;\u003d15, here is one of the formation:\u003c/p\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"white-space:pre\"\u003e \u003c/span\u003e\u003cimg title\u003d\"case 5\" src\u003d\"CDN_BASE_URL/34f7d9ae452411391c09bdf3f7af36e6?v\u003d1715151830\" alt\u003d\"case 5\" width\u003d\"371\" height\u003d\"256\"\u003e\u003c/p\u003e\r\n\u003ch3\u003eInformation\u003c/h3\u003e\r\n\u003cp\u003eTime limit≈150x my program speed, Enjoy this birthday party game, I set this problem such that semi naive solution will pass..\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eSee also:\u003c/strong\u003e \u003ca title\u003d\"TJANDRA\" href\u003d\"https://www.spoj.com/problems/TJANDRAS/TJANDRA/\" target\u003d\"_blank\"\u003eAnother problem added by Tjandra Satria Gunawan\u003c/a\u003e\u003c/p\u003e\n\u003c/div\u003e"}}]}