Best board fill
All submissions for this problem are available.
The following a tie breaker problem. The best solution will receive one point. All other successful answers will be scored on a curve and receive a fraction of a point based on how close they come to the best answer.
Given a large board (with holes) and set of tetris-like figures (an unlimited source, capable of generating any number of them), try to cover the board as exactly as possible.
The source is capable of generating the following pieces:
1) ### .#.
2) ##. .##
3) #.# ###
4) ### #..
5) ..# ### #..
6) #.# ### .#.
You are allowed to flip and rotate pieces before placing them on the board.
The first line contains two numbers - 100<=n,m<=1000 - the height and the width of the board.
The next n lines, each containing m space-separated numbers, are the board description. The symbol '0' is a square which should be filled, the symbol '1' is a square which should not be filled.
First output the number of pieces used, k < 106. Then write k successive descriptions of the used pieces. Each description should be of the form: t - the number of full squares of the piece, followed by t pairs of integers denoting the coordinates of the respective squares (using 0-based offsets, with the top-left of input written as (0,0) ).
Input: 3 3 0 0 0 0 1 0 0 0 0 Output: 2 4 0 0 0 1 1 1 0 2 4 0 2 1 2 2 2 2 1
For each square you will receive a penalty, calculated in the following way:
Let a be the number a square should be covered by (either 0 or 1), and let b be the actual number of times the square has been covered by a # piece (pieces may overlap). If a > b (the square should have been covered, but was not), the penalty is 3. If b > a (the square should not have be covered and was covered, or should have been covered, but was covered more than once), the penalty is b-a.
The total penalty is the sum of individual penalties, taken over all squares.
In the example the penalty is 3+3+1+1 = 8.
The program will be run several times for different data sets and the overall score will be the mean of scores received.
All tests have been randomly generated, with 1 covering less than 40% of the total number of squares.
|Time Limit:||0.120365 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.