XX Открытая Всесибирская олимпиада по программированию им. И.В. Поттосина
Очный тур, Вторая номинация, НГУ, 3 ноября 2019 г.
Задача 1. Перекраска крыш
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Король Берляндии очень любит порядок. Например, столица Берляндии на карте выглядит как прямоугольное клеточное поле, на котором каждая клетка является кварталом.
Недавно он издал указ, чтобы в каждом квартале все крыши домов были покрашены в один из двух цветов — красный или синий, причём внутри каждого квартала цвет всех крыш должен быть одинаковый. Теперь в столице Берляндии ожидают появления ревизоров, которые будут проверять исполнение указа. Ревизоры будут ходить по городу, периодически переходя из квартала в соседний по стороне квартал. Для успешности проверки необходимо, чтобы ревизоры могли добраться из любого квартала в любой.
Министр финансов через знакомых выяснил, что у ревизоров есть занятная фобия. Оказалось, что они не могут перейти в соседний квартал, если в нём такой же цвет крыш, как в текущем квартале. Таким образом, в некоторых кварталах придётся перекрасить крыши всех домов, чтобы пройти проверку. Министр финансов как обычно хочет сэкономить деньги, поэтому просит Вас определить минимальное количество кварталов, в которых придётся перекрасить все крыши.
Формат входных данных
В первой строке входного файла записаны два целых числа ? и ? — количество строк и количество столбцов на карте столицы (1 ⩽?, ?⩽1000).
Далее следуют ? строк, состоящих из ? символов, каждый из которых либо ’1’, либо ’2’.
Символ ’1’ означает, что в соответствующем квартале все крыши синие, а символ ’2’ — что все крыши имеют красный цвет.
Формат выходных данных
В выходной файл необходимо вывести одно целое число — минимальное количество кварталов, в которых потребуется перекрасить все крыши.
Пример
input.txt
output.txt
1 4
2211
2
Страница 1 из 17
XX Открытая Всесибирская олимпиада по программированию им. И.В. Поттосина
Очный тур, Вторая номинация, НГУ, 3 ноября 2019 г.
Задача 2. Симметричная матрица
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана квадратная матрица, имеющая ? строк, все элементы которой — целые числа. Разрешается за одно действие переставить местами два элемента в матрице. Требуется определить, за какое минимальное количество действий можно получить из данной матрицы симметричную. Напомним, что симметричной называется матрица, у которой на пересечении ?-ой строки и ?-го столбца стоит такой же элемент, что и на пересечении ?-ой строки и ?-го столбца для любых ?, ?.
Гарантируется, что в заданной матрице ? элементов встречаются ровно один раз, все остальные встречаются по два раза.
Формат входных данных
В первой строке входного файла записано целое число ? — количество строк в матрице (1 ⩽?⩽500).
Далее следуют ? строк заданной матрицы. Каждая из них содержит ? целых чисел, разделённых пробелом, по модулю не превосходящих 10^9.
Формат выходных данных
В первую строку выходного файла необходимо вывести одно целое число ? — минимальное количество действий, за которое можно получить симметричную матрицу. Далее нужно вывести пример таких ? действий. Для ?-го действия выведите четыре целых числа ??, ??, ??, ?? в отдельную строку, которые означают, что требуется переставить элемент, стоящий в ??-ой строке, в ??-ом столбце с элементом, стоящим в ??-ой строке, в ??-ом столбце.
Примеры
input.txt
output.txt
2
1 2
3 1
2
1 1 1 2
2 1 2 2
3
1 4 -3
4 2 5
6 6 5
2
3 3 3 2
3 3 1 3
Страница 2 из 17
XX Открытая Всесибирская олимпиада по программированию им. И.В. Поттосина
Очный тур, Вторая номинация, НГУ, 3 ноября 2019 г.
Задача 3. Создание карты
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт
Вася по-прежнему любит играть в компьютерные игры, и всё ещё работает тестировщиком игр. Но он уж
