MITM: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) (Новая страница: «==Ограничения== Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, напри...») |
Глеб (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
==Ограничения== | ==Ограничения== | ||
| − | Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^14$, решим задачу количество чисел < $k$ с суммой цифр - $s$ | + | Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^{14}$, решим задачу количество чисел < $k$ с суммой цифр - $s$ |
==Альтернативное решение без ДП по цифрам== | ==Альтернативное решение без ДП по цифрам== | ||
Версия 17:30, 25 марта 2020
Ограничения
Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^{14}$, решим задачу количество чисел < $k$ с суммой цифр - $s$
Альтернативное решение без ДП по цифрам
Давайте разделим число на левую часть(большие 7 разрядов) и правую(меньшие 7 разрядов). Давайте для всех чисел правой части предподсчитаем, сколько из них имеют сумму $x$ и запишем это в массив подсчет, затем будем перебирать левую часть, пусть и числа из левой части сумма - $x$, тогда нам нужно найти количество правых частей с суммой $S - x$(это просто обращение к массиву подсчета), тогда мы научились решать задачу за $\sqrt(k)$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin