09.07.2023 06:21
wataru 44 8500 Источник

Есть вот такая, вроде бы, простая задача на литкоде: Дано три числа total - сколько у вас есть денег, cost1, cost2 - цены двух товаров. Надо подсчитать, сколько всего существует различных способов купить сколько-то этих двух товаров, не выходя из бюджета (значение имеет только общее количество покупок, а не порядок). Иными словами, сколько существет целых неотрицательных пар (x, y), таких что x*cost1+y*cost2 <= total . Например, имея товары ценами {5, 10} и 20 денег на руках, есть 9 способов потратить деньги: 0, 5, 5+5, 5+5+5, 5+5+5+5, 10, 10+5, 10+5+5, 10+10.

Задача даже помечена как medium, и вообще почти в одну строчку решается, но это если допускать безумно медленное решение за O(total / max(cost1, cost2)) , т.е линейное от входных чисел. А сможете ли вы решить ее сильно быстрее - за O(log(max(cost1, cost2))) ? В этом случае задачка становится вполне себе hard и требует много математики, изобретательности и аккуратности. Если интересно решение, добро пожаловать под кат. Буду рад любым альтернативным решениям. Может кто-то сможет додуматься до похожего решения проще.

Примечание по оформлению

Я буду активно пользоваться "аббревиатурами" в этой статье: всякое нудное объяснение я буду прятать в них. Если вы видите подчеркнутое слово "очевидно", наведите туда мышку и более глубокое объяснение должно всплыть в подсказке.

Сводим задачу к сумме определенного вида

Итак, для экономии букв давайте введем обозначения: a, b - цены товаров, c - сумма на руках. Во-первых, можно считать, что GCD(a,b)=1, иначе очевидно можно просто сократить все три числа на наибольший общий делитель (в случае с c, там будет деление нацело). Пусть x и y - переменные, сколько товаров первого и второго типа мы покупаем. Тогда у нас есть Диофантово неравенство:

ax+by \le c, x \ge 0, y \ge 0

Неравнества с двумя переменными решать вообще сложно. Давайте как-то получим одну переменную. Эталонное медленное решение предполагает, например, перебор всех возможных значений x и дальше нахождение количества возможных значений y. Но как это решение ускорять я не придумал. Давайте вместо этого перебирать потраченную сумму:

ax+by = i, x \ge 0, y \ge 0, 0 \le i \le c

Это уже Диафантово уравнение с какими-то дополнительными условиями. Но оно весьма стандартное и, поскольку мы уже сократили наибольший общий делитель, можно найти общую формулу для всех его решений:

x = x_0i+bt \\ y=y_0i-at \\ x_0a+y_0b = 1

x_0и y_0тут - это какие-то константы, которые можно найти через расширенный алгоритм эвклида. t- это свободная переменная, позволяющая прыгать между всеми целочисленными точками на прямой. Сдвиги на вектор \{b, -a\}между соседними целочисленными точками очевидны.

Теперь надо решить дополнительные ограничения на неотрицательность x и y. Они дают нам ограничения на t:

\frac{-x_0 i}{b} \leq t \leq \frac{y_0 i}{a}

Поскольку tцелое, можно расставить округления:

\lceil \frac{-x_0 i}{b}\rceil \leq t \leq \lfloor \frac{y_0 i}{a} \rfloor

Чтобы не думать об отрицательных числах, давайте договоримся, что x_0 \leq 0, y_0 \geq 0. Этого можно очевидно добиться. Тут же стоит заметить, что очевидно \frac{-x_0i}{b} \le \frac{y_0i}{a}, поэтому, округляя эти значения вверх и вниз мы в худшем случае получим нижнюю границу на 1 больше верхней границы (если вещественные границы оказались между одними и теми же целыми числами). Поэтому количество целых значений t, удовлетворяющие всем неравнествам (даже если их там таких нет), можно получить так: \lfloor \frac{y_0 i}{a} \rfloor - \lceil \frac{-x_0 i}{b}\rceil +1

А поскольку i может принимать все значения до c, формула для ответа будет:

\sum_{i=0}^c \left(\lfloor \frac{y_0 i}{a} \rfloor - \lceil \frac{-x_0 i}{b}\rceil +1\right)

Тут в перемешку округления вниз и вверх. Давайте выразим ceil через floor. Они обычно отличаются на 1, кроме случаев, когда значение под ceil целое. Поскольку x_0 и bочевидно взаимнопросты, то выражение под ceil целое, только для i делящихся на b. Поэтому давайте там везде поставим ceil=floor+1, но запомним, что ровно в \lfloor\frac{c}{b}\rfloor+1итерациях у нас вычитается лишняя единица, их надо будет после суммы назад прибавить. +1 от ceil сократиться с +1 уже под знаком суммы и мы получим:

\sum_{i=0}^c \left(\lfloor \frac{y_0 i}{a} \rfloor - \lfloor \frac{-x_0 i}{b}\rfloor \right) + \lfloor \frac{c}{b}\rfloor +1

Теперь разобьем сумму на две и введем вспомогательную функцию:

SumFloor(n, k, m) = \sum_{i=0}^{n-1} \lfloor \frac{ki}{m}\rfloor

В итоге, ответ к задаче:

SumFloor(c+1, y_0, a)-SumFloor(c+1, -x_0, b)+\lfloor\frac{c}{b}\rfloor+1

Выводим рекуррентную формулу для суммы

Теперь осталась самая малость: научиться считать сумму в SumFloor за логарифм.

Боремся с граничными условиями

Во-первых, можно считать, что k и mвзаимнопросты. Можно их на НОД сократить, вообще не поменяв ни одно слагаемое. Но вообще числа, которые в этой задаче получаются, уже взаимнопросты (см. "очевидно" выше). Но в общем случае один раз в начале подсчитать GCD за логарифм тоже можно - на оценку сложности это не повлияет.

Во-вторых, давайте считать, что k < m. В противном случае можно выделить лишнюю часть, если подставитьk=mf+k', k' = k\%m<mв сумму и подсчитать все целое отдельно в арифметической прогрессии:

\sum_{i=0}^{n-1} \lfloor \frac{(mf+k')i}{m}\rfloor= \sum_{i=0}^{n-1} \left( fi +\lfloor \frac{k'i}{m}\rfloor \right) = \sum_{i=0}^{n-1} \lfloor \frac{k'i}{m}\rfloor + \frac{fn(n-1)}{2}

Или:

SumFloor(n, k, m) = SumFloor(n, k\%m, m)+\frac{\lfloor\frac{k}{m}\rfloor n (n-1)}{2}

Вот мы и выразили сумму с kчерез сумму c k' < m.

Во-третьих, можно считать, что n \le m. В противном случае, можно разбить сумму на куски, первый несколько раз проходит по mчисел, второй проходит не больше чем m. Пусть n = mf + n', n' = n\%m < m, тогда:

SumFloor(n, k, m) = \sum_{i=0}^{mf-1} \lfloor \frac{ki}{m}\rfloor + \sum_{i=mf}^{mf+n'-1} \lfloor \frac{ki}{m}\rfloor

Давайте отдельно рассмтрим левую и правую суммы. В левой сумме воспользуемся равенством \lfloor a/b \rfloor = \frac{a - a \%b}{b}и подсчитаем отдельно не-модули как арифметическую прогрессию:

\sum_{i=0}^{mf-1} \lfloor \frac{ki}{m}\rfloor = \sum_{i=0}^{mf-1} \frac{ki-(ki)\%m}{m} = \frac{kmf(mf-1)}{2m} - \sum_{i=0}^{mf-1} \frac{(ki)\%m}{m}

В оставшейся сумме i пробегает все возможные остатки по модулю m ровно f раз. А поскольку k и m взаимно просты, то очевидно kiтоже пробегает все возможные остатки по модулю m ровноfраз, но в каком-то другом порядке. Но порядок нам не важен, можно просто fраз просуммировать все остатки от 0 до m-1. Итак, левая сумма сокращается до:

\frac{kmf(mf-1)}{2m} - f\frac{m(m-1)}{2m} = \frac{f(kmf-k-m+1)}{2}

В правой сумме заменим переменную i = mf+i':

\sum_{i=mf}^{mf+n'-1} \lfloor \frac{ki}{m}\rfloor = \sum_{i'=0}^{n'-1} \lfloor \frac{k(mf+i')}{m}\rfloor = \sum_{i'=0}^{n'-1} \lfloor \frac{ki'}{m}\rfloor+kfn'

Собирая все вместе, помня, что f = \lfloor \frac{n}{m} \rfloor:

SumFloor(n, k, m) = SumFloor(n\%m, k, m) + \frac{f(kmf-k-m+1)}{2} +kf(n\%m)

Вот мы и выразили сумму до nчерез сумму до n' < m.

Выводим формулу для общего случая

Итак, мы знаем, что GCD(m, k) = 1, k < m, n \le m.

А теперь главная хитрость тут, это применить Hermite's identity. Я много с ним эксперементировал и самый простой способ получается, если взять заnчисло k, а за xоставшееся \frac{i}{m}:

\sum_{i=0}^{n-1} \lfloor \frac{ki}{m} \rfloor = \sum_{i=0}^{n-1} \sum_{t=0}^{k-1} \lfloor \frac{i}{m} + \frac{t}{k} \rfloor

Теперь, как обычно это бывает со вложенными суммами, интегралами или пределами, надо первым делом поменять их порядок:

SumFloor(n, k, m) = \sum_{t=0}^{k-1} \sum_{i=0}^{n-1} \lfloor \frac{i}{m} + \frac{t}{k} \rfloor

Следующая догадка состоит в том, чтобы заметить, что под знаком округления вниз стоит сумма из двух чисел, меньших 1 каждое! Ведь i < n \le mи t < k. Поэтому значение floor будет или 0 или 1. 1 только в случае \frac{i}{m} + \frac{t}{k} \ge 1. Отсюда можно вывести ограничение на i, при котором что-то ненулевое вообще суммируется: i \ge m - \frac{mt}{k}. Т.к. iцелое, то можно переписать:

i \ge m - \lfloor\frac{mt}{k}\rfloor

Но сумма изначальная по iбыла от 0 до n-1поэтому, чтобы подсчитать только единицы, надо посмотреть, сколько их от m - \lfloor\frac{mt}{k}\rfloorдо n. Когда эта нижняя граница не превосходит nто количество единичных слагаемых будет n - m + \lfloor \frac{mt}{k} \rfloor. Если же эта нижняя граница больше nто единиц в сумме вообще не будет, но формула выше даст отрицательное число. Поэтому эту формулу можно использовать, только когда она дает неотрицательное число. Теперь можно вывести условие на t, при котором это условие выполняется:

m - \lfloor \frac{mt}{k} \rfloor \le n

Можно сгрупировать floor и целые числа по разные стороны. Дальше будет неравнество вида \lfloor x \rfloor \ge nЕго можно очевидно заменить на x \ge n

\frac{mt}{k} \ge m-nt \ge \frac{k(m-n)}{m}

Т.к. tцелое:

t \ge \lceil \frac{k(m-n)}{m} \rceil

Это число, для сокращения выкладок ниже, назовем N' = \lceil \frac{k(m-n)}{m} \rceil.

Итак, tпробегает значения от N'до k-1, а внутри происходит сумма скольки-то единиц. Их количество мы уже считали выше. Итоговая формула:

SumFloor(n, k, m) = \sum_{t=N'}^{k-1} \left( n - m + \lfloor \frac{mt}{k} \rfloor \right)

Полезно заметить, что N' \le k(очевидно), поэтому запись выше имеет смысл. Немного спорный вопрос, а что происходит, если N' = k, но этот случай нам проблем не составит дальше и в итоге мы получим, что сумма 0 слагаемых равна 0.

Целую часть можно вынести за знак суммы, получив (n-m)(k-N')(и даже в случае N'=k все работает). Остается почти SumFloor(*, m, k), только вот там сумма не от 0 до какого-то числа, а от N' до какого-то большого значения. Эту сумму можно выразить, как SumFloor(k, m, k) - SumFloor(N', m, k).

Промежуточный итог:

SumFloor(n, k, m) = (n-m)(k-N')+SumFloor(k, m, k) - SumFloor(N', m, k)

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

SumFloor(k, m, k) = SumFloor(0, m, k) + \frac{(k-1)(m-1)}{2} = \frac{(k-1)(m-1)}{2}

А вторая до:

SumFloor(N', m, k) = SumFloor(N', m \% k, k) + \frac{\lfloor\frac{m}{k}\rfloor N' (N'-1)}{2}

В итоге получаем (напомниаю, что N' = \lceil \frac{k(m-n)}{m} \rceil)

SumFloor(n, k, m) = \frac{(k-1)(m-1) - \lfloor\frac{m}{k}\rfloor N' (N'-1)}{2} + (m-n)(k-N') - \\ - SumFloor(N', m \% k, k)

При этом, выше мы уже показали, что N' \le k. Также, очевидно, что m\%k < k. Также, m\%kи kвзаимнопросты. Поэтому, после одного рекуррентного перехода мы всегда останемся в том же общем случае, поэтому опять проверять граничные условия не надо.

А база у рекурсии, если k=0, то результат 0. Еще можно остановится, если m=1и выдать сумму арифметической прогресси ik. Или, если n=0, то сумма ничего - ноль.

Подобно алгоритму Эвклида для GCD, эта рекуррентная формула позволяет считать сумму за O(log(max(k,m))). Его еще можно итеративно реализовать и получить O(1)по памяти.

А вот и код:

// Расширенный алгоритм Эвклида
// Возвращает GCD(a,b) и переменные x, y, т.ч. a*x+b*y=GCD(a,b)
int GcdEx(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    if (b > a) return GcdEx(b, a, y, x);
    int xx, yy;
    int d = GcdEx(b, a % b, xx, yy);
    y = xx - a/b*yy;
    x = yy;
    return d;
}

// Считает sum i=0.. n-1 floor(i*k/m)
// Ограничения:
// m > 0, 0 <= k < m, 0 <= n <= m, GCD(k, m) = 1
long long FloorSumInternal(long long n, long long k, long long m) {
	if (k == 0 || n == 0) return 0;
	if (m == 1) return k*n*(n-1)/2;
	const long long n1 = ((m-n)*k + m - 1)/m;
	long long ans = ((m-1)*(k-1) - (n1-1)*n1*(m/k))/2 + (n-m)*(k-n1);
	ans -=  FloorSumInternal(n1, m%k, k);
	return ans;
}

// Считает sum i=0.. n-1 floor(i*k/m)
// Ограничения только естественные: m > 0, k >= 0, n >= 0
long long FloorSum(long long n, long long k, long long m) {
	if (k == 0 || n == 0) return 0;

/*
    В общем случае надо сократить GCD. 
    Но в этой задаче k и m, очевидно, будут взаимнопросты.
	const long long d = Gcd(m, k);
	m /= d;
	k /= d;
*/

	if (m == 1) return k*n*(n-1)/2;

	if (k >= m) {
		return FloorSum(n, k%m, m) + (k/m)*n*(n-1)/2;
	}

	if (n >= m) {
		long long f = n/m;
		return FloorSum(n%m, k, m) + f*(k*m*f-k-m+1) / 2 + k*f*(n%m);
	}

	return FloorSumInternal(n, k, m);
}

// Решение самой задачи.
long long waysToBuyPensPencils(int total, int cost1, int cost2) {
	int x0, y0;
	int d = GcdEx(cost1, cost2, x0, y0);
	cost1 /= d;
	cost2 /= d;
	total /= d;

	if (x0 >= 0) {
		int t = x0/cost2 + 1;
		x0 -= cost2*t;
		y0 += cost1*t;
	}
	if (y0 <= 0) {
		int t = -y0 / cost1 + 1;
		x0 -= cost2*t;
		y0 += cost1*t;
	}

	return FloorSum(total+1, y0, cost1) - FloorSum(total+1, -x0, cost2) + total / cost2 + 1;
}

Комментарии (44)


  1. Imp5
    09.07.2023 07:13
    #25733418
    +1

    Линейное решение тоже может быть быстрым.


    1. wataru Автор
      09.07.2023 07:13
      #25733440
      +2

      Ну это потому что там тесты мелкие — очень мало больших чисел. Они же там рассчитывали на линейное решение. А на мелких числах, да, логарифмическое решение делает сильно больше арифметических операций.


  1. Sergey_Kovalenko
    09.07.2023 07:13
    #25734148
    +3

    Сначала подумал: да ерунда, ровные ступеньки под прямой. Через секунду понял, что не прав... Да, классная ловушка для любителей математики, на досуге подумаю сам, потом посмотрю ваше решение. Спасибо за хорошую задачку!


  1. thevlad
    09.07.2023 07:13
    #25734366
    +2

    Фактически нам надо посчитать количество целочисленных точек для (n1*c1, n2*c2), где n1,n2 E Integer, внутри прямоугольного треугольника. Как мне кажется можно чисто из геометрических соображений, попробовать решить следующим образом. Рекурсивно бить на прямоугольник лежащий внутри треугольника на целочисленных координатах (0,0) - (x1*cost1, y1*cost2), и два новых прямоугольных треугольника ((x1+1)*cost1, 0) и (0, (y1 + 1)*cost2). Для двух новых треугольников спускаемся рекурсивно вниз. Но докрутить до рабочего решения по быстрому с наскоку не получилось, хотя кажется идея рабочая.

    PS: хотя да, косяк, асимптота будет линейная 2^log2(N)


    1. wataru Автор
      09.07.2023 07:13
      #25734408

      Проблема в том, что так вы удваиваите количество треугольников. Тут, подобно QuickSort может даже O(n log n) получится, в зависимости от деталей реализации.


  1. mentin
    09.07.2023 07:13
    #25734832
    +1

    Под эталонным решением наверное имеется в виду не

    O(min(cost1, cost2))

    А O(total / max(cost1, cost2))?


    1. wataru Автор
      09.07.2023 07:13
      #25734880

      Да, вы правы, самое простое решение будет действительно за O(total / max(cost1, cost2)). Перепутал с другим решением.


      Исправил текст.


      Но вообще, есть решение и за O(min(cost1, cost2)): можно перебрать значение x%B. После чего уравнение упрощается до x'A+y <= C', откуда можно подсчитать обычную арифметическую прогрессию, перебирая все возможные y.


      Но, в общем-то, оба этих решения линейны по максимуму: Если ограничить все входные числа неким N, то обе этих оценки будут O(N) в худшем случае.


      1. mentin
        09.07.2023 07:13
        #25734942
        +1

        Пока не понял решение через min, но выбрав минимум из total/max и min, уже уменьшили сложность до корня :)


        1. wataru Автор
          09.07.2023 07:13
          #25734970
          +1

          Отличная идея! Но логарифм, все-равно круче!


          А решение за минимум вот такое:
          Считаем решения Ax+By <= C. Переберем x%B: x = x'*B+i. Подставим в неравенство и упрастим: B(Ax'+y) <= C-iA. Теперь для фиксированного y существует ровно floor((C-iA)/B)-y решений. Просуммируем по всем y — это будет просто арифметическая прогрессия за O(1). Ну, еще аккуратно с отрицательными числами еще надо границы перебора i подобрать. В итоге один цикл по i до B.


  1. mentin
    09.07.2023 07:13
    #25734980

    Не упростит ли решение переход от решения диофантова неравенства к решению равенства?

    Когда мы решаем ax + by < c - это число точек в прямоугольном треугольнике. Давайте достроим его до прямоугольника. Число точек в прямоугольнике найти легко, а с другой стороны оно = дважды число точек в треугольнике минус число точек на гипотенузе этого треугольника (они были учтены дважды). То есть достаточно найти число решений диофантова равенства ax + by = c.


    1. wataru Автор
      09.07.2023 07:13
      #25735032
      +1

      Давайте достроим его до прямоугольника.

      Тут проблема в том, что треугольник может иметь не целые вершины. Например, при 5x+7y=100. Эта прямая отсекается осями координат в каких-то рациональных точках.
      А если такой треугольник достраивать до прямоугольника, то там не будет симметрии.


      Вот если верширны целые (когда C делится на A и на B), то есть много способов. Например, через формулу Пика для площади.


      1. mentin
        09.07.2023 07:13
        #25735204

        Да, точно, симметрии нет, и идея не работает.


  1. Alexandroppolus
    09.07.2023 07:13
    #25735004

    В качестве идеи: например, b = 3, а = 2. Total = 20. Считаем черные точки. На синих линиях количество этих точек - сумма арифметической прогрессии. На красных - тоже. Синих линий всего floor(total/b) + 1, красных - floor(total/a) - floor(total/b). Остальное вроде понятно. Выглядит подозрительно просто, может я где ошибся?


    1. wataru Автор
      09.07.2023 07:13
      #25735102
      +1

      У вас картинка — очень частный случай. Вершины треугольнка в целых точках. В общем случае это не так. Например, цены 7, 13, бюджет — 20. Зеленая линия тут не будет проходить через целые точки на осях.


      А в этом случае длины красных линий будут менятся на нецелое количество "шагов". Соответственно, у вас получится там похожая на SumFloor сумма округленной арифметической прогрессии (Только еще и начало будет не с 0, а с произвольной точки. Но это тоже можно считать, сведя его к разности двух SumFloor).


      А вот этот частный случай действительно легко считается. Или можно до прямоугольника достроить, как mentin предложил, или через формулу Пика площади многоугольника на целых вершинах. Надо только через GCD найти количество точек на зеленой прямой.


      Edit: поздно заметил, что у вас на картинке только одна точка целая. Это действительно шаг впередНо этот случай тоже можно обработать. Плохой случай, когда обе вершины нецелые. И еще, под "целыми" точками, я имел ввиду черные.


      Edit2: Осознал! Ваша картинка работает, потому что 20 делиться на 1=3-2 (цены товаров). Именно поэтому все красные линии имеют целую длину в шагах. В общем случае это не так.


      1. Alexandroppolus
        09.07.2023 07:13
        #25735180

        Зеленая линия тут не будет проходить через целые точки на осях

        Под "целыми точками" вы подразумеваете черные кругляшки, которые считаем?

        Если в моем рисунке взять бюджет не 20, а 19, то зеленая линия тоже не проходит через них на обеих осях, тем не менее по прежнему имеются арифметические прогрессии. На синих это всегда (1+2+3+...), на красных в данном случае, при total==19, будет (2+4+6+8+...). Красная прогрессия зависит от, но, кажется, нулевой элемент и шаг можно вычислить.


        1. wataru Автор
          09.07.2023 07:13
          #25735218

          Да, черные кругляшки. Надо не бюджет, а надо цены менять. Например, 7, 3 и бюджет 17. Главное, чтобы бюджет не делился на cost1-cost2 (ибо вот на эту величину меняется цена при движении по красной линии).


          1. Alexandroppolus
            09.07.2023 07:13
            #25737284

            Да, красные не образуют прогрессию в общем случае.. У них та же проблема, как и для горизонтальных/вертикальных линий


  1. Firz
    09.07.2023 07:13
    #25735148

    Никогда не понимал, почему составителям алгоритмических задачек так сложно явно указывать условия задачи, хорошо хоть в примере указано как условия трактовать. К примеру, You can spend part or all of your money я трактую как явное указание на 0 < spent <= total, раз прям or all отдельно указано, а про 0 нет. А оказывается нет, all не входит в part и указан отдельно, а вот 0 это оказывается включено в part. ¯\_(ツ)_/¯


    1. iliazeus
      09.07.2023 07:13
      #25735950
      +2

      Эта неоднозначность разрешается первым же примером входных-выходных данных в условии задачи. Решение от этого, кстати, принципиально не меняется. И в целом, условие - это компромисс.


      1. Firz
        09.07.2023 07:13
        #25736376

        Вот я про это и говорю, почему неявно(я бы даже сказал неправильно, в данном случае с нулем и "part") написанные условия нужно исправлять примерами.


  1. Abs_Magica
    09.07.2023 07:13
    #25736480

    total = 20
cost1 = 5
cost2 = 10
x1 = 0
n1 = total
i1 = total // max(cost1, cost2)
while i1 > 0:
    x1 += (n1 - max(cost1, cost2)) // min(cost1, cost2)
    n1 -= max(cost1, cost2)
    i1 -= 1
print(1 + total // cost1 + total // cost2 + x1)

    Получилось как-то так.


    1. wataru Автор
      09.07.2023 07:13
      #25736498

      Ну так это то самое медленное линейное решение за O(total / max(cost1, cost2)), упомянутое в начале статьи. Сложность в задаче — это придумать более быстрый алгоритм.


  1. BaLord
    09.07.2023 07:13
    #25736912
    -1

    Автор чуть исказил условия, но с этим надо определиться четко, сколько комбинаций когда обе покупки присутствуют.

    " Надо подсчитать, сколько всего существует различных способов купить сколько-то этих двух товаров, не выходя из бюджета (значение имеет только общее количество покупок, а не порядок). "

    Т.е. обязательно должна быть пара товаров, а не 0 товаров какого то типа, следует из условий.

    Соответственно Total - A - B = получаем свободный остаток C.

    Потом С / A = C1, затем С / B = C2.

    Потом соответственно комбинаторика обычная, количество комбинаций X = С1 * С2

    И потом прибавить 2 это в одном случае когда Первая покупка = 1 и Вторая покупка = 1

    Единственное с комбинаторикой надо проверить мог ошибиться и X = (C1+1) * (С2+1)


    1. wataru Автор
      09.07.2023 07:13
      #25736930

      Ну вы бы хоть на примере из условия свое решение прогнали.


      Ваше решение вообще не работает, потому что остаток C делится между и покупками первого и второго товара. Поэтому нельзя просто брать "комбинацию" любое количество из С1 и любое из С2. Взяв сколько-то товаров первого типа (x <= C1), у вас остается остаток C-A*x, что меньше С2.


      1. BaLord
        09.07.2023 07:13
        #25737158

        если считать что 0 товаров возможно, получается целочисленное деление.

        С1 = 20 / 5 = 4 и С2 = 20 / 2 = 2, и соответственно получается X = 4 * 2 = 8


        1. BaLord
          09.07.2023 07:13
          #25737166

          и как я написал будет C1 = 5 / 5 = 1, C2 = 5 / 10 = 0, но второй множитель 0, и соответственно число комбинаций 2 * 1 + 2 = 4


          1. wataru Автор
            09.07.2023 07:13
            #25737200

            Ничего не понял, что вы тут считаете. Но 4 все еще никак не похоже на нужный в задаче ответ 9.


        1. wataru Автор
          09.07.2023 07:13
          #25737184

          Нет, тут вы считатете, что 0 товаров невозможно. Чтобы считать с 0, вам надо сделать +1 везде, ведь можно брать от 0 до 4 первого товара (5 вариантов) или от 0 до 2 второго (3 варианта). В итоге получается (4+1)*(2+1) = 15. А правильный ответ 9. Если же считать без нуля товаров (4*2), то получается, что надо обязательно брать каждый товар хотя бы по разу, а значит там всего 2 варианта (5+10 и 5+5+10), а вы насчитали 8.


          1. BaLord
            09.07.2023 07:13
            #25737240
            -1

            правильный 8мь, 9ть если только 0 1го товара и 0 2го товара, а так всего 2 получается


            1. BaLord
              09.07.2023 07:13
              #25737250

              чтобы считать комбинаторику уточните все же 0 возможен или нет. если нет то получает 2*1 = 2 варианта если 0 возможен то 2*4 = 8 мь вариантов


              1. BaLord
                09.07.2023 07:13
                #25737288

                считается элементарно C1 = 20 / 5 и С2 = 20 / 10, если 0 возможен, т.е. 4 * 2 = 8

                второй вариант остаток от вычитания C - A - B = 20 - 5 - 10 = 5

                соответственно C1 = (20 - 15) / 5 = 1 и С2 = (20 - 15) / 10 = 0, т.е. (1+1) * (0 + 1) = 2, почему прибавляем по 1 это самые первые варинты когда и и первый и второй товар в единичном экземпляре


                1. BaLord
                  09.07.2023 07:13
                  #25737294

                  9й вариант у вас получается только из-за того что вы берете что вы вообще не покупаете, т.е. оба товара 0


                  1. BaLord
                    09.07.2023 07:13
                    #25737316

                    с 9-ым вариантом у вас как в задаче про орел / решку, но можно еще 2 варианта монета упала на ребро и вообще не упала на поверхность...


                    1. BaLord
                      09.07.2023 07:13
                      #25737342
                      -2

                      по вам есть еще несколько вариантов пошел в магазин, а вместо пирожка с капустой или пирожка с картошкой, купил 4 бутылки пива

                      либо еще вариант пошел в магазин и украл 4 бутылки пива

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


              1. wataru Автор
                09.07.2023 07:13
                #25737320

                Ох, у вас все так напутанно!


                Давайте другой тест рассмотрим, а то в этом так совпало, что ваш неправильный ответ на неправильную задачу отличается от искомого ответа всего на 1, и вы, не формализуя и не доказывая ничего, просто списали эту единицу на вариант {0, 0}.


                Вот, например, цены 3 и 5, а бюджет 13. Тут есть 10 вариантов: {0, 3, 3+3, 3+3+3, 3+3+3+3, 5, 5+3, 5+3+3, 5+5, 5+5+3}. Ваша первая формула дает C=13-3-5=5, C1=5/3 = 1, C2 = 5/5 = 1. В итоге (C1+1)*(C2+1)=4. Даже близко не 10.


                Если же, как вы в конце сделали, не вычитать 3 и 5 из 13, а взять 13 сразу, то будет: C1=13/3 = 4, C2=13/5=2, (4+1)*(2+1)=15. Тоже вообще не 10. Или если +1 в скобках не прибавлять, то будет 4*2=8 — все равно не 10.


                И даже если {0,0} не рассматривать, то нужно получить 9, а оно никак из ваших формул не вылезает.


                1. BaLord
                  09.07.2023 07:13
                  #25737414

                  извините если каждый товар должен присутствовать единожды, откуда вы 0 выводите, т.е. нельзя покупать один товар, их должно быть 2, хотя бы 1 первый и хотя бы 1 второй.


                  1. wataru Автор
                    09.07.2023 07:13
                    #25737420

                    Так, тогда остется 3 варианта {5+3, 5+3+3, 5+5+3} Из ваших формул 3 никак нигде не получается.


                  1. BaLord
                    09.07.2023 07:13
                    #25737436

                    я может в формулах чуть ошибся был в туалете и мельком решал задачу, но она решается комбинаторикой.


                    1. wataru Автор
                      09.07.2023 07:13
                      #25737446

                      Нет. Вообще нет. Еще раз: перемножая какие-то два числа, вы считаете, что вы можете брать какое-то количество первого товара и какое-то количество второго товара независимо. Но у вас один кошелек, из которого вы платите за оба товара. Взяв сколько-то первого товара, вы уменьшаете оставшиеся деньги на второй товар. Вот так перемножать можно было бы, если бы у вас было 2 разных бюджета на каждый товар по отдельности.


  1. MegaMANGO
    09.07.2023 07:13
    #25739176
    +1

    Очень интересная и полезная (как минимум для меня) статья. Большое спасибо за пищу для размышлений ????


  1. HappyLynx
    09.07.2023 07:13
    #25739308
    +1

    Если существует аналитическое решение для суммы конечного ряда остатков от деления, то я, скорее всего, смогу предложить решение представленной задачи за О(1).

    Нормализуем значения относительно цены более дешевого из товаров:

    n = total / min(cost1, cost2)

    c1 = 1

    c2 = max(cost1, cost2) / min(cost1, cost2)

    Решение задачи с total = n, cost1 = c1, cost2 = c2 эквивалентно решению исходной задачи.

    Разобъем множество всех комбинаций товаров, удовлетворяющих условию задачи, следующим образом: сначала рассмотрим все комбинации, которые дают сумму, лежащую на полуинтервале (n-1;n], затем (n-2;n-1], затем (n-3;n-2] и т.д. (n-k;n-k+1] пока n-k+1 >= c1 (т.е. n-k+1 >= 1). Объединение всех этих комбинаций плюс пустая комбинация дадут нам исходное множество. Осталось их посчитать.

    Количество комбинаций, сумма товаров в которых лежит на отрезке (x-1;x], равно одной комбинации исключительно из товаров c1 плюс floor(x / c2) комбинаций, включающих товары c2. Код на Java за О(n) исключительно для проверки утверждений выше (без нормализации, т.к. ошибки округления валят тесты)

    int c1 = Math.min(cost1, cost2);
int c2 = Math.max(cost1, cost2);        
long sum = 1;
for (int i = total; i >= c1; i -= c1) {
    sum += 1 + (long) Math.floor(((double) i) / c2);
}
return sum;

    Суть в том, что теперь мы можем эту сумму с округлениями вниз, которую считает цикл, представить как разнсть сумм без округлений: sum(1 + x / c2) - sum(x mod c2). Значение первой легко вычислимо за О(1), потому что существует аналитическое решение для суммы арифметической прогрессии. А вот существует ли аналитическое решение для второй суммы остатков от деления, я не знаю, к сожалению.

    Итого, если кто-то знает аналитическое решение для суммы по k от 1 до n выражений ((k*a + b) mod c), буду благодарен подсказке.


    1. wataru Автор
      09.07.2023 07:13
      #25739340

      Нормализуем значения относительно цены более дешевого из товаров:

      Так делать нельзя. Вот были цены 3 и 7. Вы поменяли их на 1 и 2. Но оно не эквивалентно, потому что в изначальной задаче 3 вторых товара позволяли купить 7 первого. А в новой задаче — только 6.


      без нормализации, т.к. ошибки округления валят тесты

      Это не ошибки округления, а именно неправильность такой "нормализации". Можно сократить GCD(c1, c2), да. Но не min(c1, c2).


      А так сумма модулей тоже считается за логарифм, через сумму округлений вниз из статьи. Но за O(1) формулы, похоже, нет. В модулях тоже можно выбрасывать полные круги, но там все очень нерегулярно. Эта сумма состоит из кусков арифметической прогрессии, динами total/c1, округленной то вниз, то вверх. В зависимости от того, на каком остатке начинается эта прогрессия там будет на одно слагаемое больше. При чем каждое следующее начало сдвигается на total%c влево. Возможно там тоже можно вывести рекуррентную формулу уже для шага в total%c1 и модуля c1, просто аккуратно все нарисовав на бумаге — но там очень много деталей. Я не смог. Но в любом случае, эту рекурентную формулу можно вывести через функцию SumFloor из статьи, переведя сумму модулей в сумму округлений и обратно.


      1. HappyLynx
        09.07.2023 07:13
        #25739358

        Так делать нельзя. Вот были цены 3 и 7. Вы поменяли их на 1 и 2. Но оно не эквивалентно, потому что в изначальной задаче 3 вторых товара позволяли купить 7 первого. А в новой задаче — только 6.

        Еще раз перечитайте формулы нормализации, что я привел, c2 и n не заявлены мной, как целые числа. На вашем примере:

        cost1 = 3, cost2 = 7, total = 42

        c1 = 1, c2 = 7/3, n = 42/3

        Это не ошибки округления

        Это именно ошибки округления, т.к. я переписывал этот код на BigDecimal с описанной нормализацией и он продолжал работать (в отличие от double), но выглядел существенно менее наглядно.


        1. wataru Автор
          09.07.2023 07:13
          #25739368

          По формулам не понятно было. Ну да, если к нецелым числам переходить, то, конечно, делить можно. Но зачем? У вас в сумме все-равно эти числа друг на друга делятся, так что смысла в этом особо нет.