2

Для решения задачи нужно использовать именно сортировку вставками! Вот сама задача:

Результаты олимпиады

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

Входные данные

На первой строке дано число N(1≤N≤1000) — количество участников. На каждой следующей строке даны идентификационный номер и набранное число баллов соответствующего участника. Все числа во входном файле не превышают 105.

Выходные данные

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

Пример

Вввод

4

3 3

3 1

4 4

2 3

Вывод

4 4

2 3

3 3

3 1

----------------------------------------------------------------------------------------------------------------------------------

Вот мой код:

def compare(a, b):
    if a[1] > b[1]:
        return True
    elif a[1] == b[1]:
        return a[0] > b[0]
    else:
        return False

def trt(f):
    for i in range(1, len(f)):
        tmp = f[i]
        j = i - 1
        while j >= 0 and compare(tmp, f[j]):
            f[j + 1] = f[j]
            j -= 1
        f[j + 1] = tmp

f = []
n = int(input())
for i in range(n):
    a = [int(s) for s in input().split()]
    f.append(a)
trt(f)

for i in f:
    for j in i:
        print(j, end = ' ')
    print('')

Если что функция сортировки называется 'trt', потому что проверяющая система считает функции с 'sort' в названии встроенными функциями сортировки,а их использовать нельзя.

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

P.S. Ещё пробовал такое решение, но оно не прошло по тем же критериям, что и прошлое (неизвестно, кстати, на тех же тестах они свалились или же нет):

scores = []
participants = dict()
n_participants = dict()
size = int(input())
for i in range(size):
    data = [int(s) for s in input().split()]
    if data[1] in scores:
        n_participants[data[1]] = data[0]
    else:
        participants[data[1]] = data[0]
    scores.append(data[1])

for i in range(1, size):
    tmp = scores[i]
    j = i - 1
    while j >= 0 and scores[j] > tmp:
        scores[j+1] = scores[j]
        j -= 1
    scores[j+1] = tmp

for i in reversed(scores):
    if i in n_participants:
        if n_participants[i] < participants[i]:
            print(n_participants[i], i)
            print(participants[i], i)
            del participants[i]
            del n_participants[i]
        else:
            print(participants[i], i)
            print(n_participants[i], i)
            del participants[i]
            del n_participants[i]
    else:
        try:
            print(participants[i], i)
        except KeyError:
            continue

1 ответ 1

3

Ваш код выдаёт

4 4 
3 3 
2 3 
3 1 

Вместо

4 4 
2 3 
3 3 
3 1 

В условии сказано:

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

Это означает, что при одинаковом количестве баллов сначала печатается участник с наименьшим номером. Пример, два участника: 2 5 и 3 5 - сначала печатается № 2, потом № 3.

Для правильной работы нужно поменять > на < в выражении return a[0] > b[0]:

def compare(a, b): 
    if a[1] > b[1]:
        return True
    # Если баллы равны
    elif a[1] == b[1]:
        # Сравни номера участников
        # Если номер участника 'a' меньше номера участника 'b'
        # значит можно двигать элемент 'a' дальше по списку,
        # иначе он достиг своего места
        return a[0] < b[0]
    else:
        return False

Вспомогательный код (ввод/вывод) можно переписать следующим образом:

size = int(input())
scores = []

for _ in range(size):
    participant, points = input().split()
    scores.append( (int(participant), int(points)) )

trt(scores)
for participant, points in scores:
    print(participant, points)

Я убрал лишние действия и заменил имена переменных на говорящие.

1
  • как собрать ваш код, просто у меня не получается, спасибо 18 июн 2021 в 12:14

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.