Матч 313, Циклы в перестановке (CyclesInPermutations)

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

Игра в перестановки производится на доске размером 1 ´ n. В ячейках записаны числа от 1 до n, каждое по одному разу. Номер позиции первой ячейки равен 1, нумерация ячеек производится слева направо. Например, одна из допустимых позиций для доски размером 6 имеет вид:

3

2

4

1

6

5

Игра ведется следующим образом. Вначале игрок выбирает произвольную клетку в качестве начальной и становится на нее. На каждом шаге он передвигается в такую позицию, номер которой записан в текущей клетке. Процесс передвижения игрока продолжается до тех пор, пока он снова не окажется в начальной клетке.

Необходимо найти номер такой начальной клетки, для которой в процессе игры будут посещено максимально возможное количество клеток.

Класс: CyclesInPermutations

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

Ограничения: board содержит от 1 до 50 разных чисел, пронумерованных с 1 до размера board.

Вход. Массив чисел board, содержащих перестановку чисел от 1 до n.

Выход. Максимальное количество клеток, которое игрок может посетить в процессе игры при оптимальном выборе начальной клетки.

Пример входа

board

{3,2,4,1,6,5}

{1,2,3,4,5,6}

{5,1,2,3,4}

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

3

1

5

РЕШЕНИЕ

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

В задаче необходимо найти все длины циклов заданной перестановки и выбрать среди них наибольшую.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class CyclesInPermutations

{

public:

int maxCycle(vector<int> board)

{

int i, j, count, res = 0;

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

{

count = 0;

for(j = board[i]; j - 1 != i; j = board[j - 1]) count++;

if (count > res) res = count;

}

return res + 1;

}

};