P4904 Layout

At a certain sister school, the teachers are so “considerate” and “warm‑hearted” that they assigned a whole blackboard of homework over National Day — even Information Technology has homework. Even worse, the assignment is to make a “National Day Travel Plan” PowerPoint. (Teacher, could you be any more fake?)

However, student XHY does not know how to make a PowerPoint, so she asked the expert CYD for help. She wants to tile $N$ photos of size $4\times 3$ without overlap and without gaps into a single rectangle to use as a background image. For aesthetics, she wants the rectangle’s width and height to be as close as possible (i.e., minimize their absolute difference). Among all arrangements that achieve this minimum difference, the number of rotated photos should be as small as possible. Photos may only be $4\times 3$ (not counted as rotated) or $3\times 4$ (counted as rotated). Please help CYD write a program to design such an arrangement for XHY that meets these requirements and uses the fewest rotated photos.

The first line contains a positive integer $N$.

Output a single non‑negative integer — the minimal number of rotated photos.

- For 20% of the testdata, $N \le 10$. - For 30% of the testdata, $N \le 20$. - For 50% of the testdata, $N \le 50$. - For 70% of the testdata, $N \le 233$. - For 100% of the testdata, $N \le 900$. Translated by ChatGPT 5