Задание 26 КЕГЭ: правильно сортирую данные, но не проходит часть тестов — почему?
Задание 26: читаю данные из файла, сортирую и выбираю что-то (например, минимальный элемент, помещающийся под ограничение, или второй максимум). Логика вроде верная, ответ для первого числа совпадает, а для большого файла — нет. В чём может быть подвох именно в 26?
2 ответа
Задание 26 обычно требует ДВА ответа (например, "минимальный вес последнего вошедшего предмета" и "количество вошедших"), и подвох чаще в логике отбора, а не в самой сортировке. Типовые причины несовпадения на большом файле:
- Неверная сортировка по второму ключу. Если при равных значениях важен порядок, добавь второй ключ:
data.sort(key=lambda x: (x[0], x[1])). - Жадность работает, но граница считается неверно. Классика 26 — жадно набирать самые маленькие/выгодные, пока не упрёшься в лимит. Проверь, не берёшь ли ты на один элемент больше/меньше из-за
<вместо<=. - Тип данных. Если в файле числа, не забудь
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)
Проверь именно границу <= и сортировку по правильному ключу — на большом файле всплывает именно это.
Очень частая ошибка в 26 на больших данных — сортировка строк вместо чисел. Если читаешь a = f.readlines() и сортируешь, питон сравнивает строки лексикографически: '100' окажется меньше '99'. На маленьком примере может случайно совпасть, а на большом файле разъедется. Лечится одним int() при чтении. Всегда приводи к числам до сортировки.