Все источники
>>
Олимпиады и турниры
>>
Турнир городов
>>
17 турнир (1995/1996 год)
>>
осенний тур, основной вариант, 10-11 класс
Фильтр
Выбрана 1 задача Убрать все задачи
Максимальное время работы на одном тесте: 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 |
Решение
Задачи
Задача 108114 (#1) |
|
В плоскости выпуклого четырёхугольника ABCD расположена точка P.
Проведены биссектрисы PK,PL, PM и PN треугольников APB, BPC, CPD и DPA соответственно.
а) Найдите хотя бы одну такую точку P, для которой четырёхугольник
KLMN – параллелограмм.
б) Найдите все такие точки.
|
|
Решение |
Задача 98286 (#2) |
|
|
Дано n чисел, p – их произведение. Разность между p и каждым из этих чисел – нечётное число. Докажите, что все данные n чисел иррациональны.
|
|
|
Решение |
Задача 98287 (#3) |
|
|
Прямоугольник разбит на прямоугольные треугольники, граничащие друг с другом только по целым сторонам, так, что общая сторона двух треугольников всегда служит катетом одного и гипотенузой другого. Докажите, что отношение большей стороны прямоугольника к меньшей не менее 2.
|
|
|
Решение |
Задача 98288 (#4) |
|
|
Кресла для зрителей вдоль лыжной трассы занумерованы по порядку: 1, 2, 3, ..., 1000. Кассирша продала n билетов на все первые 100 мест, но n больше 100, так как на некоторые места она продала больше одного билета (при этом n < 1000). Зрители входят на трассу по одному.Каждый, подойдя к своему месту, занимает его, если оно свободно, если же занято, говорит "Ох!", идёт в сторону роста номеров до первого свободного места и занимает его. Каждый раз, обнаружив очередное место занятым, он говорит "Ох!". Докажите, что число "охов" не зависит от того, в каком порядке зрители выходят на трассу.
|
|
|
Решение |
Задача 108003 (#5) |
|
|
На берегу круглого озера растут 6 сосен. Известно, что если взять такие два треугольника, что вершины одного совпадают с тремя из сосен, а вершины другого – с тремя другими, то в середине отрезка, соединяющего точки пересечения высот этих треугольников, на дне озера находится клад. Неизвестно только, как нужно разбить данные шесть точек на две тройки. Сколько раз придётся опуститься на дно озера, чтобы наверняка отыскать клад?
|
|
|
Решение |
Страница: 1 2 >> [Всего задач: 6]
