All submissions for this problem are available.
Barry Allen lives in a N x N square feet apartment. He wants to carpet the entire floor but only square carpets of side lengths upto N-1 are available. Help Barry to cover his floor with the minimum number of carpets possible. Make sure that there is neither excess carpet nor empty spaces.
A single integer N denoting the side length of Barry's apartment.
In the first line, output an integer k denoting the number of carpets required to cover the floor.In the next line, output k space separated integers denoting the sizes of the carpets used in increasing order of sizes.
N ranges from 2 to 50.
Input: 3 Output: 6 1 1 1 1 1 2
A square of side length 3 can be split into smaller squares in two ways: Either into 9 squares of side1 or 5 squares of side 1 and 1 square of size 2.The second case is the favourable one.
|Time Limit:||1 - 6 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.