Матч 433, Магические слова (MagicWords)

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

Строка T содержит в точности L символов. Строка T(i) является циклическим сдвигом строки T, начинающейся с позиции i. T(i) содержит такое же количество символов, как и T. Для каждого j от 0 до L – 1 j - ый символ T(i) равен (i + j) % L - ому символу строки T. Слово T является магическим, если существует в точности k позиций i таких, что T(i) = T.

Массив s содержит n слов. Для каждой перестановки p = p₀p₁p₂…p_n-1 определим строку s[p₀] + s[p₁] + … + s[p_n-1] как конкатенацию слов из s. Вычислить количество перестановок, генерирующих магические слова.

Класс: MagicWords

Метод: int count(vector<string> s, int k)

Ограничения: s содержит от 1 до 8 строк, каждая строка в s содержит от 1 до 20 символов ‘A’ – ‘Z’, 1 £ k £ 200.

Вход. Массив строк s и целое число k.

Выход. Наименьшее возможное значение суммы S.

Пример входа

s	k
{"CAD","ABRA","ABRA"}	1
{"AB","RAAB","RA"}	2
{"AA","AA","AAA","A"}	1

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

6

3

0

РЕШЕНИЕ

перебор

Функция magic(s, k) проверяет, является ли строка s магической. В ячейке mem[s] запоминаем количество таких позиций i, для которых T(i) = T. Если очередная перестановка p слов из s будет такой же как и одна из предыдущих (значение mem[p] отлично от нуля), то функция magic(p, k) не вызывается на этой перестановке. Достаточно проверить равенство mem[p] = k. Если оно имеет место, то увеличиваем res на 1 (имеем еще одну магическую строку).

Перебираем все перестановки массива строк s (их не более 8!), для каждой из них проверяем, является ли она магической.

В ячейках m[str] содержится количество строк str, которе встречается во входном массиве s. После перебора всех перестановок значение res следует умножить на факториалы m[str] для всех строк, содержащихся в m. Это следует совершить из-за специфики функции next_permutation (например, для множества {“a”, “a”, “a”} next_permutation сгенерирует лишь одну перестановку, хотя таковых должно быть 3! = 6).

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <string>

#include <map>

#include <numeric>

using namespace std;

map<string, int> m, mem;

map<string, int>::iterator iter;

int fact(int n)

{

return (n) ? fact(n - 1) * n : 1;

}

int magic(string s, int k)

{

int i, j, len = s.size(), res = 0;

string temp = s + s;

for(i = 0; i < len; i++)

{

for(j = 0; j < len; j++)

if (temp[i + j] != temp[j]) break;

if (j == len) res++;

if (res > k) break;

}

mem[s] = res;

return res == k;

}

class MagicWords

{

public:

int count(vector<string> s, int k)

{

int i, res = 0 ;

string str;

sort(s.begin(),s.end());

for(i = 0; i < s.size(); i++) m[s[i]]++;

do{

str = accumulate(s.begin(),s.end(),string());

if (mem.find(str) != mem.end()) res += (mem[str] == k);

else res += magic(str, k);

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

for(iter = m.begin(); iter != m.end(); iter++)

res *= fact((*iter).second);

return res;

}

};