Инженерный тур. 1 этап

Поскольку игры с метками [Singleplayer] и [Multiplayer] не пересекаются, и каждая игра имеет только одну из этих меток, их процентное соотношение не изменится, если исключить из графика другие метки.

На общей диаграмме [Singleplayer] и [Multiplayer] вместе занимают 54%. Если исключить другие метки, то на графике они будут занимать 100%. Это означает, что их доля увеличится в \(k=100/54\) раза больше. Следовательно, процентное соотношение [Singleplayer] и [Multiplayer] также увеличится в \(k\) раз.

Процентное отношение [Singleplayer] будет равно: \[44\cdot k=\frac{44\cdot 100}{54}=81{,}4814\%.\]

В ответе следует указать 81,48.

Дана маска \([?*a*]\), где знак вопроса может быть заменен на один из 26 символов. Оставшаяся часть маски \([*a*]\) обозначает любую строку, в которой есть хотя бы одна буква «\(a\)».

Так как требуется найти количество строк длиной от 1 до 4, соответствующих маске \([?*a*]\), а знак вопроса уже определен, то требуется определить, сколько строк длины от 1 до 3 соответствуют маске \([*a*]\).

Строк длины 1 с буквой a: 1.

Строк длины 2 с буквой a: \(26^2-25^2=51\).

Строк длины 3 с буквой a: \(26^3-25^2=1951\).

Итого \([*a*]\) преобразуется в одну из \((1+51+1951)=2003\) строк.

Итоговый ответ на задачу: \(26\cdot 2003=52078\).

Задачу можно решить с помощью бинарного поиска по ответу, это следует из следующего замечания: если можно собрать \(p\) пирамидок, то, очевидно, можно собрать и \((p-1)\), и если нельзя собрать \(p\) пирамидок, то тем более нельзя собрать и \((p+1)\).

Попробуем понять, получится ли собрать определенное количество пирамидок, равное \(p\). Для этого будем действовать по принципу жадности: отсортируем все кольца независимо от того, в каком порядке они будут расположены — по возрастанию или по убыванию. В результате получится отсортированный массив колец \(c\).

Затем пройдемся по этому массиву и оденем каждое кольцо \(c_i\) на стержень, на котором находится минимальное количество колец. Если на этом стержне уже есть кольцо того же диаметра, что и \(c_i\), то пропустим это кольцо. Если в итоге на каждом стержне окажется по три кольца, то получится собрать \(p\) пирамидок.

Рассмотрим два неверных подхода к решению задачи.

1. Одевать кольца на стержень с максимальным числом колец. Контрпример: \(c=[1,~2,~3,~4,~4,~4,~5,~5,~5]\), если в распоряжении есть минимум три стержня, то ответ 3 достижим: \((1,~4,~5)\), \((2,~4,~5)\), \((3,~4,~5)\), а при неверном подходе получится пирамидка \((1,~2,~3)\) и незаконченная пирамидка \((4,~5,~\_)\).
2. Посчитать для кольца каждого диаметра, сколько раз можно его использовать — для колец одного диаметра, которых всего менее \(a\) штук, можно их использовать столько раз, сколько их встречается, для колец одного диаметра, которых более \(a\) штук, их используем не более \(a\) раз (иначе по принципу Дирихле будет пирамидка с двумя кольцами одного диаметра) — посчитаем, сколько есть «доступных» колец и поделим на 3, получив число полных пирамидок. Контрпример: \(a=2\), \(c=[1,~1,~2]\). Очевидно, что ни одной пирамидки собрать нельзя, но идея подхода посчитает, что кольца с диаметром 1 можно использовать дважды и кольцо диаметра 2 — всего три кольца, а значит, можно собрать пирамидку.

Сложность: \(\mathcal{O}\left(b\cdot \log{b}+b\cdot \log{\left(min\left(a,~\dfrac{b}{3}\right)\right)}\right)\).

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

import sys

a, b = map(int, sys.stdin.readline().split())
c = list(map(int, sys.stdin.readline().split()))

c.sort()

l, r = 1, min(b // 3, a)

while l <= r:
    m = (l + r) // 2
    cycles = 0

    p = [0 for i in range(m)]
    it = 0
    for i in range(b):
        if p[it] < c[i]:
            p[it] = c[i]
            it += 1
            if it == m:
                it = 0
                cycles += 1

    if cycles < 3:
        r = m - 1
    else:
        l = m + 1

print(max(0, r))

Задачу можно решить методом динамического программирования. Определим два массива \(upper\) и \(lower\), оба размера \((n+1)\), следующим образом:

• \(upper_i\) — минимальное количество нажатий на клавиатуре для печати первых \(i\) символов строки \(s\) с установленным в конце верхним регистром;
• \(lower_i\) — минимальное количество нажатий на клавиатуре для печати первых \(i\) символов строки \(s\) с установленным в конце нижним регистром.

База динамики. Изначально \(lower_0=0\), \(upper_0=1\), так как изначально клавиатура установлена на нижний регистр, и печатать ничего не нужно, остальные значения \(lower\) и \(upper\) не определены.

Переход динамики. Будем просматривать строку \(s\) слева направо. Пусть сейчас мы смотрим на \(i\)-й символ строки, тогда есть два варианта событий:

1. Символ \(s_{(i-1)}\) (у строки 0-индексация) в нижнем регистре, тогда \(lower_i\) обновится на минимальное значение из следующих:

   • \((lower_{(i-1)}+1)\) — поскольку уже напечатаны \((i-1)\) символов, и у клавиатуры был установлен нижний регистр, то текущий символ напечатаем за одно нажатие;
   • \((upper_{(i-1)}+2)\) — используем нажатие на CAPS для переключения регистра на нижний. После того как напечатаны \((i-1)\) символов и включен верхний регистр, нажимаем на клавишу символа.

   \(upper_i\) же примет минимальное значение из следующих:

   • \((lower_i+1)\) — используем ответ для \(lower_i\), но тратим одно действие на нажатие CAPS, переключая регистр на верхний;
   • \((upper_{(i-1)}+2)\) — берем ответ для \(upper_{(i-1)}\), нажимаем на SHIFT, затем на клавишу с символом. Это требует два действия, и после нажатия на клавишу с символом регистр переключается обратно.
2. Символ \(s_{(i-1)}\) в верхнем регистре. Тогда делаем все то же самое, что описано выше, но подменяем понятия \(lower\) и \(upper\).

Ответ на задачу — минимум из \(lower_n\) и \(upper_n\). Также можно использовать не два, но один двухмерный массив, как показано в решении ниже.

Сложность: \(\mathcal{O}(n)\).

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

import sys

n = int(sys.stdin.readline())
s = str(sys.stdin.readline().strip())

dp = [[0 for i in range(n + 1)], [0 for i in range(n + 1)]]
dp[1][0] = 1

for i in range(n):
    if s[i].lower() == s[i]:
        # буква в нижнем регистре
        dp[0][i + 1] = 1 + min(dp[0][i], 1 + dp[1][i])
        dp[1][i + 1] = min(dp[0][i + 1] + 1, 2 + dp[1][i])
    else:
        # буква в верхнем регистре
        dp[1][i + 1] = 1 + min(dp[1][i], 1 + dp[0][i])
        dp[0][i + 1] = min(dp[1][i + 1] + 1, 2 + dp[0][i])

print(min(dp[0][-1], dp[1][-1]))

Отсортируем массив \(a\) и будем искать в нем такой отрезок \([l,\,r]\), на котором встречается ровно \(k\) различных чисел, а разница между \(a[r]\) и \(a[l]\) будет максимальной разницей в этом наборе. По всем таким наборам нужно найти минимальную разницу.

Решим задачу методом двух указателей. Создадим \(left=0\) и будем итерироваться по массиву переменной \(right\), поддерживая на отрезке \(k\) различных чисел (это можно сделать, используя счетчик и, например, словарь с количеством вхождений каждого элемента на отрезке).

Если на отрезке менее \(k\) различных чисел, то сдвигаем \(right+1\), иначе, если на отрезке \(k\) различных чисел, то пытаемся обновить ответ, как минимум, из того, что в нем находится и \(a[right]\), и \(a[left]\), затем сдвигаем \(left+1\).

Сложность: \(\mathcal{O}(n+n\cdot \log n)\), что то же самое, что \(\mathcal{O}(n\cdot \log n)\).

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

import sys

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

a.sort()
mn = 1 << 60
f = {}

r = 0
for i in range(n):
    if a[i] not in f or f[a[i]] == 0:
        f[a[i]] = 1
        k -= 1
    else:
        f[a[i]] += 1

    while k == 0:
        mn = min(mn, a[i] - a[r])
        if f[a[r]] == 1:
            k += 1
        f[a[r]] -= 1
        r += 1

if mn == 1 << 60:
    print(-1)
else:
    print(mn)

По закону Джоуля – Ленца: \[\begin{gather} Q_1=I^2_1\cdot R_1\cdot t_1;\\ Q_3=I^2_3\cdot R_3\cdot t_3. \end{gather}\] Так как элементы \(R_1\) и \(R_2\) соединены параллельно и подключены к элементу \(R_3\) последовательно, то \[I_3=I_1+I_2 ~\text{и}~ U_1=U_2.\] Из закона Ома: \[\begin{gather} I_1\cdot R_1=I_2\cdot R_2~\Rightarrow~ I_1=\frac{I_2\cdot R}{3R}=\frac{1}{3} I_2;\\ I_3=I_2+\frac{1}{3} I_2=\frac{4}{3} I_2~\Rightarrow~ I_2=\frac{3}{4} I_3~\Rightarrow~ I_1=\frac{1}{4} I_3;\\ Q_1=\left(\frac{1}{4} I_3 \right)^2\cdot 3R_3\cdot t_1=\left(\frac{1}{4} I_3 \right)^2\cdot 3R_3\cdot t_3 \frac{t_1}{t_3} =\frac{3}{16} \cdot Q_3\cdot \frac{t_1}{t_3};\\ Q_1=\frac{3}{16}\cdot 220\cdot \frac{120}{30}=165 \text{~Дж}. \end{gather}\]

Общее сопротивление цепи в первом случае равно: \[R_1=\frac{R+r}{2}.\]

Мощность в цепи равна: \[P_1=\frac{U^2}{R_1} =\frac{2\cdot U^2}{R+r},\] где U — напряжение между точками \(A\) и \(B\).

После того как одну из ламп заменили резистором, общее сопротивление цепи стало равным: \[R_2=\frac{2R\cdot (R+r)}{3R+r},\] а мощность: \[P_2=\frac{U^2 (3R+r)}{2R\cdot (R+r)}.\]

По условию \[P_2=k\cdot P_1.\]

Тогда \[\frac{U^2 (3R+r)}{2R\cdot (R+r)}=k\cdot \frac{2\cdot U^2}{R+r},\] отсюда получаем: \[r=(4k-3)\cdot R=(4\cdot 5-3)\cdot 100= 1{,}7 \text{~кОм}.\]

Емкости конденсаторов равны: \[\begin{gather} C_2=2C_1;\\ C_3=3C_2=6C_1. \end{gather}\] Найдем заряд на первом конденсаторе после того, как замкнули первый ключ: \[q_0=C_1\cdot U_{\text{ист}}.\]

Затем найдем отношение зарядов после замыкания второго ключа, зная, что после этого напряжение на \(C_1\) и \(C_2\) стало одинаковым: \[\frac{q_1}{C_1} =\frac{q_2}{C_2} ~\Rightarrow~\frac{q_1}{q_2} =\frac{C_1}{C_2} =\frac{1}{2}~\Rightarrow~q_1=\frac{1}{2} q_2.\]

Известно, что \[q_0=q_1+q_2~\Rightarrow~q_2=\frac{2}{3} q_0 \text{~и~} q_1=\frac{1}{3} q_0.\]

Найдем заряды на конденсаторах после замыкания третьего ключа: \[\frac{q'_2}{q_3} =\frac{C_2}{C_3 }=\frac{1}{3}~\Rightarrow~q'_2=\frac{1}{3} q_3.\] Известно, что \[q_2=q'_2+q_3~\Rightarrow~q_3=\frac{3}{4} q_2=\frac{1}{2} q_0\] и \[q'_2=\frac{1}{4} q_2=\frac{1}{6} q_0.\] Находим напряжения на каждом конденсаторе: \[\begin{gather} U_{C_1}=\frac{C_1 \cdot U_{\text{ист}}}{3\cdot C_1}=4 \text{~В},\\ U_{C_2}=\frac{C_1\cdot U_\text{ист}}{6\cdot C_2} = \frac{U_\text{ист}}{12}=1 \text{~В},\\ U_{C_3}=\frac{C_1\cdot U_\text{ист}}{2\cdot C_3} = \frac{U_\text{ист}}{12}=1 \text{~В}. \end{gather}\]

Диод, очевидно, находится в открытом состоянии.

Мощности, выделяемые на элементах: \[P_R=U_0\cdot I_R\] и \[P_\text{д}=U_0\cdot I_\text{д}.\] Отсюда \[\frac{P_R}{P_\text{д}} =\frac{I_R}{I_\text{д}}.\] Эквивалентная схема.

Методом наложенных контуров находим токи: \[I_R=0+\frac{U_0}{R}\] и \[I_\text{д}=\frac{16U_0}{R}-\frac{9R\cdot U_0}{R^2},\] \[\frac{P_R}{P_\text{д}} =\frac{I_R}{I_\text{д}} = \frac{\frac{U_0}{R}}{\left(\frac{16U_0}{R}-\frac{9R\cdot U_0}{R^2} \right)}\approx 0{,}1.\]

Найдем ток во входной цепи: \[I_\text{вх}=\frac{U_1}{R_1} =\frac{32}{4000}=8 \text{~мА}.\] По графику находим выходной ток, он равен 7 мА, но необходимо проверить, возможен ли такой ток. Найдем максимально возможный ток в выходной цепи: \[I_\text{вых}=\frac{U_2}{R_2} =\frac{15}{3000}=5 \text{~мА}.\] Можно сделать вывод, что фототранзистор вышел в насыщение, и ток в выходной цепи составляет 5 мА.