670A - Выходные
Данная задача может быть решена несколькими способами. Рассмотрим один из них. Реализуем функцию, которая по стартовому дню года определяет количество выходных в нём. Для этого просто переберем все дни в году начиная с первого и будем проверять текущий день — выходной это день или нет. Несложно понять, что если первый день недели совпадает с началом года, то в этом году будет минимальное количество выходных. Если же начало года совпадает с первым выходным в неделе (в нашем понимании это суббота), то в этом году будет максимальное количество выходных дней.
670B - Игра роботов
Для решения данной задачи будем перебирать сколько идентификаторов назовут роботы в порядке слева направо. Договоримся, что будем решать эту задачу в 1-индексации. Пусть текущий робот назовёт i идентификаторов, тогда если k - i > 0 выполним k = k - i и перейдем к следующему роботу, в противном случае, выведем a[k], где a — это массив с идентификаторами роботов, и закончим алгоритм.
670C - Поход в кино
Воспользуемся map-ом (назовём его cnt) и насчитаем, сколько учёных говорит на каждом языке (то есть cnt[i] должно быть равно количеству учёных, которые говорят на языке номер i). Заведём пару res, в которой будем хранить количество \textit{очень довольных} учёных и количество \textit{почти довольных} учёных. Изначально выполним присвоение res = make_pair(0, 0). Переберем все фильмы, начиная с первого. Пусть текущий фильм имеет номер i. Тогда, если res < make_pair(cnt[b[i]], cnt[a[i]]), выполним присвоение res = make_pair(cnt[b[i]], cnt[c[i]]) и обновим ответ номером текущего фильма.
670D1 - Волшебный порошок - 1
Данную задачу с уменьшенными ограничениями можно решить следующим образом. Будем печь по одной печеньке до тех пор пока это возможно. Для каждой новой печеньки насчитаем val — сколько нужно волшебного порошка для её приготовления. Для этого переберём все ингредиенты, и для ингредиента номер i, если a[i] ≤ b[i] выполним присвоение b[i] = b[i] - a[i], в противном случае, выполним присвоение b[i] = 0 и val = val + a[i] - b[i]. После того, как мы перебрали все ингредиенты, если val > k, то больше печенек испечь мы не сможем. В противном случае, выполним присвоение k = k - val и перейдем к приготовлению следующей печеньки.
670D2 - Волшебный порошок - 2
Будем делать бинарный поиск по ответу. Пусть мы проверяем текущий ответ cur. Тогда целевая функция должна выглядеть следующим образом. Насчитаем в переменную cnt сколько грамм волшебного порошка нам нужно для приготовления cur печенек. Переберём все ингредиенты по очереди. Пусть текущий ингредиент имеет номер i. Тогда если a[i]·cur > b[i] выполним присвоение cnt = cnt + a[i]·cur - b[i]. Если после рассмотрения какого-то ингредиента cnt стало больше чем k, целевая функция должна вернуть false. Если такого не произошло ни после какого ингредиента, целевая функция должна вернуть true.
Понятно, что если целевая функция вернула true нужно сдвинуть левую границу бинпоиска в cur, иначе нужно сдвинуть правую границу.
670E - Редактор правильных скобочных последовательностей
Будем решать данную задачу следующим образом. Сначала с помощью stack насчитаем массив pos, где pos[i] будет означать позицию скобки, парной для скобки в позиции i. Затем заведём два массива left и right. Тогда left[i] будет равно позиции ближайшей слева относительно позиции i неудалённой скобки, а right[i] будет равно позиции ближайшей справа относительно позиции i неудалённой скобки. Если таковых скобок нет, будет хранить в соответствующей позиции в массиве число \texttt{-1}.
Пусть текущая позиция курсора равна p. Тогда при операции \texttt{L} выполним присвоение p = left[p], а при операции \texttt{R} выполним присвоение p = right[p]. Осталось научиться обрабатывать операцию \texttt{D}.
Пусть lf равно p, а rg равно pos[p]. Если lf > rg сделаем swap(lf, rg). То есть теперь мы знаем границы подстроки, которую нужно удалить. Пересчитаем сначала позицию p. Если right[rg] = = - 1 (то есть после удаления текущей подстроки не останется скобок справа), нужно сдвинуть p влево, то есть выполнить присвоение p = left[lf], иначе нужно выполнить присвоение p = right[rg]. Осталось только пересчитать ссылки для концов удаляемой подстроки. Здесь нужно быть аккуратным, и проверять есть ли скобки слева и справа относительно концов удаляемой подстроки.
Для вывода ответа нужно определить номер первой слева неудалённой скобки, с помощью массива right пройти по всем неудалённым скобкам и вывести их в ответ. Для определения номера первой неудалённой скобки можно сложить все пары концов удаляемых подстрок в массив, затем отсортировать его и, проитерировавшись по полученному массиву, определить искомую позицию. Бонус: как определить позицию первой неудалённой скобки за линейное время?
670F - Восстанови число
Сначала нужно найти длину изначального числа. Для этого просто переберем её. Пусть текущая длина равна len. Тогда если len равно длине заданной строки минус количество цифр в числе len, то len это и есть длина изначального числа (то есть она определяется однозначно). Затем нужно убрать из заданной строки все цифры, которые есть в числе len, сгенерировать три строки из оставшихся цифр и выбрать из них лексикографически минимальную — это и будет ответом. Пусть t — это подстрока, которую запомнил Вася. Какие же три строки нужно сгенерировать?
Записать сначала строку t, а затем все оставшиеся цифры из заданной строки в возрастающем порядке. Эта строка может быть составлена, только если t не начинается с нуля.
Записать сначала наименьшую цифру из оставшихся в заданной строке отличную от нуля в начало. Если таковой нет, то такую строку составить мы не сможем. В противном случае, нужно записать все оставшиеся цифры, меньшие первой цифры в строке t в возрастающем порядке, затем дописать строку t и затем все оставшиеся цифры в возрастающем порядке.
Записать сначала наименьшую цифру из оставшихся в заданной строке отличную от нуля в начало. Если таковой нет, то такую строку составить мы не сможем. В противном случае, нужно записать все оставшиеся цифры, меньшие или равные первой цифре в строке t в возрастающем порядке, затем дописать строку t и затем все оставшиеся цифры в возрастающем порядке.
Также нужно отдельно рассмотреть случай, когда число, которое передавал Вася, равно нулю.
