Список вопросов
Как зайти в Даркнет?!
25th January, 01:11
5
0
Как в tkinter из поля ввода Entry получить значение в одну переменную и обновить строку кнопкой, затем получить ещё одно введённое значение и затем сложить их. Ниже пример кода
21st July, 19:00
893
0
Программа, которая создает фейковые сервера в поиске игровых серверов CS 1.6 Steam
21st March, 17:43
948
0
Очень долго работает Update запрос Oracle
27th January, 09:58
912
0
не могу запустить сервер на tomcat HTTP Status 404 – Not Found
21st January, 18:02
905
0
Где можно найти фрилансера для выполнения поступающих задач, на постоянной основе?
2nd December, 09:48
938
0
Разработка мобильной кроссплатформенной военной игры
16th July, 17:57
1724
0
период по дням
25th October, 10:44
3955
0
Пишу скрипты для BAS только на запросах
16th September, 02:42
3720
0
Некорректный скрипт для закрытия блока
14th April, 18:33
4613
0
прокидывать exception в блоках try-catch JAVA
11th March, 21:11
4381
0
Помогите пожалуйста решить задачи
24th November, 23:53
6085
0
Не понимаю почему не открывается детальное описание продукта
11th November, 11:51
4350
0
Нужно решить задачу по программированию на массивы
27th October, 18:01
4395
0
Метода Крамера С++
23rd October, 11:55
4309
0
помогите решить задачу на C++
22nd October, 17:31
4002
0
Помогите решить задачу на python с codeforces
22nd October, 11:11
4492
0
Python с нуля: полное руководство для начинающих
18th June, 13:58
2599
0
Решение задачи Шахматная доска с Codeforces
С пояснением   Просмотров: 1162
Однажды Магнус решил разыграть одну классическую шахматную партию. Но открыв чулан, Магнус пришел в ужас! Его любимая доска была разломлена на 4 части, каждая размера n на n, причем n обязательно нечетно. Хуже того, некоторые клетки имели неправильный цвет. j-я клетка i-й строки k-й части доски имеет цвет a k, i, j; 1 соответствует черному цвету, а 0 — белому.
Магнусу стало интересно, какое минимальное количество клеток нужно перекрасить, чтобы из частей доски можно было составить правильную доску. В правильной доске любая пара соседних по стороне клеток должна иметь различный цвет, и размер правильной доски должен быть 2n на 2n. Части доски разрешено переставлять, но нельзя поворачивать или переворачивать.
Магнусу стало интересно, какое минимальное количество клеток нужно перекрасить, чтобы из частей доски можно было составить правильную доску. В правильной доске любая пара соседних по стороне клеток должна иметь различный цвет, и размер правильной доски должен быть 2n на 2n. Части доски разрешено переставлять, но нельзя поворачивать или переворачивать.
Код
#include using namespace std; const int N = 109; int n; string a[4][N]; int main() { cin >> n; for(int k = 0; k < 4; ++k) for(int i = 0; i < n; ++i){ cin >> a[k][i]; for(int j = 0; j < n; ++j) a[k][i][j] -= '0'; } vector v; for(int k = 0; k < 4; ++k){ int sum = 0; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if((i + j) % 2 != a[k][i][j]) ++sum; v.push_back(sum); } int res = int(1e9); vector perm; for(int k = 0; k < 4; ++k) perm.push_back(k); do{ int sum = 0; for(int k = 0; k < 4; ++k){ int id = perm[k]; if(k & 1) sum += v[id]; else sum += n * n - v[id]; } res = min(res, sum); }while(next_permutation(perm.begin(), perm.end())); cout << res << endl; }
 
 
 
 
 
Автор: Администратор
Автор: Администратор
Пояснение к задаче
Заметим, что при данных ограничениях 2 части доски будут иметь левый верхний угол белого цвета, а другие 2 — черного. Переберем, у каких частей доски левый верхний угол будет белым, соответственно, у оставшихся частей он будет черным. Все, что осталось — посчитать количество клеток, которые покрашены не в свой цвет, и вывести минимум по всем возможным перестановкам частей доски.
Комментарии
info@mycod.net  
Карта сайта  
Правообладателям
Заявка на расчет
×
или напишите нам прямо сейчас: