sslotin

793 Tinkoff Challenge - Elimination Round -75
426 Codeforces Round #243 (Div. 2) -18
105 Codeforces Beta Round #81 -7
31 Codeforces Beta Round #31 (Div. 2, Codeforces format) -3
707 Codeforces Round #368 (Div. 2) -2
1 Codeforces Beta Round #1 1
2 Codeforces Beta Round #2 1
6 Codeforces Beta Round #6 (Div. 2 Only) 1
115 Codeforces Beta Round #87 (Div. 1 Only) 5
116 Codeforces Beta Round #87 (Div. 2 Only) 5

sslotin

sslotin

def ints():
    return map(int, input().split())

n, m, q = ints()

g = [[] for _ in range(n+1)]

for _ in range(m):
    u, v = ints()
    g[u] += [v]

sslotin

from os import popen
from random import randint, choice, uniform

"""
def gen():
    n = randint(2, 3)
    q = randint(1, 20)
    test = str(n) + ' 0 ' + str(q) + '\n'
    g = [[] for _ in range(n+1)]
    for _ in range(q):

sslotin

sslotin

Разбор задач 13-20

13. Неубывающий массив

Дан массив из n целых чисел. Требуется за 2n операций "прибавить к одному элементу другой" сделать его неубывающим.

Пусть все числа положительные. Тогда можно ко второму элементу прибавить первый, после этого к третьему прибавить второй и так далее. Таким проходом мы превратим массив в массив префиксных сумм. Он очевидно, будет неубывающим.

Что делать, если есть не положительные числа? Возьмём сначала самый большой по модулю элемент и прибавим его ко всем остальным. Теперь они все одного знака. Если положительного -- то делаем как раньше, если отрицательного -- проходимся с конца.

sslotin

Разбор задач 21-27

21. Математика

Посчитайте (1−a^n)/(1−a) по произвольному модулю за O(log n).

"Деление по модулю" здесь не работает -- модуль произвольный, а не простой. Поэтому (1-a)^-1, скорее всего, не существует.

Нужно заметить, что эта формула -- сумма геомерической прогрессии 1 + a + a^2 + ... + a^n. Её можно посчитать бинарным возведением в степень:

sslotin

sslotin

sslotin