Реши задание на изображении

Пришли, пожалуйста, изображение ещё раз: в текущем чате условия заданий A–E не отображаются, поэтому я не могу решить их без текста.

Это продолжение текущей учебной цели: ты прислал запрошенные изображения с задачами A–E. Решения:

A. Три разметчика

Всего правильных индивидуальных ответов:

\[ 3\cdot70=210. \]

Если итоговый ответ неверен, правильно ответил максимум один разметчик. Если верен — максимум три.

Пусть \(x\) — число правильных итоговых ответов. Тогда

\[ 210\le 3x+(100-x)\cdot1=100+2x, \]

откуда \(x\ge55\). Значение 55 достижимо.

Все 100 итоговых ответов также могут быть правильными: на 10 фотографиях все трое отвечают верно, а на остальных 90 ровно двое отвечают верно.

Ответ:

55 100

B. Как расходится сигнал по графу

В предельном состоянии сигнал в вершине пропорционален её степени.

Степени вершин:

• \(A,B,C,D\): по \(3\);
• \(S\): \(4\).

Сумма степеней:

\[ 4\cdot3+4=16. \]

Сигнал сервера:

\[ 120\cdot\frac{4}{16}=30. \]

Ответ:

30

C. Насколько глубокая модель?

Для глубины \(h\) двоичное дерево может иметь не более \(2^h\) листьев:

\[ 2^h\ge100 \Rightarrow h\ge7. \]

Максимальная глубина дерева со 100 листьями достигается у «цепочки»:

\[ h_{\max}=100-1=99. \]

Возможны все значения от 7 до 99 включительно:

\[ 99-7+1=93. \]

Ответ:

93

D. Ранняя остановка

Считаем подряд идущие эпохи без улучшения. При строгом улучшении счётчик сбрасывается.

import sys

data = list(map(int, sys.stdin.buffer.read().split()))

n, k = data[0], data[1]
loss = data[2:2 + n]

best_error = loss[0]
best_epoch = 1
bad = 0
stop_epoch = n

for i in range(1, n):
    if loss[i] < best_error:
        best_error = loss[i]
        best_epoch = i + 1
        bad = 0
    else:
        bad += 1
        if bad == k:
            stop_epoch = i + 1
            break

print(stop_epoch)
print(best_epoch)

E. Словарь токенов

import re
import sys
from collections import Counter

n, k = map(int, sys.stdin.readline().split())

counts = Counter()

for _ in range(n):
    line = sys.stdin.readline()
    tokens = re.findall(r"[A-Za-z]+", line)
    counts.update(tokens)

ordered = sorted(
    counts.items(),
    key=lambda item: (-item[1], item[0])
)

answer = [str(len(counts))]

for token, frequency in ordered[:k]:
    answer.append(f"{token} {frequency}")

sys.stdout.write("\n".join(answer))

Конечно. Ниже — подробный разбор всех задач A–E.

A. Три разметчика

Дано

• 100 фотографий;
• 3 разметчика;
• каждый разметчик правильно обработал 70 фотографий.

Общее число правильных индивидуальных ответов:

\[ 3\cdot70=210. \]

Итоговый ответ для фотографии выбирается большинством голосов.

Обозначим через \(x\) количество фотографий, для которых итоговый ответ оказался правильным.

Минимальное значение

Если итоговый ответ правильный, то на этой фотографии могло быть не более 3 правильных индивидуальных ответов.

Если итоговый ответ неправильный, то правильным мог быть не более 1 разметчик. Иначе два правильных ответа победили бы большинством.

Поэтому общее число правильных ответов не превосходит

\[ 3x+1(100-x). \]

Так как всего правильных индивидуальных ответов 210, получаем:

\[ 210\le 3x+100-x, \]

\[ 210\le100+2x, \]

\[ 2x\ge110, \]

\[ x\ge55. \]

Значит, меньше 55 правильных итоговых ответов быть не может.

Значение 55 действительно достижимо:

• на 55 фотографиях все трое ответили правильно;
• на остальных 45 фотографиях правильно ответил только один разметчик.

Чтобы каждый разметчик дал ровно 70 правильных ответов, можно распределить 45 одиночных правильных ответов поровну: по 15 каждому.

Тогда каждый получит:

\[ 55+15=70 \]

правильных ответов.

Значит, минимум равен 55.

Максимальное значение

Теоретически все 100 итоговых ответов могут быть правильными.

Например:

• на 10 фотографиях все трое ответили правильно;
• на остальных 90 фотографиях правильно ответили ровно двое.

Тогда каждый итоговый ответ определяется правильно.

На первых 10 фотографиях каждый разметчик получил по 10 правильных ответов. На остальных 90 фотографиях можно распределить ошибки так, чтобы каждый ошибся ровно 30 раз. Тогда каждый дополнительно даст

\[ 90-30=60 \]

правильных ответов.

Итого у каждого:

\[ 10+60=70. \]

Следовательно, максимум равен 100.

Ответ

55 100

---

B. Как расходится сигнал по графу

В задаче сигнал перемещается по неориентированному графу. Из вершины он переходит в одну из соседних вершин с одинаковыми вероятностями.

В таком случае в установившемся режиме сигнал находится в вершине пропорционально степени этой вершины:

\[ p_v=\frac{\deg(v)}{\sum\limits_u\deg(u)}. \]

По рисунку:

• у вершин \(A,B,C,D\) степень равна 3;
• у сервера \(S\) степень равна 4.

Сумма степеней всех вершин:

\[ 3+3+3+3+4=16. \]

Доля сигнала, приходящаяся на сервер:

\[ \frac{4}{16}=\frac14. \]

Если общий сигнал равен 120, то на сервере будет:

\[ 120\cdot\frac14=30. \]

Важно: сигнал распределяется не поровну между вершинами. Вершина с большим количеством рёбер посещается чаще.

Ответ

30

---

C. Насколько глубокая модель?

Пусть у бинарного дерева 100 листьев. Глубина — это количество рёбер от корня до самого глубокого листа.

Минимальная глубина

У бинарного дерева глубины \(h\) не может быть больше

\[ 2^h \]

листьев.

Проверим:

\[ 2^6=64<100, \]

поэтому глубины 6 недостаточно.

\[ 2^7=128\ge100. \]

Значит, минимальная возможная глубина:

\[ h_{\min}=7. \]

Максимальная глубина

Рассмотрим самый длинный путь от корня до листа. Если его длина равна \(h\), то каждая внутренняя вершина этого пути должна иметь ещё одного потомка. В каждой такой боковой ветви будет как минимум один лист.

Таким образом, дерево глубины \(h\) должно иметь как минимум

\[ h+1 \]

листьев.

Так как листьев всего 100:

\[ h+1\le100, \]

\[ h\le99. \]

Глубина 99 достижима: можно построить дерево-«цепочку», в котором на каждом уровне один потомок продолжает длинную ветвь, а второй является листом.

Все ли значения между 7 и 99 возможны?

Да. Для каждого значения

\[ 7\le h\le99 \]

можно построить бинарное дерево со 100 листьями и глубиной \(h\).

Следовательно, число возможных глубин:

\[ 99-7+1=93. \]

Ответ

93

---

D. Ранняя остановка

Идея

Пусть ошибка модели записана для каждой эпохи.

Нужно:

1. найти лучшую ошибку;
2. считать, сколько эпох подряд ошибка не улучшалась;
3. остановить обучение, когда таких эпох стало \(k\);
4. вывести эпоху остановки и эпоху, на которой была достигнута лучшая ошибка.

Улучшением считается только строгое уменьшение ошибки:

\[ \text{new\_loss}<\text{best\_loss}. \]

Если ошибка стала такой же или увеличилась, это считается отсутствием улучшения.

Пример

Пусть

ошибки: 10 8 8 7 9 9 8
k = 3

• эпоха 1: лучшая ошибка 10;
• эпоха 2: ошибка уменьшилась до 8, счётчик сбрасывается;
• эпоха 3: улучшения нет, счётчик равен 1;
• эпоха 4: ошибка уменьшилась до 7, счётчик снова 0;
• эпоха 5: улучшения нет, счётчик 1;
• эпоха 6: улучшения нет, счётчик 2;
• эпоха 7: улучшения нет, счётчик 3 — обучение останавливается.

Ответ был бы:

7
4

Код

import sys

data = list(map(int, sys.stdin.buffer.read().split()))

n, k = data[0], data[1]
loss = data[2:2 + n]

best_error = loss[0]
best_epoch = 1
without_improvement = 0

# Если k эпох без улучшения не наступили,
# обучение заканчивается после последней эпохи.
stop_epoch = n

for i in range(1, n):
    current_error = loss[i]
    current_epoch = i + 1

    if current_error < best_error:
        # Ошибка улучшилась
        best_error = current_error
        best_epoch = current_epoch
        without_improvement = 0
    else:
        # Улучшения нет
        without_improvement += 1

        if without_improvement == k:
            stop_epoch = current_epoch
            break

print(stop_epoch)
print(best_epoch)

Сложность алгоритма:

\[ O(n) \]

по времени. Дополнительная память для самого алгоритма — \(O(1)\), не считая хранения входного массива.

---

E. Словарь токенов

Идея

Для каждой из \(n\) строк нужно:

1. выделить токены;
2. посчитать, сколько раз встречается каждый токен;
3. узнать количество различных токенов;
4. отсортировать токены:
   • сначала по убыванию частоты;
   • при одинаковой частоте — по алфавиту;
5. вывести первые \(k\) токенов.

В качестве токена берём последовательность латинских букв:

[A-Za-z]+

Например, из строки

Hello, world! Hello.

получатся токены:

Hello
world
Hello

Знаки препинания игнорируются.

Сортировка

Используется ключ:

key=lambda item: (-item[1], item[0])

Для пары

(token, frequency)

это означает:

• -item[1] — частота по убыванию;
• item[0] — название токена по возрастанию.

Код

import re
import sys
from collections import Counter

n, k = map(int, sys.stdin.readline().split())

counts = Counter()

for _ in range(n):
    line = sys.stdin.readline()

    # Выделяем последовательности латинских букв
    tokens = re.findall(r"[A-Za-z]+", line)

    # Добавляем найденные токены в счётчик
    counts.update(tokens)

# Сортировка:
# сначала частота по убыванию,
# затем токен по алфавиту
ordered = sorted(
    counts.items(),
    key=lambda item: (-item[1], item[0])
)

answer = [str(len(counts))]

for token, frequency in ordered[:k]:
    answer.append(f"{token} {frequency}")

sys.stdout.write("\n".join(answer))

Что выводит программа

Первая строка:

\[ \text{количество различных токенов}. \]

Следующие строки имеют вид:

токен частота

и содержат не более \(k\) самых частых токенов.

Сложность сортировки при \(m\) различных токенах:

\[ O(m\log m). \]

Краткие ответы:

• А) 55 100
• Б) 30
• В) 93
• Г) программа для определения эпохи остановки и лучшей эпохи.
• Д) программа для подсчёта и сортировки токенов.

В предыдущем изображении были задания только А–Д; условия задания Е у меня нет.

Это самостоятельное новое задание: на изображении задача F «Решающий пень», а предыдущая учебная цель относилась к заданиям А–Д.

Пришли изображение задачи F «Решающий пень» ещё раз или перепиши её условие: сейчас само изображение и текст задачи мне не видны.

Это продолжение текущей учебной цели: ты прислал изображение с условием задачи F «Реша́ющий пень», которую ранее просил решить.