|Online MIPT programming contest||РУССКИЙ|
Time limit = 5 secondsPolyomino is a connected figure made of one-cell squares, adjacent by its sides. By other words, it is consecutive one-cell figure that could be traced by chess rook. Pentamino is polyomino consisted of 5 one-cell elements. There are exactly 12 different pentaminoes (rotations and reflections do not create new ones).
The problem is to verify whether given 60 one-cells elements figure can be covered with full set of pentaminoes. That means each of 12 figures should beg used exactly once and each cell of the source figure should be covered.
Input. Input contains numbers M and N and rectangle M*N (M rows and N columns) with '0' and '1' elements. There are exactly 60 '1' cells in the rectangle.
Output. Output must contain a single word YES if the given 60-cells figure can be covered with full set of pentaminos and NO otherwise.
10 6 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111
11 13 0000100000000 0011111000000 0000111010000 0000111010110 1111111111111 1111111111100 1111111100000 0001111000000 0000111000000 0000111000000 0000011000000
Here must be also name of Golomb, the inventor of pentamino.
27 Marth 2009
© acm.mipt DevGroup
The page was generated in 200ms