Python

Python задача "Сортировка перестановки"

Дана перестановка из n чисел. Требуется её отсортировать. Можно применять только такую операцию любое число раз: взять число из i-й ячейки и переставить его в j-ю ячейку, если наибольший общий делитель чисел i и j больше 1. При этом в ячейке может оказаться одновременно несколько чисел. Но после всех операций в каждой i-й ячейке должно быть одно число i .
Нумерация ячеек ведется с 1, числа в перестановке от 1 до n .
Определите по исходной перестановке, можно её отсортировать указанным способом или нельзя.

Входные данные
В первой строке записано одно целое число n
(1≤n≤200000) — размер перестановки.
Во-второй строке записано n различных целых чисел a1,a2,…an
(1≤ai≤n) — исходная перестановка.

Выходные данные
Выведите «YES», если можно отсортировать перестановку указанным способом, и «NO» в противном случае случае.
 входные данные

9 

1 8 3 6 5 4 7 2 9 

выходные данные

YES



входные данные

6 

6 2 3 5 4 1 

выходные данные

NO
Николай Радченко
Николай Радченко
307
Очевидно, что если a[1] != 1, сортировка невозможна, т.к. НОД (x, 1) == 1 и мы ничего не можем поместить в ячейку 1.

Пусть q[x] - наименьший простой делитель числа x.
Предположим, у нас в ячейке a[i] находится число k.
Если k == i - число k находится на своём месте.
Если НОД(k, i) > 1 - число k можно одним ходом поместить в ячейку a[k].
Если НОД(k, i) == 1 и q[k] * q[i] <= n, число k можно двумя ходами поместить на своё место: сначала в ячейку a[q[k] * q[i]], потом в ячейку a[k].
Если НОД(k, i) == 1 и q[k] * q[i] > n, сортировка невозможна, т.к. у нас нет ячейки, в которую мы сможем перенести число для последующего переноса в a[k].

Наименьшие простые делители поучаем банальным решетом Эратосфена.
 import math

_, a = int(input()), list(map(int, input().split()))



q = [0] * (len(a) + 1)

for i in range(2, len(q)):

  if q[i]: continue

  q[i] = i

  for j in range(i * i, len(q), i): q[j] = q[j] or i



for i, j in enumerate(a, start=1):

  if i == j or 0 < q[i] * q[j]  1: continue

  print('NO')

  break

else: print('YES')
Роман Асташов
Роман Асташов
62 194
Лучший ответ
Решение данной задачи можно осуществить с помощью алгоритма Тарьяна для поиска компонент сильной связности в графе. Для этого нужно создать граф, в котором вершины - числа от 1 до n, а ребрами соединить все пары вершин, у которых наибольший общий делитель больше 1. Затем применить к этому графу алгоритм Тарьяна и проверить, что все вершины принадлежат одной компоненте сильной связности. Если это так, то ответ "YES", иначе - "NO".

Пример решения на Python:
 import math 

 

n = int(input()) 

a = list(map(int, input().split())) 

 

# Создаем граф 

graph = [[] for _ in range(n)] 

for i in range(n): 

    for j in range(i+1, n): 

        if math.gcd(i+1, j+1) > 1: 

            graph[i].append(j) 

            graph[j].append(i) 

 

# Алгоритм Тарьяна 

used = [False] * n 

order = [] 

def dfs(v): 

    used[v] = True 

    for u in graph[v]: 

        if not used[u]: 

            dfs(u) 

    order.append(v) 

for i in range(n): 

    if not used[i]: 

        dfs(i) 

order.reverse() 

 

comp = [-1] * n 

k = 0 

def dfs2(v): 

    comp[v] = k 

    for u in graph[v]: 

        if comp[u] == -1: 

            dfs2(u) 

for v in order: 

    if comp[v] == -1: 

        dfs2(v) 

        k += 1 

 

# Проверка наличия одной компоненты сильной связности 

if k == 1: 

    print("YES") 

else: 

    print("NO")
Обратите внимание, что данное решение имеет асимптотику O(n log n), что позволяет решать задачу для значений n до 200000.
Николай Мельник
Николай Мельник
2 847
Алибек Али А для 200001 не позволяет? Аллес капут, нейросеть запретила...
Николай Мельник для огромных чисел лучше всего использовать другую библиотеку просто
Дмитрий Шулятев так у тебя даже код не рабочий а должно быть YES как в примере

Похожие вопросы