Предметный тур. Информатика. 3 этап

Можно получить решение, встроив информацию о \(15 \times 15\) сетке в исходный код, но это занимает много времени. Поскольку сетка симметрична относительно центрального квадрата (8-я строка и 8-й столбец), можно решить задачу более простым способом.

В данной сетке квадрат окрашен в черный цвет, если «расстояние» от центрального квадрата до него нечетное, и в белый, если четное. В частности, квадрат на \(r\)-й строке и \(c\)-м столбце черный тогда и только тогда, когда расстояние Чебышева (шахматное расстояние) от центрального квадрата, \(\max(|r - 8|, |c - 8|)\), нечетное (здесь \(|x|\) обозначает абсолютное значение \(x\)).

Пример программы-решения

Ниже представлено решение на языке Python.

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    x = min(n, 15 - n + 1)
    x = min(x, min(m, 15 - m + 1))
    print("black" if x % 2 == 1 else "white")

1. Инициализация:

   • Текущая позиция: \(pos = 1\).
   • Счетчик команд: \(count = 0\).
   • Множество посещенных ячеек: \(visited = \varnothing\).

2. Основной цикл:

   • Пока \(pos \neq n\) и \(pos \notin visited\):

     • Добавляем \(pos\) в \(visited\).
     • Перемещаемся: \(pos \gets a_{pos}\).
     • Увеличиваем счетчик: \(count \gets count + 1\).

3. Проверка результата:

   • Если \(pos = n\): возвращаем \(count\).
   • Иначе (если \(pos \in visited\)): возвращаем \(-1\) (робот зациклился).

• Максимальное количество шагов не превосходит \(n\), так как после \(n\) шагов робот гарантированно войдет в цикл (по принципу Дирихле).
• Использование множества \(visited\) позволяет детектировать циклы за \(\mathcal{O}(1)\) на каждом шаге.
• Алгоритм имеет временную сложность \(\mathcal{O}(n)\) и пространственную сложность \(\mathcal{O}(n)\).

Пример программы-решения

Ниже представлено решение на языке Python.

n = int(input())
a = list(map(int, input().split())) 

cur_pos = 1
steps = 0

while cur_pos != n:
    steps += 1
    cur_pos = a[cur_pos - 1]
    if steps > n: 
        steps = -1
        break

print(steps)

Задача заключается в подсчете количества троек \((i, j, k)\) таких, что \(A_i < B_j < C_k\). Если зафиксировать \(j\), то искомое количество будет равно произведению количества \(i\), для которых \(A_i < B_j\), и количества \(k\), для которых \(B_j < C_k\).

Таким образом, для каждого \(j\) можно подсчитать количество подходящих \(i\) и \(k\), перемножить их и сложить результаты.

Как же подсчитать количество \(i\) и \(k\)? Если просто перебирать все элементы массива, то сложность будет \(\mathcal{O}(N^2)\), что неприемлемо.

Предварительно отсортируем массивы \(A\) и \(C\). Тогда количество \(i\) и \(k\) можно найти с помощью бинарного поиска. В C++ для этого удобно использовать стандартные функции lower_bound и upper_bound.

Итоговая временная сложность составит \(\mathcal{O}(N \log N)\), что является приемлемым.

Пример программы-решения

Ниже представлено решение на языке Python.

import bisect
 
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
 
a.sort()
b.sort()
c.sort()
 
cnt = 0
 
for i in range(n):
    p = bisect.bisect_left(a, b[i])
    q = bisect.bisect_right(c, b[i])
    q = n - q
    cnt += p * q
 
print(cnt)

Вместо того чтобы удалять строки и столбцы по одному, как в исходной постановке задачи, можно рассмотреть следующую операцию, выполняемую ровно один раз: «выбрать некоторые (возможно, ни одной) строки и столбцы исходной матрицы \(A\) и удалить выбранные строки и столбцы одновременно».

Например, для следующей матрицы \(A\), приведенной в примере 1, \[\begin{matrix} 1 &2 &3 &4 &5\\ 6 &7 &8 &9 &10\\ 11 &12 &13 &14 &15\\ 16 &17 &18 &19 &20 \end{matrix}\] можно выбрать первую строку, третью строку, второй столбец и пятый столбец и удалить их одновременно, чтобы получить следующую матрицу \(B\), приведенную в примере 1: \[\begin{matrix} 6 &8 &9\\ 16 &18 &19 \end{matrix}\]

Чтобы определить, можно ли сделать матрицу \(A\) равной матрице \(B\) с помощью таких операций, достаточно перебрать все \(2^{H_1}\) способов выбора «удалять ли каждую из \(H_1\) строк» и все \(2^{W_1}\) способов выбора «удалять ли каждый из \(W_1\) столбцов» (всего \(2^{(H_1 + W_1)}\) способов) и проверить, делает ли какой-либо из них матрицу \(A\) равной матрице \(B\).

Для перебора всех \(2^{(H_1 + W_1)}\) способов выбора строк и столбцов можно использовать метод битового перебора (bit brute-forcing), который опишем ниже:

• Каждый способ выбора «удалять ли каждую из \(H_1\) строк» представляется \(H_1\)-битовым двоичным неотрицательным числом \(X\), где:

  • Для \(i = 0, 1, 2, \dots, H_1 - 1\):

    • Если \(i\)-я строка удаляется, то \(i\)-й бит (считая с младшего разряда) числа \(X\) равен \(1\).
    • Если \(i\)-я строка не удаляется, то \(i\)-й бит равен \(0\).
• Например, выбор удаления первой и третьей строк из 5 строк может быть представлен числом \(00101\) в двоичной системе. Таким образом, все \(2^{H_1}\) способов выбора строк могут быть представлены числами \(000\ldots 00\), \(000\ldots 01\), \(\ldots\), \(111\ldots 11\) в двоичной системе или числами \(0, 1, \ldots, 2^{H_1} - 1\) в десятичной системе.
• Аналогично способы выбора «удалять ли каждый из \(W_1\) столбцов» могут быть представлены числами \(0, 1, \dots, 2^{W_1} - 1\).

Таким образом можно перебрать все комбинации способов выбора строк и столбцов с помощью двойного вложенного цикла, где:

• первый цикл перебирает способы выбора строк: \(0, 1, \ldots, 2^{H_1} - 1\);
• второй цикл перебирает способы выбора столбцов: \(0, 1, \ldots, 2^{W_1} - 1\).

Пример программы-решения

Ниже представлено решение на языке Python.

h1, w1 = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h1)]

h2, w2 = map(int, input().split())
b = [list(map(int, input().split())) for _ in range(h2)]

for i in range(1 << h1):
    for j in range(1 << w1):
        hvec = []
        wvec = []
        for k in range(1, h1 + 1):
            if (i & (1 << (k - 1))) == 0:
                hvec.append(k)
        for k in range(1, w1 + 1):
            if (j & (1 << (k - 1))) == 0:
                wvec.append(k)
        if len(hvec) != h2 or len(wvec) != w2:
            continue
        
        match = True
        for k in range(1, h2 + 1):
            for l in range(1, w2 + 1):
                if a[hvec[k - 1] - 1][wvec[l - 1] - 1] != b[k - 1][l - 1]:
                    match = False
                    break
            if not match:
                break
        if match:
            print("Yes")
            exit()

print("No")

Дан прямоугольник размером \(n \times m\), где каждая ячейка раскрашена в один из цветов. Требуется подсчитать количество прямоугольников, раскрашенных ровно в один цвет.

Для каждой строки \(d\) и каждого столбца \(l\) перебираем все возможные прямоугольники, начиная с \((d, l)\). Для каждого прямоугольника находим минимальную высоту столбцов в диапазоне \([l, r]\) и добавляем ее к ответу.

• \(n\) — количество строк.
• \(m\) — количество столбцов.
• \(a\) — матрица размера \(n \times m\), содержащая цвета ячеек.
• \(h\) — массив высот столбцов, где \(h[i]\) — количество подряд идущих ячеек одного цвета сверху в столбце \(i\).
• \({ans}\) — итоговый ответ (количество одноцветных прямоугольников).

1. Инициализируем массив \(h\) единицами.

2. Для каждой строки \(d\) от \(0\) до \(n-1\):

   • Для каждого столбца \(l\) от \(0\) до \(m-1\):

     • Инициализируем \(\text{min\_h} = h[l]\) и \(r = l\).

     • Пока \(r < m\) и \(a[d][r] = a[d][l]\):

       • Обновляем \(\text{min\_h} = \min(\text{min\_h}, h[r])\).
       • Добавляем \(\text{min\_h}\) к \({ans}\).
       • Увеличиваем \(r\) на \(1\).

   • Если \(d \neq n-1\), обновляем массив \(h\):

     • Для каждого столбца \(i\) от \(0\) до \(m-1\):

       • Если \(a[d][i] \neq a[d+1][i]\), сбрасываем \(h[i] = 1\).
       • Иначе увеличиваем \(h[i]\) на \(1\).
3. Выводим \({ans}\).

• Временная сложность: \(\mathcal{O}(n \cdot m^2)\).
• Пространственная сложность: \(\mathcal{O}(m)\).

Пример программы-решения

Ниже представлено решение на языке Python.

n, m = map(int, input().split())
a = [input().strip() for _ in range(n)]
h = [1] * m  # Массив высот столбцов

ans = 0  # Итоговый ответ
for d in range(n):
    for l in range(m):
        min_h = h[l]  # Минимальная высота в текущем прямоугольнике
        r = l
        # Идём вправо, пока цвет ячеек совпадает
        while r < m and a[d][r] == a[d][l]:
            min_h = min(min_h, h[r])  # Обновляем минимальную высоту
            ans += min_h  # Добавляем количество прямоугольников
            r += 1
    # Обновляем высоты столбцов для следующей строки
    if d != n - 1:
        for i in range(m):
            if a[d][i] != a[d + 1][i]:
                h[i] = 1  # Сбрасываем высоту, если цвет меняется
            else:
                h[i] += 1  # Увеличиваем высоту, если цвет совпадает
print(ans)