1) Космическое поселение

Найти максимальную толщину защиты, что можно поставить n модулей

Если мы можем установить d - то можем и d - 1

По условию, нулевую толщину можем установить

f(d) - можем ли установить d 

0 1 2 3 4 5 6 ... 1563 1564              2е18
1 1 1 1 1 1 1 ...  1    0  0 0 0 0 0




2) Задача про угадывание

Угадывание числа, один человек загадывает число, второй должен его угадать, 
при этом он может спрашивать, а второй отвечать да или нет 
И как угадать быстрее всего? 

Загадано число от 1 до n, и я спрашиваю каждый раз про половинку 

1) Правда ли, что загаданное число <= n / 2 

O(logn), чтобы угадать любое число 


Пусть мы умеем угадывать любое число за x < logn 

За x запросов нам могут дать 2^x 

x < logn
2^x < 2^logn 
2^x < n

5 < 8


1сек - 10^8






15 6 6
2 2 2 3 2 2
3 3 5 2 4 3

3)Задача с ИОИП


Есть табличка, шириной в w 
Есть 2 группы слов 

1) Мы должны зафиксировать длину рулона 

2) После этого мы делим табличку на две, проводя вертикальную черту 

3) Жадно пишем слова 

4) Задача - найти минимальную длину рулона


Табличка шириной в 15, нужно найти минимальную высоту(количество строк), такую что мы можем разделить на 
две таблички верт.чертой и записать все слова 

Если хватает d, то и d + 1 хватает 
Поэтому у нас функция 

0 0 0 0 0 .... 1 1 ... 1


l = -1, r = n + m 

Зафикисировали высоту d, хотим провести верт.черту, чтобы все поместилось 

w * d - матрица, n + m слов 


Если перебирать черту бинпоиском 

w, m = w / 2 - ширина левой таблички 

m = 3, d = 4

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0


f(m) -  можно ли поместить левую группу в табличку m * d - просто симулирируем алгоритм

0 0 0 .. 0 1 1 .. 1



log(1e9) = 32, log(1e18) = 64 ~ O(1) ~ 100


O(logn * logn * n) = O(n * log^2)





4) Просто задача 

Есть два отсортированных массива, нужно найти медиану их объединения 

a = [1, 2, 3, 4]

b = [2, 2, 5]

a + b = [1, 2, 2, 2, 3, 4, 5]

Можно определить понятие медианы массива c[n] как минимальное число x, 
такое, что в a есть >= n / 2 элементов, <= x


r = 1e18, l = -1, делаем бинпоиск 

f(m) - верно ли наше условие 

Внутри для каждого массива ищем самое правое число <= x и складываем индексы + 1 

5) STL 

1) Пара pair<int, int>, make_pair(3, 4)

pair<int,int> a = {3, 4}

2) Вектор

Динамический массив 

Иногда для скорости меняем на массивы 

a.back(), a.front(), reverse, sort 

3) Стек 

Можно представлять как стопку тарелок 

Есть 2 операции - добавить в начало, удалить из начала 


stack<int> st; 

st.pop() - удалить из начала, st.push(x), st.top() - что лежит сверху, 
st.empty() - пустой ли, st.size() - размер


Можно было бы объявить массивчик a[1000000], просто int head = 0

a[i] = -1 - это пустота, иначе это элемент стека 


Понятно, как реализовать стек 

Есть скобочная последовательность из '(', ')'

ПСП -  определим баланс как количество открытых минус количество закрытых на каком-то префиксе 

( ()() ) 
bal[i] = [1, 2, 1, 2, 1, 0]

Если баланс в конце = 0 и он всегда >=0, имеем правильную с.п. 

Как проверить на правильность? 
Видим открывающую - пушим в стек, а для закрывающей st.pop(), если стек не пустой
Если стек пустой - то неправильная, и псоле конца работы стек должен быть пустой 


4) Очередь 

queue<int> q;

Добавить в конец, удалить из начала

st.pop(), st.push(), st.front() 


Нам приходят запросы вида t - просто какое-то действие в сети, и t возрастают 

И для каждого запроса мы должны отвечать, сколько было запросов в последние 50 минут 

Формально, сколько было запросов в промежутке [t - 3000, t]

Можно хранить все запросы в очереди 

Когда нам приходит запрос t, кладем его в очередь 
Идем с начала очереди, пока запросы устаревшие, q.pop()
Просто возвращаем q.size()


5) Deque - stack + queue - можем делать что хотим с началом и концом 


6) List - можем удалять откуда угодно, но не можем обращаться по индексу 


7) set, map, unordered_map, unordered_set

set - множество, в котором хранятся в возрастаюшем порядке

set<int> s;

Итераторы - это крутые указатели 
auto it = s.begin();
*it - это минимальный элемент множества 

for (auto cur : s){ - перебираются элементы множества в возр.порядке 
	
}

it++; - элемент, следующей за минимальным 

s.end()

Для любого контейнера элементы лежат в диапазоне [c.begin(), c.end())


auto it = s.end();

it--; *it - максимальный элемент 

s.lower_bound(x) - возвращает итератор на самое минимальное значение, >= x 
s.upper_bound(x) - возвращает итератор на самое минимальное значение, > x

Если такого элемента в сете нет, возврашается s.end()



if (s.lower_bound(x) != s.end()){
	
	cout << *s.lower_bound(x);
	
}
	
	
Для map все это верно, просто там хранятся пары (key, value), и ключи отсортированны 


s.find(x) - возвращает итератор на элемент = х, либо s.end()

s.erase(x) - удаляет элемент из множества, s.insert(x) - добавляем

if (s.find(x) != s.end()){
	return true;
}

Для словаря 

for (auto cur : m){
	cur.first - ключ 
	cur.second - значение 
}

for (auto cur : a){
	cout << cur << " ";
}


Все операции работают за O(logn), n - сколько элементов лежит

multiset, multimap(не нужно)

multiset<int> s;

s.erase(x)

s.erase(s.find(x))

s.count(x) - сколько раз есть x, но это работает за линию(исключение из правил)(сколько раз встречается число)


 





Есть unordered_map, unordered_set

unordered_set<long long> s;

Здесь нет порядка(он произвольный и меняется при операциях)

unordered_set<int> s;
for (auto cur : s){
	
}

Все операции в среднем работают за O(1)





6) Динамика

Была длина n - 1, делаем n 
Если мы приписываем 0, то предыдущая цифра - любая 
Если мы припишем 1, то раньше обязан был стоять 0, а конкретнее, нам подходят все последовательности 
длины n - 2, к которым приписали 0

dp[n][0] = dp[n - 1][0] + dp[n - 1][1]
dp[n][1] = dp[n - 1][0]


dp[n] = dp[n - 1] + dp[n - 2]



Откуда мы можем прийти на i-ую ступеньку
Либо с i - 1, либо с i - 2 

dp[i] = min(dp[i - 1], dp[i - 2])

НАЧАЛО
a[1] = 1
a[2] = 20
a[3] = 4
a[4] = 3

dp[1] = 1
dp[2] = 20
dp[3] = 5
dp[4] = 8