Wataru

Логика вашего решения вообще непонятна. Какие-то жадные сдвиги одной из двух переменных на 1, да еще и ответ ровно один раз вернется, когда как в задаче надо найти все решения уравнения.

Там по вашей ссылке в задаче есть подсказка: уравнение можно переписать в виде (x-2y)(x+2y)=n

Отсюда получается решение: Перебирайте все делители n, не превосходащие корень. Пусть делитель d, тогда второй множитель будет n/d.

Осталось решить систему линейных уравнений:

x-2y=d
x+2y=n/d

Решается в уме - x=(d+n/d)/2, y=(n/d-d)/4

Отслось только учесть диофантовость уравнения - ответ должен быть неотрицательные целые числа. Значит, надо чтобы оба делителя d, n/d давали одинаковый остаток от деления на 4 и 2. Ну и d<=n/d, но это учтется перебором делителя до корня.

Вот и все решение - циклом переберите делитель до корня, убедитесь, что он и оставшийся множитель дают один и тот же остаток по модулю 4, вычислите x и y и выведите их.

Кубическая функция с первым коэффициентом 1, как у вас, уходит в минус бесконечность слева и плюс бесконечность справа. Она может не иметь экстремумов или иметь два - максимум левее минимума.

Если экстремумов нет - будет возрастающая функция, с одним вещественным корнем всегда. Если экстремумы есть, то надо или чтобы они оба были меньше 0, или оба были больше.

Вот, возьмите производную, найдите когда у нее есть корни и где они. Подставьте их в исходную функцию и найдите экстремумы - будут выражения от a. Дальше составьте условия: или корней нет, или они есть и максимум меньше 0, или они есть и минимум больше 0. Решите неравенства и найдите интервалы для a.

У вас ошибка: надо еще P30(0) прибавлять.

Какой-то более простой формулы мне придумать не удалось, и она вряд ли есть. Если руками вывести формулы для маленького количества банков, то там все-равно получается полином n/2-ой степени, т.е. от 15 слагаемых никуда не уйти.

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

Если нужно числа - можно написать программу, или считать на калькуляторе. Начинайте с 0.7^30. Делайте m+, домножайте на 3/7*30/1, потом на 3/7*29/2, и так далее (нажимая m+ каждый раз), пока 15 слагаемых всего не наберется.

Или вбить в wolframalpha и получть 98.3%.

Можно попробовать вычислить корень быстрым алгоритмом. Но там сложно. Гуглите Karatsuba square root. Есть открытые реализации. Есть еще какой-то адский метод через быстрое преобразование Фурье, попробуйте погуглить и его.

Более простой в реализации, но менее быстрый метод вычисления корня - бинарный поиск. Храните l, r, l^2, r^2 и lr. По этим числам можно вычислить m=(l+r)/2, m^2, m*l, m*r без длинных умножений, а только складывая длинные числа и деля на 2. Вам надо поддерживать, чтобы l^2 <= n <= r^2. Изначально можно сделать l=1, r=10^51 (или больше - половина длины входного числа + немного, чтобы точно квадрат был больше n), потом делить отрезок пополам и отбрасывать ненужную половину.

Еще есть вероятностный метод через символ Лежандра/Якоби. Это будет самым быстрым методом.

Это как смотреть на последнюю цифру. Квадраты могут давать там 0, 1, 4, 9, 6, 5. Но нет ни одного квадрата, который оканчивался бы на 2. Т.е. если число заканчивается на 2, то можно сразу говорить, что это не квадрат. Это мы взяли остаток от деления на 10 (последняя цифра) и посмотрели, какие из них хорошие. Вот символ Лежандра - это такая проверка для модуля по любому простому числу (а не 10).

Если брать некоторое простое число p, то n может быть квадратом, только если символ Лежандра (n/p) - равен 1 или 0 (По научному: n - должно быть квадратичным вычетом).

Если брать небольшие (<64-битные) простые числа, то можно за линию считать n%p и потом вычислять символ Лежандра (n%p/p) по алгоритму через символ Якоби за O(log(p)^2). Когда подсчитали символ Лежандра и если он -1, то n - точно не корень.

Тут проблема в том, что это необходимый, но недостаточный критерий - если для какого-то p вы получили -1 - то это точно не квадрат. Но возможно можно подобрать такое число, что все ваши тесты дадут 1, а оно не квадрат. Поэтому надо брать много простых чисел. Скажем, 20. Желательно еще числа брать достаточно большими. Но их не надо искать каждый раз, можно захардкодить. Грубая прикидка говорит, что вероятность ошибки такого алгоритма 2^(-количество простых чисел).

Т.е. берете много простых чисел. Считаете для каждого n%p выполняя деление большого числа на короткое (один проход по массиву цифр). Потом считаете символ Лежандра. Если получили где-то -1 - то точно не квадрат. Иначе - скорее всего квадрат.

Можно совместить вероятностный тест и вычисление корня. Сначала проверьте парочку простых чисел на символ Лежандра для отсечения точно не квадратов. Еще проверку последней цифры можно сделать, это очень дешево. Если не отсеклись, то считайте корень. Так будет всегда работать правильно но будет быстрее работать в некоторых случаях.

Во-первых, в С++ нет and, надо использовать &&.

Во-вторых, ошибка в алгоритме. Задача - проверить, что шаги оптимальные. Для этого вам надо знать оптимальный шаг и сравнивать его с текущим. Можете сформулировать оптимальную стратегию?

Возьмите, например, k=4,5,6 и порисуйте на бумажке, попробуйте подсчитать, какие позиции выигрышные (из них можно сделать ход в проигрышную позицию), а какие - проигрышные (любой ход ведет в выигрышную позицию). Считайте увеличивая количество предметов. Позиция с 0 предментами - проигрышная - предыдущий игрок придя в нее выиграл. Позиция 1 - выигрышная, потому что можно пойти в проигрышную 0. Найдите закономерность, попытайтесь ее логически обосновать.

Пример для k=3:

0 - проигрышная

1 - выигрышная ( можно взять 1)

2 - выигрышная (можно взять 2)

3 - выигрышная (можно взять 3)

4 - проигрышная

5 - выигрышная (можно попасть в 4, взяв 1)

6 - выигрышная (можно попасть в 4, взяв 2)

7 - выигрышная (можно взять 3 и попасть в проигрышную 4)

8 - проигрышная (любой ход ведеть в выигрышные 5-7)

...

Контрпример - это тот, который опровергает утверждение.
Утверждение - каждый связный граф имеет хотя бы одну вершину степени 2.
Т.е. контрпример - связный граф, который не имеет ни одной вершины степени 2.
Степень вершины - это сколько ребер в нее входит. Можете найти такой граф на картинке?

Если в условии "трех различных цифр" означает, что все цифры разные, то ответ - количество сочетаний из 10 по 3, умноженное на 3 факториал: C(10,3)*3! = 10*9*8 = 720.

Логично: есть 10 вариантов выбрать первую цифру, 9 - вторую (исключив вариант повторения), и 8 - третью (минус 2 варианта повторения первой и второй цифры).

Проверьте для мелких чисел сначала.
2,5 - 2
4,25 - 3
8,125- 4
16,625 - 5.

Вроде как напрашивается паттерн, что ответ в вашей задаче 2021.

Почему так? Его можно доказать. Как Rsa97 уже написал, количество цифр - log_10, округленный вниз+1. Пусть k=2020, тогда ваш ответ:

2+floor(log(2^k))+floor(log(5^k)).

Если бы floor не было, учитывая log(a)+log(b) = log(ab), то мы бы получили 2+log(10^k), что было бы 2+k. Но у нас есть floor, каждый из которых уменьшает занчение на число от 0 до 1, больше 0, но меньше 1 (ведь ни 2 ни 5 ни в какой спени не дадут степень 10 - log дает нецелое число). Итого - ответ меньше чем k+2 на некое число, от 0 до 2 (невключительно) и целое. Такое число только одно - k+1.

Проблема у вас, похоже, что разные комбинации можно получить с разными вероятностями.

Допустим, 19 = 2+2+5+5+5. Но можно же переставлять карты местами. Ведь диллеру могли прийти 5, потом вторая 5, потом 2, потом 2, потом 5. Да и сами пятерки могли прийти 3! способами. Однако, вы не можете поставить 2 последней, потому что сумма четырех первых карт уже 17. Диллер бы не тянул эту последнюю двойку.

Но 19=3+3+4+4+5 уже можно выбрать всеми 5! разными способами. Поэтому эти 2 комбинации, хоть и дают одну и ту же сумму и содержат одинаковое количество карт, можно получить с разной вероятностью.

Правильное решение с применением динамического программирования:

Во-первых, переберите, какая карта будет вытянута последней. Найдите вероятности всех сумм с учетом этой карты (так, что она переваливает сумму за 17, но не пердыдущая). Потом просуммируйте по всем таким картам.

Исключите эту последнюю карту из колоды. Теперь надо найти сколько наборов карт заданной длины дают каждую сумму < 17. При этом при подсчете вероятности можно переставлять все эти карты как угодно. Поэтому имеет значение, сколько карт мы использовали для суммы.

Теперь считайте динамическое программирование - сколькими способами вы можете выбрать n карт из первых k, получив сумму s (порядок не важен).

При подсчете у вас есть 2 варианта - последняя из k карт или входит, или нет в сумму (допустим массив a[] хранит веса карт).
Т.е. F(n,k,s) = F(n,k-1,s)+F(n-1,k-1,s-a[k]).

База:
F(0, k, s) = 1 если s==0; 0 иначе
F(n,0,s) = 1 если n==0 и s==0; 0 иначе.
F(n, k, s<0) = 0

Можно сэкономить на памяти и считать в двумерном массиве с конца в начало, выкинув k (второй параметр).

Потом искомая вероятность набрать сумму x c последней картой l, если осталось в колоде max_k карт (если x<17+l, x>=17, иначе - вероятность 0):

P(x) = sum_{n=1..max_k} f(n, max_k, x-l) * n! * (max_k-n)! / (max_k+1)!

Тут перебор по всем возможным количествам карт у диллера. Дальше берем количество способов набрать нужную сумму из ДП. Потом домножаем на n!, потому что эти карты в руке у диллера могли прийти в любом порядке. Дальше домножаем на вероятность вытянуть конкретные n+1 карт (считая последнюю) из колоды с max_k+1 картами. Это 1/(max_k+1)/max_k/,,,/(max_k-n+1) = (max_k-n)!/(max_k+1)!

Этот множитель после f() можно пересчитывать за одно домножение и деление
при увеличении n.

Напоминаю, это надо просуммировать по всем возможным картам взятым за l, заново прогоняя ДП.

В моей нотации С(n,k) - сочетания из n по k.

Нужно знать вот это тождество для сочетаний:
С(n,k) = C(n,n-k).

Применив к тому, что у нас под знаком суммы:
C(2n+1, 2k) = С(2n+1, 2n+1-2k)

Когда k проходит от 0 до n, слева получаются сочентания по всем четным числам от 0 до 2n+1, а справа - по всем нечетным.

Есть формула, что сумма всех сочетаний из n по всем возможным k будет 2^n, Получается тупо из раскрытия (1+1)^n по биному Ньютона.

Но у нас тут не сумма по всем, а только по четным. Но выше мы уже видели, что суммы по всем четным и всем нечетным совпадают. Отсюда напрашивается варинат просто подсчитать удвоенную искомую сумму.

Формально: пусть X - искомая сумма в задаче.
тогда
X+X = sum_{k=0..n} C(2n+1, 2k) + sum_{k=0..n}(2n+1, 2n+1-2k) =
= sum_{k=0..n} C(2n+1, 2k) + sum_{k=0..n}(2n+1, 2*(n-k)+1) =
= sum_{k=0..n} C(2n+1, 2k) + sum_{k=n..0}(2n+1, 2*(n-k)+1) =

Во второй сумме заменим n-k=j. Т.к. k=n..0, то j = 0..n.

= sum_{k=0..n} C(2n+1, 2k) + sum_{j=0..n}(2n+1, 2*j+1).

А это тупо сумма по всем возможным k от 0 до 2n+1 (только четные и нечетные в отдельных суммах):
= sum_{k=0..2n+1} C(2n+1, k) = 2^(2n+1)

Остюда X = 2^(2n+1) / 2 = 2^(2n)

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

Варианты метрик:

- Для каждого кластера считается наибольшее расстояние между двумя элементами, и это суммируется по всем кластерам. Можно суммировать квадраты этих расстояний, тогда будут наказываться кластеризации с очень большими кластерами.
- отношение максимального расстояния между соседними точками в любом кластере и минимального расстояния между кластерами.
- Это может быть и качественная метрика. Любая кластеризация, где расстояние между соседними точками в кластере меньше расстояния между кластерами считается хорошей. Это частный случай предыдущей метрики, но вам достаточно искать не минимум, а любое значение <1.

Некоторые метрики имеют смысл только при фиксированном количестве кластеров, как первая.

Разные метрики дают разные кластеризации и все они в каком-то смысле хорошие. Что именно подходит вам в вашей задаче - можете судить только вы эмпирически.

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

Многие метрики, если они аддитивны как первая, можно считать динамическим программированием: f(i,k) - значение метрики если мы разбили первые i точек на k кластеров.

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

Еще можно применять стандартные методы без оптимизаций опирающихся на то, что у нас одномерное пространство - тупо применяйте метод k ближайших соседей, например.

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

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

Аккуратно с крайними случаями - три центра окружностей не должны лежать на одной и той же прямой, иначе вы не сможете понять, какая из двух точек вам нужна.

Во-первых, для таких больших коэффициентов вы в long long не влезаете, если в лоб считать.

Можно проверить в 2 этапа. Подсчитать A=a*x+b, B=c*x+d. Потом проверить что A*x*x = -B. Но тут нужно заранее отсечь случаи, когда abs(A) > abs(B)/(x*x). Тогда переполнений не будет.

Во-вторых, как же сложно у вас разбор случаев идет. Я не могу разобраться, что там происходит. Там наверняка опечатка, но я даже читать не хочу. Перепишите, пожалуйста. Вам надо найти самый старший ненулевой коэффициент и перебирать его делители. Плюс добавить корень 0, если этот коэффициент не d. Это делается сильно проще так:

if (d != 0) {
  n = d;
} else {
  s.push_back(0);
  if (c != 0) {
    n = c;
  } else if (b != 0) {
   n = b;
  } else {
   n = a;
  }
}
if (n == 0) {cout << "-1"; return}

Самое простое решение для понимания - полный перебор. Тупо 3 цикла - сколько монет с номиналом 2 взяли, сколько монет с номиналом 3 и сколько монет с номиналом 5. Каждый цикл от 0 до <Сколько осталось набрать> / номинал. Потом проверяем, что сумма сошлась. Более того, можно последний цикл пропустить и просто проверить, что оставшееся можно набрать пятаками.

bool CanExchange(int n, int have2, int have3, int have5) {
  for(int take2 = 0; take2 <= min(have2, n/2); ++take2) {
    int left2 = n - 2*take2;
    for (int take3 = 0; take3 < min(have3, left2/3); ++take3) {
      int left23 = left2 - take3*3;
      if (left23 % 5 == 0 && left23 / 5 <= have5) {
        return true;
      }
    }
  }
  return false;
}

Но это для данной конкретной задачи, где всего 3 типа монет. В общем случае нужно писать рекурсивную функцию вместо вложенных циклов, которая будет принимать сколько осталось собрать и какой тип монет перебирать.

Самое быстрое решение - динамическое программирование.

F(n,k) - можно ли набрать число n первыми k типами монет.

F(0.0) = 1
F(*, 0) = 0
F(n,k) = Sum(i = 0..have[k]) F(n-i*value[k], k-1)

Фактически, это тот же рекурсивный перебор, только с мемоизацией. Можно переписать это двумя циклами и соптимизировать по памяти до O(n).

Возьмите для каждого товара набор точек {день, показатель} за сколько-то последних дней. Постройте линейную регрессию. Наклон прямой (т.е. коэффициент перед номером дня) и будет этим показателем динамики.