Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных).
Сегодня я принял виртуальное участие в Educational Codeforces Round 138 (Rated for Div. 2).
Это я могу назвать достаточно неудачным соревнованием.
Первая задача
Решалась она просто: если n = m, то выводим "NO", иначе выводим "YES". Это всё потому, что если у нас m = n, то все столбцы заняты, и любой ход приведёт к тому, что две ладьи будут стоять на одной линии. Асимптотика O(1).
1 минута, Python.
Вторая задача
Сверху я написал формулу, описывающую решение задачи.
Для тех, кто не бом-бом в этих ваших математических обозначениях:
- sum(a) + sum(b) - max(b)
Это достаточно логично (как мне кажется).
6 минута, Python
Четвёртая задача
Третья задача не поддалась мне :(
В четвёртой задаче нам нужно знать про решето Эратосфена. Это очень простая штука.
- Считать мы будем неоднозначные массивы.
- Нужна переменная, которая хранит количество возможных неоднозначных массивов длины i - 1
- Нужна переменная, которая хранит число, кратные которому удовлетворяют НОД(a[i],i) != 1, поскольку i ∊ [2,i]
- Ещё одна переменная хранит количество всех возможных массивов длины i - 1
- И последняя хранит количество всех возможных массивов длиной от 1 до n
Описанное дальше нужно проделать для всех i ∊[1, n].
Дальше если бы существовал возможный массив длины i - 1, i мог бы быть возможным, поэтому все действия в этом абзаце делаем только если (количество возможных неоднозначных массивов длины i - 1 > 0). Если i является простым числом, удовлетворяющим НОД(a[i],i) != 1, поскольку i ∊ [2,i], число должно быть кратно i. Затем идёт добавление возможных новых элементов к предыдущим, чтобы массив оставался неоднозначным. Прибавление всех возможных неоднозначных массивов размера i в res.
Затем для всех i добавление всех возможных элементов ко всем возможным массивам длины i - 1 и всех возможных массивов размера i к количеству всех возможных массивов.
После перебора всех i мы выводим разницу между количеством всех возможных массивов длиной от 1 до n и количеством неоднозначных массивов.
Вот и всё. Тут я постарался расписать решение как можно подробнее, чтобы Гена задавал меньше вопросов.
22 минута, Python.
Последние две задачи показали, что я капец как плохо работаю с графами. Эта тема слишком обширная, поэтому ждите несколько теоретических статей по этой теме.