7
\$\begingroup\$

Write a program or function that takes as input three positive integers x, y, and a and returns or outputs the maximum number of whole a✕1 rectangles that can be packed (axis-aligned) into an x✕y rectangle. Although the result will always be an integer, the program need not give the result using an integer type; in particular, floating-point outputs are acceptable. Use of standard loopholes is forbidden. Answers are scored in bytes including the cost of non-standard compiler flags or other marks.

Sample inputs and outputs:

 x,  y,  a -> result
--------------------
 1,  1,  3 ->      0
 2,  2,  3 ->      0
 1,  6,  4 ->      1
 6,  1,  4 ->      1
 1,  6,  3 ->      2
 6,  1,  3 ->      2
 2,  5,  3 ->      2
 5,  2,  3 ->      2
 3,  3,  3 ->      3
 3,  4,  3 ->      4
 4,  3,  3 ->      4
 4,  4,  3 ->      5
 6,  6,  4 ->      8
 5,  7,  4 ->      8
 7,  5,  4 ->      8
 6,  7,  4 ->     10
 7,  6,  4 ->     10
 5,  8,  3 ->     13
 8,  5,  3 ->     13
12, 12,  8 ->     16
12, 13,  8 ->     18
13, 12,  8 ->     18
 8,  8,  3 ->     21
12, 12,  5 ->     28
13, 13,  5 ->     33

In response to a question in the comments, note that some optimal packings may not be obvious at first glance. For instance, the case x=8, y=8, and a=3 has solutions that look like this:

||||||||
||||||||
||||||||
---||---
---||---
|| ||---
||------
||------

(8 + 2 + 2 = 12 vertical placements and 2 + 3 + 4 = 9 horizontal placements gives 12 + 9 = 21 placements in total.)

\$\endgroup\$
  • \$\begingroup\$ So many links to meta... o.O \$\endgroup\$ – Leaky Nun Aug 18 '16 at 1:27
  • 1
    \$\begingroup\$ I feel like I've seen this question beforw. Lemme search. \$\endgroup\$ – xnor Aug 18 '16 at 1:39
  • 1
    \$\begingroup\$ Nice first question (even if confirmed to be duplicate)! \$\endgroup\$ – Leaky Nun Aug 18 '16 at 1:41
  • 1
    \$\begingroup\$ Not finding a dupe. I seem to remember something with fitting 1x4's, so having variable sizes would make this different. \$\endgroup\$ – xnor Aug 18 '16 at 2:13
  • 2
    \$\begingroup\$ Must the rectangles be placed axis-aligned? \$\endgroup\$ – xnor Aug 18 '16 at 2:37
8
\$\begingroup\$

Python 2, 53 bytes

lambda p,q,n:p/n*q+q/n*(p%n)-min(0,n-p%n-q%n)*(p>n<q)

Adapts the formula given in this paper, which is:

def f(p,q,n):a=p%n;b=q%n;return(p*q-[a*b,(n-a)*(n-b)][a+b>=n and p>=n and q>=n])/n
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.