Весенние старты 2026 з6

г. Иркутск

Конкурс юных программистов «Весенние старты» 2026
Номинация "Решение программистских задач"
Автор заданий Г.Б. Рейнгольд

Задача F. Сортировка по количеству делителей (20 баллов)

Задаётся набор натуральных чисел. Требуется преобразовать его следующим образом:

1. Числа, стоящие на нечётных позициях, отсортировать по количеству делителей по возрастанию. В случае равного количества делителей числа располагаются по возрастанию.

2. Числа, стоящие на чётных позициях, отсортировать по количеству делителей по убыванию. В случае равного количества делителей числа располагаются по убыванию.

Пример:
Вход –      28 8 82 54 23 77 1
Выход –    1 54 23 77 82 8 28

Пояснение к примеру:

Исходные числа:  __________   28  8 82 54 23 77  1
Количества делителей у них:      6   4   4   8   2   4  1


Формат входных данных: строка целых чисел, разделённых пробелами. Количество чисел в строке <=100, числа <=10000000000).

Формат выходных данных: строка целых чисел, разделённых пробелами. Количество чисел такое же, как и в строке ввода.

Лимит времени на прохождение одного теста – 2 секунды.

Авторское решение (Python)

# Всенние старты 2026
# Задача F "Сортировка по количеству делителей"
# Авторское решение
# Автор заданий Рейнгольд ГБ
#
# Это самая трудная задача!
# Нужно знать и любить математику.
# Знать или определить по ходу дела, что
# делители делятся на пары, что у полных квадратов
# нечётное количество делителей, что можно определять
# делители парами и надо идти до квадратного корня.
#
# Для решения надо уметь работать с функциями
# остатка от деления и целой части
# (либо пользоваться операцией целочисленного деления.
# Либо уметь работать с ветвлением.

# Здравый смысл необходим.


def vivod(n, a): # Вывод массива без скобок и запятых, без этого, впрочем, можно обойтись.
    for i in range(1, n + 1, 1):
        print(a[i], end = ' ')
    print()

def kd0(a): # Количество делителей алгоритм линейной сложности (неэффективный),
            # в этом случае пройдут не все тесты. Но его сделать легко.
    n = 0
    for i in range(1, a + 1, 1):
        if a % i == 0:
            n += 1
    return n       
            

def kd(a): # Быстрое вычисление количества делителей числа. Сложность "квадратный корень".
    n = 0 # Количество делителей, возвращается в главную программу
    i = 1 # Возможные делители
    aa = a**0.5 # Для сокращения количества операций.
                # Чтобы сразу учитывать два парных делителя
    #print('a=', a, '*', end = ' ')
    while i <= aa:
        if a % i == 0:
            n += 2 # Сразу два делителя.
            #print(i, a // i, end = ' ')
        i += 1
    if aa == int(aa): # Полный квадрат. Один непарный делитель.
        n -= 1
    #print('*', n)
    return n

n = int(input())
a = list(map(int, input().split())) # Строка входных чисел
n = len(a) # Количество введённых чисел
a = [0] + a + [0] # Добавляется два буферных элемента для удобства,
                # чтобы считать не с 0, а с единицы и в конце для безопасности

# print(n)
# print(a)

d = [0] * (n + 2) # Список количеств делителей для входных чисел
for i in range(1, n + 1, 1):
    d[i] = kd(a[i])

# print(d)

a1 = [0] # Список чисел на НЕЧЁТНЫХ позициях
a2 = [0] # Список чисел на ЧЁТНЫХ позициях
d1 = [0] # Список количеств делителей на НЕЧЁТНЫХ позициях
d2 = [0] # Список количеств делителей на ЧЁТНЫХ позициях
         # Все эти списки с буферными элементами в начале и в конце
for i in range(1, n + 1, 2): # Проход по нечётным позициям
    a1.append(a[i])          # и занесение во вспомогательные списки
    d1.append(d[i])          # исходных чисел и количества их делителей
for i in range(2, n + 1, 2): # Аналогично по чётным позициям   
    a2.append(a[i])
    d2.append(d[i])   

a1 = a1 + [0]
a2 = a2 + [0]
d1 = d1 + [0]
d2 = d2 + [0]

n1 = len(a1) - 2
n2 = len(a2) - 2

for i in range(1, n1, 1): # Главная часть. Сортировка по количеству делителей
    for j in range(i + 1, n1 + 1, 1):   # по ВОЗРАСТАНИЮ тех элементов, которые 
        if d1[i] > d1[j]:               # в исходном списке стоят на НЕЧЁТНЫХ
            a1[i], a1[j] = a1[j], a1[i] # позициях.
            d1[i], d1[j] = d1[j], d1[i]
        if d1[i] == d1[j]:    # Если количество делителей равное, то
            if a1[i] > a1[j]: # отсортировать по возрастанию
                a1[i], a1[j] = a1[j], a1[i]
               
for i in range(1, n2, 1):             # Обработка элементов на нечётных
    for j in range(i + 1, n2 + 1, 1): # в исходном списке  позициях.
        if d2[i] < d2[j]:             # Тут всё аналогично. Только по УБЫВАНИЮ.
            a2[i], a2[j] = a2[j], a2[i]
            d2[i], d2[j] = d2[j], d2[i]
        if d2[i] == d2[j]:
            if a2[i] < a2[j]:
                a2[i], a2[j] = a2[j], a2[i]
               
for i in range(1, n1 + 1, 1): # Перенос из вспомогательных списков
    a[2*i - 1] = a1[i]        # в основной.
for i in range(1, n2 + 1, 1):
    a[2 * i] = a2[i]

vivod(n, a) # Вывод результата