Матч 57, Потерянный алгоритм сортировки

(LostSortingAlgorithm)

Имеется информация о следующих четырех домах, один из которых Вы хотите купить:

· A: $100,000, 2 спальни, 30 минут до работы

· B: $200,000, 3 спальни, 10 минут до работы

· C: $300,000, 3 спальни, 10 минут до работы

· D: $100,000, 3 спальни, 20 минут до работы

Расставим приоритеты Вашего выбора:

1. Вам не нужен большой дом. Лучшим является дом с меньшим числом спален;

2. Расстояние от дома до работы должно быть наименьшим;

3. Наименее важной характеристикой является цена: чем меньше, тем лучше.

Если отсортировать имеющиеся четыре дома в порядке уменьшения описанных приоритетов, то получим последовательность: A, B, C, D.

Массив clues содержит информацию о домах в порядке убывания приоритетов. Каждый элемент clues содержит информацию об одном доме: clues[i][j] содержит значение j - го атрибута i - го дома. Меньшие значения атрибутов соответствуют большему приоритету. Необходимо восстановить порядок приоритетов среди атрибутов. Считается, что никакие два дома не имеют одинаковых приоритетов.

Вернуть строку, содержащую атрибуты в порядке уменьшения их приоритетов. Если атрибутам невозможно расставить приоритеты, то вернуть “IMPOSSIBLE”. Если существует несколько вариантов расстановки приоритетов, вернуть “TOO MANY”.

Класс: LostSortingAlgorithm

Метод: string recoverSortingAlgorithm(vector<string> clues)

Ограничения: clues содержит от 1 до 50 элементов, clues[i] содержит от 1 до 8 символов ‘0’ – ‘9’, ‘A’ – ‘F’, длины clues[i] равны, все элементы clues[i] разные.

Вход. Массив clues, содержащий информацию о домах в порядке убывания приоритетов.

Выход. Строка, содержащая атрибуты в порядке уменьшения их приоритетов. Если атрибутам невозможно расставить приоритеты, то строка должна содержать “IMPOSSIBLE”. Если существует несколько вариантов расстановки приоритетов, вернуть “TOO MANY”.

Пример входа

clues

{"12D", "23A", "33A", "13B"}

{"0112", "2102", "1010"}

{"0123","0145","1234","1245","2345","2346"}

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

"120"

"IMPOSSIBLE"

"TOO MANY"

РЕШЕНИЕ

комбинаторика

Поскольку приоритетов имеется не более 8, то можно рассмотреть все их возможные перестановки (комбинации) в массиве pos. Для каждой комбинации приоритетов сортируем массив clues, используя функцию comp. Если после сортировки он равен самому себе, то нас удовлетворяет текущая перестановка приоритетов. Если таких перестановок существует несколько, возвращаем "TOO MANY". Иначе в строку res заносим найденную перестановку. Если после генерации всех перестановок в res ничего не записано (res = “”), то требуемой перестановки приоритетов не существует, возвращаем "IMPOSSIBLE".

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int n,pos[8];

int comp(const string &a, const string &b)

{

for(int i = 0; i < n; i++)

{

if (a[pos[i]] < b[pos[i]]) return 1;

if (a[pos[i]] > b[pos[i]]) return 0;

}

return 0;

}

class LostSortingAlgorithm

{

public:

string recoverSortingAlgorithm(vector<string> clues)

{

int i;

n = (int)clues[0].size();

string res = "";

vector<string> clue;

for(i = 0; i < 8; i++) pos[i] = i;

do

{

clue = clues;

sort(clue.begin(),clue.end(),comp);

if (clue == clues)

{

if (res != "") return "TOO MANY";

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

res += pos[i] + '0';

}

} while(next_permutation(pos,pos+n));

return res == "" ? "IMPOSSIBLE" : res;

}

};