Олимпиадное программирование

Дистанционное занятие №1
Задачи:
Тройки чисел
Представление чисел
Кубическое уравнение
Три сына
Очередь в банк
2018, ЯНВАРЬ

Тройки чисел
2018, ЯНВАРЬ

Тройки чисел. Примеры.
2018, ЯНВАРЬ

Решение
Возвести в квадрат
Но не просто так, а перенеся корень из 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
2018, ЯНВАРЬ

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

Представление чисел
МАТ-МЕХ 2015

Решение
МАТ-МЕХ 2015

Решение
МАТ-МЕХ 2015

Оптимизация
МАТ-МЕХ 2015
Совет: при такой реализации sqrt(N) вычисляется при каждой
Итерации цикла while. Этого можно избежать, если заранее
вычислить эту величину и использовать в условии цикла её значение.

Кубическое уравнение
МАТ-МЕХ 2015

Решение
МАТ-МЕХ 2015

Три сына
2018, ЯНВАРЬ

2018, ЯНВАРЬ

Решение
2018, ЯНВАРЬ

2018, ЯНВАРЬ

Оптимизации
2018, ЯНВАРЬ

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

Очередь в банк
2018, ЯНВАРЬ

2018, ЯНВАРЬ

Тесты
2018, ЯНВАРЬ

Упрощенное условие
2018, ЯНВАРЬ

Решение на 40 баллов
2018, ЯНВАРЬ

Решение на 100 баллов
2018, ЯНВАРЬ

Решение на 100 баллов
2018, ЯНВАРЬ

Код на питоне
2018, ЯНВАРЬ
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')
f = open ("longqueue.in", "r")
n, x = [int(x) for x in f.readline().split()]
bb = [int(x) for x in f.readline().split()]
d = 0
a = [0]
for b in bb:
if b >= x:
d += 1
a.append ( d)
m_count = int (f.readline())
result = []
h = 0 # head person position
for i in range (m_count):
m = f.readline().split()
if m[0] == '1':
if int (m[1]) >= x:
a.append(a[-1] + 1)
else:
a.append(a[-1])
elif m[0] == '2':
h = h + 1
elif m[0] == '3':
r = a[int (m[1]) + h] - a[h]
result.append(r)
print (r)
f.close
with open("longqueue.out", "w") as f:
for r in result:
f.write(str(r)+'\n')