Задание 26 ЕГЭ по информатике

1. 1.

   pairs = [(5, 2), (1, 9), (3, 1)]
   pairs.sort(key=lambda p: p[1])
   print(pairs)   # [(3, 1), (5, 2), (1, 9)]

Ответ: Пары упорядочены по второму элементу

1. 1. Начало: a = [5, 1, 4, 2]. Длина 4, значит внешний цикл сделает 4 прохода, но упорядочится список раньше.
2. 2. Проход 1 (i = 0), внутренний цикл по j от 0 до 2.
3. 3. j = 0: сравниваем a[0]=5 и a[1]=1. Левый больше → меняем. a = [1, 5, 4, 2].
4. 4. j = 1: сравниваем a[1]=5 и a[2]=4. Левый больше → меняем. a = [1, 4, 5, 2].
5. 5. j = 2: сравниваем a[2]=5 и a[3]=2. Левый больше → меняем. a = [1, 4, 2, 5]. Проход закончен: пятёрка всплыла в конец и больше не сдвинется.
6. 6. Проход 2 (i = 1), внутренний цикл по j от 0 до 1 — последний элемент уже на месте.
7. 7. j = 0: a[0]=1 и a[1]=4. Левый меньше → не трогаем. a = [1, 4, 2, 5].
8. 8. j = 1: a[1]=4 и a[2]=2. Левый больше → меняем. a = [1, 2, 4, 5]. Теперь на местах два последних элемента.
9. 9. Проход 3 (i = 2), j пробегает только 0: a[0]=1 и a[1]=2, менять нечего.
10. 10. Проход 4 (i = 3): внутренний цикл пустой. Итог: [1, 2, 4, 5].
11. 11. Считаем работу: 3 + 2 + 1 + 0 = 6 сравнений для четырёх элементов. В общем виде это n(n−1)/2 — отсюда и оценка O(n²). Для n = 1000 это уже полмиллиона сравнений, для n = 100 000 — пять миллиардов.

Ответ: [1, 2, 4, 5] за 6 сравнений

1. 1. Индексы: a[0]=3, a[1]=7, a[2]=12, a[3]=18, a[4]=25, a[5]=31, a[6]=44, a[7]=59.
2. 2. Ищем 44. Начало: lo = 0, hi = 7.
3. 3. Шаг 1. mid = (0 + 7) // 2 = 3, a[3] = 18. Это меньше 44 → искомое правее, lo = 4. Участок поиска: индексы 4…7.
4. 4. Шаг 2. mid = (4 + 7) // 2 = 5, a[5] = 31. Меньше 44 → lo = 6. Участок: индексы 6…7.
5. 5. Шаг 3. mid = (6 + 7) // 2 = 6, a[6] = 44. Совпало → ответ: индекс 6. Три шага вместо семи сравнений при переборе подряд.
6. 6. Теперь ищем 20. Начало: lo = 0, hi = 7.
7. 7. Шаг 1. mid = 3, a[3] = 18 < 20 → lo = 4.
8. 8. Шаг 2. mid = (4 + 7) // 2 = 5, a[5] = 31 > 20 → hi = 4. Участок сузился до одного индекса 4.
9. 9. Шаг 3. mid = 4, a[4] = 25 > 20 → hi = 3. Теперь lo = 4 больше hi = 3, условие while lo <= hi нарушено, цикл заканчивается — числа в списке нет.
10. 10. Обратите внимание на mid + 1 и mid - 1. Если написать lo = mid вместо lo = mid + 1, участок перестанет сужаться, когда в нём останется два элемента, и цикл зациклится навсегда. Это самая частая ошибка в самописном двоичном поиске.
11. 11. И на (lo + hi) // 2: деление обязательно целочисленное. Обычное / вернёт дробь, и обращение a[3.5] уронит программу.

Ответ: 44 стоит на индексе 6; числа 20 в списке нет

1. 1.

   a = [int(x) for x in open('26.txt')]
   a.sort()

   limit = 30
   summa = 0
   kolichestvo = 0
   for x in a:
       if summa + x > limit:
           break
       summa += x
       kolichestvo += 1

   print(kolichestvo, summa)

2. 2. Шаг 1. Сортируем: [12, 5, 9, 3, 14, 7] превращается в [3, 5, 7, 9, 12, 14].
3. 3. Шаг 2. Начальное состояние: summa = 0, kolichestvo = 0.
4. 4. Шаг 3. x = 3. Проверка 0 + 3 = 3, это не больше 30 → берём. summa = 3, kolichestvo = 1.
5. 5. Шаг 4. x = 5. 3 + 5 = 8 ≤ 30 → берём. summa = 8, kolichestvo = 2.
6. 6. Шаг 5. x = 7. 8 + 7 = 15 ≤ 30 → берём. summa = 15, kolichestvo = 3.
7. 7. Шаг 6. x = 9. 15 + 9 = 24 ≤ 30 → берём. summa = 24, kolichestvo = 4.
8. 8. Шаг 7. x = 12. 24 + 12 = 36, а это больше 30 → break, цикл обрывается.
9. 9. Шаг 8. Ответ: 4 файла суммарным размером 24 Мбайт. Остаток диска 6 Мбайт, и заполнить его нечем: самый маленький из оставшихся файлов — 12 Мбайт.
10. 10. Почему здесь break, а не continue. Список отсортирован по возрастанию: если очередной файл не поместился, то и все следующие, которые не меньше него, тоже не поместятся. Продолжать перебор незачем. А вот если бы вопрос звучал «какой суммарный размер можно записать», break был бы ошибкой: за большим файлом мог бы найтись маленький, который влезает в остаток.
11. 11. Проверка ответа перебором: из шести файлов пять самых маленьких дают 3+5+7+9+12 = 36 > 30, значит пять взять нельзя ни в каком сочетании. Четыре самых маленьких дают 24 ≤ 30 — значит, 4 достижимо. Ответ верен.

Ответ: 4 24

1. 1. Сортируем объёмы по возрастанию: sorted(a) — мелкие первыми.
2. 2. Идём по отсортированному списку, поддерживая занятый объём total и счётчик cnt.
3. 3. Пока total + size <= LIMIT: добавляем заявку (total += size, cnt += 1).
4. 4. Как только очередная не влезает — можно прекратить (дальше только крупнее).
5. 5. cnt — максимальное число заявок.

Ответ: cnt — максимум помещающихся заявок