🗊Презентация Олимпиадное программирование

Олимпиадное программирование ГРИГОРЬЕВА АНАСТАСИЯ

Дистанционное занятие №1 Задачи: Тройки чисел Представление чисел Кубическое уравнение Три сына Очередь в банк

Тройки чисел

Тройки чисел. Примеры.

Решение Возвести в квадрат Но не просто так, а перенеся корень из b в правую часть a = b + 2sqrt(bp) + p Поскольку a,b и p – целые числа, то и sqrt(bp) – целое число, т.е. b равно произведению p и квадрата некоторого целого числа b = pn^2, a = p(n-1)^2 Т.о. для каждого p из отрезка [N,M] требуется найти все такие n, что N<= p(n-1)^2 < pn^2 <= M

Оптимизируем Разделим на p все части и извлечем корень Sqrt(N/p) <= n-1 < n <= Sqrt(M/p) Т.о., количество решений на 1 меньше, чем количество целых чисел на отрезке [Sqrt(N/p);Sqrt(M/p)] Проверяем на простоту каждое число от N до M и находим кол-во решений для каждого из найденных простых чисел указанным выше способом

Представление чисел

Решение

Решение

Оптимизация

Кубическое уравнение

Решение

Три сына

Решение

Оптимизации

Код на питоне n = int (input()) b = n//3 a = b-1 if n%3 ==2 b + = 1 c = n-a - b print (a, b, c)

Очередь в банк

Тесты

Упрощенное условие

Решение на 40 баллов

Решение на 100 баллов

Решение на 100 баллов

Код на питоне input = open('longqueue.in', 'r') output = open('longqueue.out', 'w') n,x=input.readline().split() x=x.rstrip() a=input.readline().split() n=int(n) a[n-1]=a[n-1].rstrip() x=int(x) b=[0] for i in range(1,n):     if int(a[i-1])>=x:         b.append(b[i-1]+1)     else:         b.append(b[i-1]) k=int(input.readline().rstrip()) smesh=0 for i in range(k):     rab=input.readline()     rab=rab.rstrip()     if rab[0]=='2':         smesh+=1     elif rab[0]=='1':         e=int(rab[2:])         if int(a[-1])>=x:             b.append(b[-1]+1)         else:             b.append(b[-1])         a.append(e)     else:         otv=b[int(rab[2:])+smesh]-b[smesh]         output.write(str(otv)+'\n')

Код на С++