<PREV Problem:
NEXT>
Solved by 14 users: defrager, UdH-WiNGeR, WsemirZ, dan, murphy, fetetriste, TTLovePP, Yagi_Arthur, RAVEman, Rizvanov, VladimirChelnokov, Dest, ripatti, topspin.
UserDateAttemptTimeCMSC
ripatti23 jun 2010C++7500.371582 
ripatti23 jun 2010C++7400.421582 
ripatti23 jun 2010C++7200.621582 
ripatti23 jun 2010C++7101.211582 
Rizvanov07 feb 2010C++2901.481435 
defrager07 apr 2009C++601.723014 
WsemirZ13 apr 2009Kylix1202.402313 
ripatti23 jun 2010C++7002.511582 
TTLovePP29 dec 2009C++402.941357 
VladimirChelnokov09 mar 2010C++202.993207 
RAVEman06 feb 2010C++2303.011288 
Yagi_Arthur31 dec 2009Kylix1203.011468 
Yagi_Arthur31 dec 2009Kylix1003.031465 
WsemirZ13 apr 2009Kylix1103.062313 
topspin04 aug 2010Kylix1503.151437 
topspin04 aug 2010Kylix1703.181265 
dan25 apr 2009C++203.521358 
Rizvanov06 feb 2010C++1303.571317 
VladimirChelnokov09 mar 2010C++103.743193 
Languages
C++
10
Kylix
3
Java
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Pentamino

Time limit = 5 seconds

Polyomino 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.

Input#1
10 6
111111
111111
111111
111111
111111
111111
111111
111111
111111
111111

Output#1
YES

Input#2
11 13
0000100000000
0011111000000
0000111010000
0000111010110
1111111111111
1111111111100
1111111100000
0001111000000
0000111000000
0000111000000
0000011000000

Output#2
NO

Author:
Here must be also name of Golomb, the inventor of pentamino.
27 Marth 2009

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 35.172.233.215