<ПРЕД Задача:
СЛЕД>
Задачу решили 14 пользователей: 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 
Языки
C++
10
Kylix
3
Java
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Пентамино

Time limit = 5 секунд

Полимино — связная фигура, составленная из одноклеточных квадратов, примыкающих друг к другу по строне. Другими словами — это связная клеточная фигура, которую можно обойти ладьёй. Пентамино — это полимино, состоящее из 5 клеток, как нетрудно убедиться, существует ровно 12 пентамино, с точностью до поворотов и осевых симметрий.

Задача состоит в том, можно ли клеточную фигуру из 60 клеток покрыть всем набором пентомино, то есть каждое пентомино должно использоваться ровно 1 раз, и каждая клетка этой 60 — клеточной фигуры должна быть покрыто каким-нибудь пентамино.

Вход. Вход состоит из чисел M и N, и прямоугольника размером M*N (M строк, N столбцов), состоящего из нулей и едениц из которых ровно 60 — единицы, остальные -нули.

Выход. Выход должен содержать слово YES, если клеточную фигуру из 60 единиц можно покрыть набором пентомино, и NO в противном случае.

Вход#1
10 6
111111
111111
111111
111111
111111
111111
111111
111111
111111
111111

Выход#1
YES

Вход#2
11 13
0000100000000
0011111000000
0000111010000
0000111010110
1111111111111
1111111111100
1111111100000
0001111000000
0000111000000
0000111000000
0000011000000

Выход#2
NO

Автор:
Вообще, первооткрывателем пентомино и задач с ним связанных является С.В.Голомб, так что здесь должно быть упомянуто и его имя.
27 марта 2009

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 75.101.220.230