|
Название задачи: Раскраска плиток. |
 |
Условие
Максимальное время работы на одном тесте: 1 секунда
После того, как к удивлению тетушки Полли, ее забор был покрашен, она поручила Тому Сойеру обновить краску на плитках, которыми был вымощен их квадратный двор. Двор был покрыт N´ N одинаковыми квадратными плитками, каждая из которых когда-то давно была покрашена в один из K цветов (K < N). Краска на плитках потускнела и Тому Сойеру поручили их покрасить, на этот раз в один любой цвет (из тех же К цветов). Покрасить нужно все плитки, в том числе и те, которые уже были покрашены в этот цвет раньше.
Окунув кисть в ведро с краской один раз, можно перекрасить один горизонтальный или вертикальный ряд плиток. Чтобы разнообразить свою работу, Том придумал, что ряд плиток можно красить только цветом, которым на данный момент уже покрашены (старой или новой краской) по крайней мере две плитки выбранного ряда (вертикального или горизонтального). За один раз Том собирается красить допустимым цветом весь ряд целиком, независимо от того, были ли уже перекрашены какие-либо его плитки ранее. Помогите Тому определить, какое минимальное число раз ему придется обмакнуть кисть, чтобы перекрасить все плитки, следуя придуманным правилам, и в какой цвет окажутся окрашены все плитки.
Формат входных данных
В первой строке входного файла b.in записаны через пробел два числа: N - количество плиток в одном ряду (1 < N ≤ 200) и K (1 ≤ K < N). В каждой из следующих N строк записаны N натуральных чисел, обозначающих номера цветов красок, в которые когда-то были выкрашены соответствующие плитки данного горизонтального ряда. Номера цветов - натуральные числа в диапазоне от 1 до K.
Формат выходных данных
В выходной файл b.out выведите два числа: L - какое минимальное число раз придется окунать кисть в ведро с краской, и номер краски С, в которую в результате окажутся перекрашены все плитки двора. Если таких красок может быть несколько, то выведите номер любой из них.
Если перекрасить все плитки, следуя придуманным Томом правилам, нельзя, выведите два раза число 0.
Примеры
|
b.in |
b.out |
|
3 2 1 2 1 2 1 1 1 2 2 |
4 1 |
|
2 1 1 1 1 1 |
2 1 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программаПокажем сначала, что решение всегда существует. Так как K < N то в каждом горизонтальном ряду плиток найдутся по крайней мере две плитки одного цвета. Выпишем для каждого ряда любой из таких цветов (в него мы заведомо можем перекрасить соответствующий ряд). Среди выписанных N значений цветов по крайней мере два окажутся одинаковыми. Окрасим в этот цвет соответствующие два горизонтальных ряда плиток. Теперь в каждом вертикальном ряду мы имеем две плитки одного и того же цвета. Следовательно, окунув еще N раз кисть в ведро с краской, Том сможет перекрасить все плитки по своим правилам, и искомое значение L не может превосходить N + 2.
Рассмотрим теперь, когда можно покрасить двор быстрее. Так как все плитки должны быть перекрашены, минимальное значение L равно N. В этом случае Том будет красить либо только горизонтальные ряды, либо только вертикальные, и перекрашивание одного ряда никак не повлияет на возможность красить в этот же цвет другие ряды. Следовательно, для того чтобы перекрасить двор за N разрешенных операций, необходимо и достаточно иметь по две плитки одного и того же цвета в каждом из горизонтальных (или вертикальных) рядов.
|
5 |
4 |
1 |
3 |
2 |
1 |
|
4 |
5 |
1 |
3 |
2 |
3 |
|
1 |
1 |
1 |
2 |
1 |
3 |
|
4 |
4 |
3 |
1 |
2 |
2 |
|
2 |
2 |
2 |
4 |
3 |
2 |
|
4 |
4 |
1 |
2 |
3 |
3 |
|
5 |
4 |
1 |
3 |
2 |
1 |
|
3 |
3 |
3 |
3 |
3 |
3 |
|
1 |
1 |
1 |
2 |
1 |
3 |
|
4 |
4 |
3 |
1 |
2 |
2 |
|
2 |
2 |
2 |
4 |
3 |
2 |
|
3 |
3 |
3 |
3 |
3 |
3 |
|
5 |
3 |
1 |
3 |
2 |
1 |
|
3 |
3 |
3 |
3 |
3 |
3 |
|
1 |
3 |
1 |
2 |
1 |
3 |
|
4 |
3 |
3 |
1 |
2 |
2 |
|
2 |
3 |
2 |
4 |
3 |
2 |
|
3 |
3 |
3 |
3 |
3 |
3 |
За N + 1 операцию все плитки можно перекрасить в цвет С тогда и только тогда, когда в каждом горизонтальном (вертикальном) ряду есть не менее одной плитки цвета С, а еще как минимум в двух горизонтальных (вертикальных) рядах - не менее чем две плитки этого же цвета. Действительно, в этом случае сначала перекрасим те два горизонтальных (вертикальных) ряда, в которых имеются две плитки цвета C. Теперь мы можем перекрасить уже любой вертикальный (горизонтальный) ряд. Выберем для этого такой ряд, что после его окраски уже в каждом горизонтальном (вертикальном) ряду окажется уже по две плитки цвета C. Это всегда можно сделать, так как в остающихся неперекрашенными N - 2 рядах по одной плитке цвета C могут располагаться максимум на N - 2 вертикалях (горизонталях), а любую из оставшихся двух вертикалей (горизонталей) мы можем перекрасить (см. рис.). Теперь у нас уже во всех горизонтальных рядах есть по две плитки цвета C, и мы можем окрасить в него оставшиеся N - 2 горизонтали (это быстрее, чем окраска N - 1 вертикали!!!). Общее количество операций L при этом равно 2 + 1 + N - 2 = N + 1.
Докажем, что это же условие является необходимым. Если существует горизонтальный ряд, в котором плиток цвета С нет, то нам заведомо потребуется две вспомогательные вертикали для его дальнейшего окрашивания. Кроме этого мы будем красить все N горизонталей и общее количество операций окажется равным N + 2. Дополнительную вертикаль мы можем либо перекрасить сразу, если имеющиеся "вторые" плитки в двух горизонталях располагаются в одной вертикали, либо согласно процедуре, описанной выше. В любом случае требуется, чтобы как минимум в двух горизонталях изначально находились по две плитки цвета C. Аналогичные рассуждения можно провести для вертикальных рядов.
Алгоритм решения задачи сформулирован. Осталось его эффективно реализовать. Опишем одну из возможных реализаций для горизонтальной закраски. В данном случае очень удобно использовать такой специфический тип данных языка программирования Паскаль, как множество. Заведем массивы множеств sh[1..N] и sh1[1..N]. Каждый элемент первого из них будет хранить множество цветов, которые встречаются в соответствующей горизонтали не менее двух раз. Аналогично, каждый элемент второго - множество цветов, которые встречаются в соответствующей горизонтали не менее одного раза. Заполнение этих массивов по двухмерному массиву цветов плиток двора a[1..N,1..N] производится так:
sh := []; sh1 := [];
for i := 1 to n do
for j := 1 to n do
if a[i,j] in sh1[i]
then sh[i] := sh[i] + [a[i,j]]
else sh1[i] := sh1[i] + [a[i,j]];
Теперь очень легко проверить возможность горизонтальной закраски за N операций: пересечение всех множеств sh[i] должно быть отлично от пустого. На Паскале эта проверка выглядит так:
sr := sh[1];{sr - вспомогательная переменная типа множество}
for i := 2 to n do sr := sr*sh[i];
if sr <> [] then {искомый цвет существует}
for color := 1 to k do {ищем этот цвет}
if color in sr then out(n,color);
Если такой цвет не найден, в том числе и по вертикальному направлению, то попытаемся перекрасить двор за N + 1 операций:
sr := sh1[1];
for i := 2 to n do sr := sr*sh1[i];
if sr <> [] then
{в каждой горизонтали есть общий цвет}
for color := 1 to k do
if color in sr then
begin
cnt := 0;
for i := 1 to n do
{ищем ряды с 2 плитками}
if color in sh[i] then inc(cnt);
if cnt >= 2 then out(n+1,color)
end;
Аналогичное рассмотрение нужно провести и по другому направлению. Если решение до сих пор не получено, то остается определить цвет, в который можно перекрасить двор за N + 2 операций (здесь достаточно рассмотреть одно направление перекраски):
sr := [];
for i := 1 to n do
if sh[i] * sr = [] then
sr := sr + sh[i]
else for color:=1 to k do
if color in sh[i]*sr then
out(n+2,color);
Таким образом, вычислительная сложность алгоритма решения задачи равна O(N2). Решение приемлемой сложности можно получить, заменив массивы множеств на двухмерные массивы размером [1..N,1..K], имеющие тот же смысл, что и описанные выше множества.
Данную задачу на полный балл решили лишь 7 участников олимпиады. Остальные либо не рассмотрели какие-либо достаточные условия для того или иного числа операций перекрашивания, либо не смогли эффективно реализовать решение и их программы работали на некоторых тестах больше отведенного для этого времени.
Также доступны документы в формате DOC
