Матч 379, Телеигра (TVGameWinnings)

Дивизион 2, Уровень 3

Имеется коробка размера n * n, содержащая набор домино. В строке i и столбце j коробки находится кость домино, на которой изображены числа i и j. Игрок выбирает n костей домино так, чтобы ни с какой строки и ни с какого столбца не было взято более одной кости. Далее по правилам домино он должен сложить из них цикл. Например, при n = 4 можно выбрать 4 кости и сложить из них цикл: (1,3), (3,2), (2,4), (4,1). При описанном выше условии n костей домино всегда можно однозначно сложить в один или несколько циклов.

На каждой кости домино, находящейся в строке i и столбце j, сзади написано число board[i][j]. Символы массива board от ‘0’ до ‘9’ представляют собой числа от 0 до 9, а символы от ‘A’ до ‘I’ представляют собой числа от -1 до -9. Вычислим произведение этих чисел для всех n выбранных костей домино. Если количество циклов (сложенных групп костей домино) четное количество, то следует умножить полученное произведение на -1. Полученное число является количеством выигранных (или в случае отрицательного числа проигранных) денег.

Необходимо найти наихудший (наименьший) и наилучший (наибольший) результат игры и вернуть их в виде массива из двух элементов.

Класс: TVGameWinnings

Метод: vector<int> getMinMax(vector<string> board)

Ограничения: board содержит от 1 до 6 элементов, board[i] содержит элементов ‘0’ – ‘9’,’A’-‘I’.

Вход. Массив board описывает числа, изображенные сзади на костях домино.

Выход. Массив, содержащий наихудший и наилучший результат игры.

Пример входа

board

{"35",

"44"}

{"00200",

"0B000",

"00020",

"10000",

"00001"}

{"12A",

"A12",

"2A1"}

Пример выхода

{-12, 20}

{-8, 0}

{-1, 8}

РЕШЕНИЕ

перебор вариантов

Наибольший возможный размер доски равен 6, следовательно число вариантов выбрать n костей домино не более 6! = 720. Перебираем все перестановки из n чисел при помощи функции next_permutation. Каждой перестановке (a₁, a₂, …, a_n) соответствует выборка костей домино (board[1][a₁], board[2][a₂], …, board[n][a_n] ). Для каждой выборки (перестановки) считаем количество циклов, вычисляем произведение чисел board[i][a_i]. Если количество циклов четно, умножаем произведение на -1. Изо всех результатов игры находим в переменной min наихудший и в переменной max наилучший.

Функция getConnectedComponents(perm) вычисляет количество циклов в перестановке perm.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <string>

using namespace std;

int m[7][7];

int getConnectedComponents(vector<int> perm)

{

int i, j, temp, groups;

for(groups = i = 0; i < perm.size(); i++)

{

j = i; groups += (perm[j] >= 0);

while(perm[j] >= 0)

temp = perm[j], perm[j] = -1, j = temp;

}

return groups;

}

class TVGameWinnings

{

public:

vector<int> getMinMax(vector<string> board)

{

vector<int> res(2,0), perm(board.size(),0);

int s, i, j, min, max;

for(i = 0; i < board.size(); i++)

for(j = 0; j < board[0].size(); j++)

if (isdigit(board[i][j])) m[i][j] = board[i][j] - '0';

else m[i][j] = -(board[i][j] - 'A' + 1);

for(i = 0; i < board.size(); i++) perm[i] = i;

min = 1000000000; max = -min;

do

{

for(s = 1, i = 0; i < perm.size(); i++)

s *= m[i][perm[i]];

i = getConnectedComponents(perm);

if (i % 2 == 0) s =-s;

if (s < min) min = s;

if (s > max) max = s;

} while(next_permutation(perm.begin(),perm.end()));

res[0] = min; res[1] = max;

return res;

}

};