MathDB

Several cells are marked in a

100 \times 100

table. Vasya wants to split the square into several rectangles such that each rectangle does not contain more than two marked cells and there are at most

k

rectangles containing less than two cells. What is the smallest

k

such that Vasya will certainly be able to do this?

Problem Statement