349. Перестановки

Не решаласьСредняя

Есть два метода генерации случайных перестановок длины 8 — правильный и творческий. Код этих методов приведён ниже.

Реализация на C++:

vector<int> RandomPermutation() {
    vector<int> perm;
    for (int i = 0; i < 8; ++i) {
        perm.push_back(i);
    }
    std::random_device rd;
    std::mt19937 g(rd());
    shuffle(perm.begin(), perm.end(), g);
    return perm;
}

vector<int> StupidPermutation() {
    const vector<int> partialSums = {0,1,8,35,111,285,
        628,1230,2191,3606,5546,8039,11056,14506,18242,
        22078,25814,29264,32281,34774,36714,38129,39090,
        39692,40035,40209,40285,40312,40319,40320};
    int r = rand() % (partialSums.back() + 1);
    int numInv = 0;
    while (partialSums[numInv] < r) {
        numInv++;
    }
    vector<int> perm;
    for (int i = 0; i < 8; ++i) {
        perm.push_back(i);
    }
    for (int step = 0; step < numInv; ++step) {
        int t1 = rand() % 8;
        int t2 = rand() % 8;
        swap(perm[t1], perm[t2]);
    }
    return perm;
}

Реализация на Python:

def RandomPermutation():
    perm = list(range(8))
    random.shuffle(perm)
    return perm

def StupidPermutation():
    partialSums = [0,1,8,35,111,285,
        628,1230,2191,3606,5546,8039,11056,14506,18242,  
        22078,25814,29264,32281,34774,36714,38129,39090,  
        39692,40035,40209,40285,40312,40319,40320]
    r = random.randint(0, partialSums[-1])
    numInv = 0
    while partialSums[numInv] < r:
        numInv += 1
    perm = list(range(8))
    for step in range(numInv):
        t1 = random.randint(0, 7)
        t2 = random.randint(0, 7)
        perm[t1], perm[t2] = perm[t2], perm[t1]
    return perm

В правильном методе генерируется случайная перестановка. В творческом сначала выбирается число n u m I n v numInv , соответствующее доле неправильно упорядоченных пар чисел в случайной перестановке. Массив p a r t i a l S u m s partialSums выбран таким образом, что распределение величины n u m I n v numInv получается правильным.

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

В этой задаче по набору из 1000 1000 перестановок необходимо определить, каким методом он был получен. Дано n n таких наборов, нужно отсортировать их так, чтобы сначала шли хорошие наборы, а потом творческие.

Решение засчитывается, если среди всех пар наборов (хороший, творческий), хотя бы 98% идёт в правильном порядке (детали в примечании).

Формат ввода

Файл permutations.in находится в архиве, доступном по адресу.

В первой его строке указано одно число n n — количество наборов перестановок.

В каждой из следующих 1000 n 1000 n строк указано по перестановке чисел от 0 0 до 7 7 .

Первая 1000 1000 строк соответствует первому набору перестановок, вторая 1000 1000 — второму и т.д.

Формат вывода

Выведите n n чисел — в i i -ой строке должен быть указан номер набора перестановок (от 0 0 до n − 1 n - 1 ). Сначала должны идти номера хороших наборов, потом творческих.

Примечание

Для определения корректности ответа вычисляются две величины:

  • t o t a l total : количество пар индексов i < j i \lt j таких, что генераторы для наборов i i и j j различны;
  • g o o d good : количество пар индексов i < j i \lt j таких, что генератор для набора i i — «хороший», а для j j — «творческий».

Ответ считается корректным, если g o o d t o t a l ≥ 0.98 \frac{good}{total} \ge 0.98 .

Ограничения

Ограничение времени
1 с
Ограничение памяти
64 МБ

Примеры

Теги

Без компиляции
Нужно войти, чтобы отправить решение.Войти