← Все вопросы

Задание 26 КЕГЭ: правильно сортирую данные, но не проходит часть тестов — почему?

Задан 22 месяца назад1.1к просмотров2 ответа
7

Задание 26: читаю данные из файла, сортирую и выбираю что-то (например, минимальный элемент, помещающийся под ограничение, или второй максимум). Логика вроде верная, ответ для первого числа совпадает, а для большого файла — нет. В чём может быть подвох именно в 26?

2 ответа

13
✓ Принятый ответ — помог автору

Задание 26 обычно требует ДВА ответа (например, "минимальный вес последнего вошедшего предмета" и "количество вошедших"), и подвох чаще в логике отбора, а не в самой сортировке. Типовые причины несовпадения на большом файле:

  1. Неверная сортировка по второму ключу. Если при равных значениях важен порядок, добавь второй ключ: data.sort(key=lambda x: (x[0], x[1])).
  2. Жадность работает, но граница считается неверно. Классика 26 — жадно набирать самые маленькие/выгодные, пока не упрёшься в лимит. Проверь, не берёшь ли ты на один элемент больше/меньше из-за < вместо <=.
  3. Тип данных. Если в файле числа, не забудь int() при чтении, иначе сортировка идёт как по строкам ('10' < '9').

Шаблон жадного отбора:

with open('26.txt') as f:
    n = int(f.readline())
    a = sorted(int(f.readline()) for _ in range(n))

limit = 1000
cnt, summ = 0, 0
for x in a:
    if summ + x <= limit:
        summ += x
        cnt += 1
        last = x       # последний вошедший
print(cnt, last)

Проверь именно границу <= и сортировку по правильному ключу — на большом файле всплывает именно это.

5

Очень частая ошибка в 26 на больших данных — сортировка строк вместо чисел. Если читаешь a = f.readlines() и сортируешь, питон сравнивает строки лексикографически: '100' окажется меньше '99'. На маленьком примере может случайно совпасть, а на большом файле разъедется. Лечится одним int() при чтении. Всегда приводи к числам до сортировки.

Ваш ответ

Войдите, чтобы ответить на вопрос.