Афанасий уже 2 недели занимался написанием кода, способного решать японские сканворды с поддержкой девяти цветов, когда на очередной встрече команды коллега сообщил ему, что способен сам справляться с задачей быстрее, и в программе уже нет смысла.

Условие

Афанасий уже 2 недели занимался написанием кода, способного решать японские сканворды с поддержкой девяти цветов, когда на очередной встрече команды коллега сообщил ему, что способен сам справляться с задачей быстрее, и в программе уже нет смысла.

Но Афанасий, будучи оптимистом, решил для себя ещё позаниматься этой задачей и сделать следующее — подсчитать, насколько хорошо коллега справляется со сканвордами. Для этой оценки он выбрал некий аналог метрики IoU — подсчёт будет идти аналогично классическому Intersection Over Union, но по цветам.

Работает это по задумке так: каждая совпавшая в оригинале и решении по цвету клеточка добавляет 1 в числитель, а в знаменатель 1 добавляется за каждую клеточку этого в оригинале и решении (за совпавшие клеточки добавляется всего одна единица). После этого будет происходить усреднение по числу цветов в оригинале картинки, округлённое до двух знаков после запятой; ноль не является цветом, поэтому при расчётах не стоит считать метрику для клеточек этого цвета. На вход на первой строке будет подаваться, сколько строк n и столбцов m (именно в таком порядке) содержит исходная картинка. Затем идет 2n строк, содержащих m разделенных пробелами чисел — первые n строк относятся к отправленному решению сканворда, а следующие n — к исходной картинке. Будем считать, что на каждой строке, начиная со второй, содержится ровно m чисел.

В качестве ответа выведите одно число, округлённое до двух знаков после запятой, как в примерах.

Вот несколько примеров:

1. Первый пример [phone]
   -> 1.0 Объяснение: вклад совпавших и не совпавших ячеек (1.0 + 1.0 + 1.0 + 1.0) / количество цветов (4)

2. Второй пример [phone]
   -> 0.08 Объяснение: вклад совпавших и не совпавших ячеек (0.25 + 0.0 + 0.0) / количество цветов (3); ноли не считаем, ни как клетки в представлениях, ни в количестве цветов.

3. Третий пример [phone] вот тут начинается отправленное изображение
   [phone] -- вот тут заканчивается отправленное изображение
   0 1 2 -- вот здесь начинается исходное изображение
   [phone]
   -> 0.47 Объяснение: вклад совпавших и не совпавших ячеек (0.4 + 0.5 + 0.5) / количество цветов (3); ноли не считаем ни как клетки в представлениях, ни в количестве цветов.

4. Четвертый пример [phone]
   -> 0.0 Объяснение: вклад совпавших и не совпавших ячеек (0.0) / количество цветов (1); ноли не считаем ни как клетки в представлениях, ни в количестве цветов.

Ответ

Для каждого ненулевого цвета исходной картинки вычисляем IoU: совпадения делим на объединение клеток этого цвета. Затем усредняем значения только по цветам оригинала.

Объединение для цвета c равно count_original[c] + count_prediction[c] − intersection[c]. Ошибочно покрашенная клетка увеличивает объединение предсказанного цвета, если этот цвет входит в оригинал.

n, m = map(int, input().split())
prediction = [list(map(int, input().split())) for _ in range(n)]
pred = [0] * 10
orig = [0] * 10
same = [0] * 10
for i in range(n):
    row = list(map(int, input().split()))
    for j, actual in enumerate(row):
        guessed = prediction[i][j]
        pred[guessed] += 1
        orig[actual] += 1
        if guessed == actual:
            same[actual] += 1
colors = [c for c in range(1, 10) if orig[c] > 0]
if not colors:
    raise ValueError('Не задана метрика для оригинала без цветов')
score = sum(same[c] / (orig[c] + pred[c] - same[c]) for c in colors) / len(colors)
print(f'{score:.2f}')

Время O(nm), память O(nm). Для полностью нулевого оригинала среднее не определено: правило этого случая нужно уточнить в условии, а не придумывать значение.