Начнём с конца.
Задача E. Multithreading
Придётся разобрать несколько случаев. Пусть S это сумма всех ni. Если W ≤ 0 или W > S то, очевидно, ответ IMPOSSIBLE. В случае N = 1 ответ существует только при W = S, это S итераций единственного потока.
Запишем вместо номеров потока скобки разных видов, расставить открывающие и закрывающие просто - соответствующие пары скобок одного типа должны идти последовательно, не пересекаяся. Если в программе есть подпоследовательность типа [(]) то можно заменить её на ([]), понятно, что результат будет тот же. Таким образом, достаточно помещать итерации разных потоков одну в другую, как скобки.
Получить W = 1 можно только поместив все пары скобок внутрь какой-то одной. Поскольку пара скобок не может содержать пару такого же типа, найти найти такой i, что ni = 1. Если же такого i нету, ответ IMPOSSIBLE.
В остальных случаях помогает следующая стратегия. Пусть W - S = K, значит надо K ≤ S - 2 пар скобок поместить внутрь. Возьмём два потока, 1 и 2, зарезервируем по одной итерации (паре скобок) каждого из этих потоков для того, чтобы помещать них "лишние" итерации, назовём их A1 и A2. В качестве "лишних" итераций можно взять любые K итераций относящиеся к любым потокам, только итерации второго потока следует размещать внутрь A1, а итерации первого - в A2.
Оставшиеся W - 2 итераций расположим последовательно, без пересечений.
Задача D. Билеты
Всё просто. Если пришёл покупатель с десяткой, то записываем открывающую скобку, с двадцаткой - закрывающую. Будет n открывающих скобок и m закрывающих. Требуется посчитать вероятность того, что в баланс в получившейся скобочной последовательности баланс не падал меньше k.
Понятно, что если k ≥ m, то ответ 1.0, а если k + n < m то ответ 0.0.
В остальных случаях можно применить принцип отражения, использующийся при аналитическом выводе формулы для чисел Каталана.
Требуется найти количество монотонных путей в решётке (0, 0) × (n, m) таких, что не содержат точек (x, y), x + k < y. В каждом не подходящем нам пути можно взять первое ребро, лежащее выше линии x + k = y, и отразить весь оставшийся за ним путь, получив таким образом монотонный путь в решётке (n + k + 1) × (m - k - 1). Соответствие является биективным.
Получим, что количество путей не подходящих путей равно Cm - k - 1m + n. Общее число путей равно Cnn + m. Значит вероятность того что баланс нарушится - P = Cm - k - 1m + n / Cnn + m = m(m - 1)(m - 2)...(m - k) / (n + k + 1) / (n + k) / ... / (n + 1).
Ответом является число 1.0 - P
При чётном числе строк и столбцов можно объединить пары вертикальных и горизонтальных паркетин чтобы получить недостающие квадратики 2 × 2.
При нечётном числе строк надо выложить одну строку из горизонтальных кусочков паркета, перейдя таким образом к случаю чётное × чётное.
Аналогично с нечётным числом столбцов.
Нумеровать куски можно по-разному, лично я для обозначения кусочка с левым верхним углом (i, j) использовал букву номер (i + 5j) mod 26. Это гарантирует что в квадрате длиной 5 с центром (i, j) таких же букв нет.
Задача B. Правильная скобочная последовательность
Пройдём по строчке, попутно считая ответ. Будем складывать открывающие скобки без пары в стек (достаточно хранить их количество). Если встретили открывающую - кладём её в стек. Если встретили закрывающую скобку, и в запасе есть хоть одна открывающая - достаём её из запаса, а ответ увеличиваем на 2.
Задача A. Почти простые числа
Рассчитаем все простые числа до N. Для каждого натурального числа меньшего N проверим, что оно делится ровно на два простых, затем увеличим ответ.
Задача E. Multithreading
Придётся разобрать несколько случаев. Пусть S это сумма всех ni. Если W ≤ 0 или W > S то, очевидно, ответ IMPOSSIBLE. В случае N = 1 ответ существует только при W = S, это S итераций единственного потока.Запишем вместо номеров потока скобки разных видов, расставить открывающие и закрывающие просто - соответствующие пары скобок одного типа должны идти последовательно, не пересекаяся. Если в программе есть подпоследовательность типа [(]) то можно заменить её на ([]), понятно, что результат будет тот же. Таким образом, достаточно помещать итерации разных потоков одну в другую, как скобки.
Получить W = 1 можно только поместив все пары скобок внутрь какой-то одной. Поскольку пара скобок не может содержать пару такого же типа, найти найти такой i, что ni = 1. Если же такого i нету, ответ IMPOSSIBLE.
В остальных случаях помогает следующая стратегия. Пусть W - S = K, значит надо K ≤ S - 2 пар скобок поместить внутрь. Возьмём два потока, 1 и 2, зарезервируем по одной итерации (паре скобок) каждого из этих потоков для того, чтобы помещать них "лишние" итерации, назовём их A1 и A2. В качестве "лишних" итераций можно взять любые K итераций относящиеся к любым потокам, только итерации второго потока следует размещать внутрь A1, а итерации первого - в A2.
Оставшиеся W - 2 итераций расположим последовательно, без пересечений.
Задача D. Билеты
Всё просто. Если пришёл покупатель с десяткой, то записываем открывающую скобку, с двадцаткой - закрывающую. Будет n открывающих скобок и m закрывающих. Требуется посчитать вероятность того, что в баланс в получившейся скобочной последовательности баланс не падал меньше k.Понятно, что если k ≥ m, то ответ 1.0, а если k + n < m то ответ 0.0.
В остальных случаях можно применить принцип отражения, использующийся при аналитическом выводе формулы для чисел Каталана.
Требуется найти количество монотонных путей в решётке (0, 0) × (n, m) таких, что не содержат точек (x, y), x + k < y. В каждом не подходящем нам пути можно взять первое ребро, лежащее выше линии x + k = y, и отразить весь оставшийся за ним путь, получив таким образом монотонный путь в решётке (n + k + 1) × (m - k - 1). Соответствие является биективным.
Получим, что количество путей не подходящих путей равно Cm - k - 1m + n. Общее число путей равно Cnn + m. Значит вероятность того что баланс нарушится - P = Cm - k - 1m + n / Cnn + m = m(m - 1)(m - 2)...(m - k) / (n + k + 1) / (n + k) / ... / (n + 1).
Ответом является число 1.0 - P
Задача С. Паркет
При нечётном числе строк и столбцов ответа нет.При чётном числе строк и столбцов можно объединить пары вертикальных и горизонтальных паркетин чтобы получить недостающие квадратики 2 × 2.
При нечётном числе строк надо выложить одну строку из горизонтальных кусочков паркета, перейдя таким образом к случаю чётное × чётное.
Аналогично с нечётным числом столбцов.
Нумеровать куски можно по-разному, лично я для обозначения кусочка с левым верхним углом (i, j) использовал букву номер (i + 5j) mod 26. Это гарантирует что в квадрате длиной 5 с центром (i, j) таких же букв нет.
Comments (0)
