Wataru

Во-первых, для таких больших коэффициентов вы в 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).

Проблема в выводе. Вы нулевые цифры вообще не выводите:

for(size_t i=0; i<SIZE; i++) {
  if (n[i]!=0) {
    cout << n[i];
  }
}

А нужно пропускать только ведущие нули. Самый простой способ исправить - завести bool printed:

bool printed = false;
for(size_t i=0; i<SIZE; i++) {
  if (printed || n[i]!=0) {
    cout << n[i];
    printed = true;
  }
}

Ну, еще может быть стоит увеличить размер длинных чисел. Не факт, что 135 цифр хватит. Введите тест n=300, k=300, и проверьте что выводится один и тот же ответ при текущем и увеличенном SIZE.

M%p = 0, значит M=k*p для какого-то целого k.

k*p >= N, значит k >= N/p.

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

k >= ceil(N/p).

слева и справа целые числа, надо найти минимальное k, значит k = ceil(N/p).

Отсюда весь ответ M = p*ceil(N/p)

ceil(N/p) можно подсчитать в целых числах в C, как (N+p-1)/p

Еще, если подумать, что вам нужно блищайшее делящееся на p число, то нужно дополнить N%p до p, то можно сделать так: N+(N%p ? p-N%p : 0)

Попробуйте проверять, что средний символ "-".
Еще надо проверять, что длина строки ровно 5 символов.

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

Надо вместо сортировки тупо просуммировать все числа и поделить на их количество (округлите вниз).

Ну и, не забудьте в конце цикл гнать по всем элементам а не от середины.

Представьте, что ваши вершины лежат на прямой OX в координатах (a_i, 0). Длины ребер тут будут тупо длинами отрезков. Теперь ваша задача обойти все точки на прямой и вернутся в начало, пройдя наименьшее расстояние.

Очевидно, что оптимальное решение тут, например, такое: начните в самой левой точке и идите по ним слева-направо. Дойдя до конца, вернитесь в самую левую точку. Это и будет оптимальное решение. Длина пути тут 2*(max(ai)-min(ai)).

Если нужна только длина пути - то можно тупо найти минимум и максимум и взять удвоенную разность. Если нужен сам путь, то сортируйте или пары {a_i, i} или сортируйте только индексы, используя собственную функцию сравнения, которая по двум целым числам сравнивает a[i1] и a[i2].

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

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

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

Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.

Проблема не в коде, а в алгоритме. Долго строить всю строку и считать в ней нули.

Есть вот такая формула. Для каждого простого числа можно опредерить степень просто деля n (не факториал!) на это простое число нацело, пока не получится 0 и суммировать все результаты.

Но это работет только для простых чисел. Т.е. чтобы узнать, в какой степени число 10 входит в N! (или сколько нулей на конце в деситичной записи) надо узнать, сколько раз 2 и 5 входят в N! и взять минимум.

Т.е. надо разложить k на простые множители, для каждого простого множителя подсчитать, сколько раз он входит в n! по формле выше. Потом поделить это на степень простого числа в k, и по всем делителям k взять минимум.

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

В случае с трассировкой лучей, за логарифм нет реализации вообще - ибо у невыпуклого многоугольника может быть O(n) пересечений с лучем (представьте себе пилу).

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

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

При запросе, сначала бинпоиском найдите, в какой колонне лежит точка. Потом еще одним бинпоиском найдите, между какими из двух прямых лежит точка. Тут сравнения будут уже непросто чисел, а надо будет подставлять точку в уравнения прямых и смотреть, лежит ли точка выше или ниже. Если точка лежит так, что выше ее (и ниже) нечетное количество прямых - то точка внутри.

Проблема этого метода, что он требует O(n^2) памяти в худшем случае и такую же предобработку.
Но, для выпуклых многоугольников, прямых в каждой колонне будет всего две. Вот описание метода с реализацией для этого упрощенного случая.

Алгоритм Ахо-Корасика.

Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.

Это комбинаторика.

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

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

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

Поэтому пусть f(a0,a1,...a9) - сколько есть способов расставить некторые из a0 нулей, a1 единиц, a2 двоек, и т.д. (ноль может идти в начале, число может быть пустым).

Ответ к задаче f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). Последнее слагаемое считает варианты, начинающиеся с нуля. Оно не вычитается, если нулей в числе нет. -1 посередине вычитает пустое число из ответа (но ее нет в последнем слагаемом, ведь мы там еще 0 в начале приписываем и пустое число надо считать).

Теперь самое интересное, формула для f(a0,a1,...a9). Замкнутой формулы я не нашел, но придумал, как считать алгоритмом.

Можно все варинаты разделить по количеству символов в числе (n), от 0 до суммы a0...a9. Давайте подумаем, где могуть быть девятки? i <= a9 из них попадут в ответ. Они могут быть на C(n, i) позициях. Останется разместить остальные цифры на n-i позиций.

Вырисовывается следующее динамическое программирование:

F(i, n) - сколько способов разместить первые i цифр на n позициях (возможно, беря не все цифры).

F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, n-j)*C(n, j)
F(0, n>0) = 0
F(i,0) = 1.
Ответ - sum(k=0..a0+...+a9) F(9, k)

У функции как бы неявный параметр массив a[] количеств всех цифр, но я его не включаю в параметры динамики, потому что по нему не надо мемоизировать.

Не забудьте, что для подсчета второй динамики, для f(a0-1,...a9) надо будет полностью отчистить мемеоизацию, потому что массив a поменялся же.

Этот алгоритм работает за O(9*n), где n - длина входного числа.

Вот пример для входного числа 112: все цифры, которых в числе нет можно выкинуть из рассмотрения и работать с массивом a={2,1} (для всех десяти цифр слишком много писать).

F(0,0) = 1
F(0,1) = 0
F(0,2) = 0
F(0,3) = 0
F(1, 0) = 1
F(1,1) = F(0, 1)*C(1,0) + F(0,0)*C(1,1) = 1
F(1,2) = F(0,2)*C(2, 0)+ F(0,1)*C(2,1) + F(0,0)*C(2,2) = 1
F(1,3) = F(0,3)*C(3, 0)+ F(0,2)*C(3,1) + F(0,1)*C(3,2) = 0
F(2,0) = 1
F(2,1) = F(1,1)*C(1, 0) + F(1,0)*C(1,1) = 2
F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
F(2,3) = F(1,3)*C(3, 0) + F(1,2)*C(3,1) = 3

Ответ F(2,3)+F(2,2)+F(2,1)+F(2,0) = 3+3+2+1= 9.

Вычитаем 1 (пустое число) и получаем 8 чисел, как у вас в примере для 112.

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

Во-первых, когда встает вопрос о можно-нельзя ли какими-то операциями получить что-то, первая мысль должна быть - придумать инвариант. Какое-то свойство, которое не меняется при применении операции. С опытом наберетесь идей для инвариантов. Тут сразу приходит в голову такой: Обозначим цвета цифрами от 0 до 2. Тогда при любом перекрашивании сумма всех чисел по модулю 3 не меняется. Если столбы одинаковые - сами числа не меняются, если 01 перекрасить в 22, 02 в 11 и 12 в 00, то сумма остается с таким же остатком от деления на 3.

Отсюда можно сразу сделать вывод, что при N делящемся на 3 ответа нет. Потому что в конце мы должны получить все цвета одинаковые, а значит сумма будет 0, N или 2N - делится на N. Раз N делится на 3, то и итоговая сумма дает остаток 0 (по модулю 3). Но изначальная раскраска может иметь любой остаток (например, 00..0001). Значит решения для таких N нет.

Далее, можно легко придумать, как "удваивать" решение. Пусть мы умеем получать какой-то N, то можно получить алгоритм для 2N. Сначала перекрашиваем первую половину по известному плану. Потом вторую половину. Потом попарно столбы из двух половин. Надеюсь, очевидно, почему это работает?

Так можно получить ответ для 2,4,8,16, но этого мало.

Следующая мысль, как можно построить универсальный план покраски - это воспользоваться тем, что если мы сделаем все столбы одинаковыми, то все последующие действия ничего не испортят. Т.е. можно взять конкретную раскраску столбов, составить план для нее. Потом взять следующий вариант входных данных, прогнать его через уже составленный план. Если результат не одноцветный - дополнить план так чтобы раскрасить все в один цвет и для этого варианта изначальной раскраски. Повторить со всеми возможными входными данными. Использовать эту идею для всех вариантов N раскрасок слишком медленно (их же 3^N). Вернемся к ней попозже.

Следующая идея должна быть - раз для существования решения важно неделимость на 3, то возможно мы сможем к группе одинаковых столбов добавить 3 столба?

После разбора нескольких случаев на бумаге я понял, что надо отдельно рассматривать случаи N%3=1 и N%3=2.

Рассмотрим первый случай. У нас есть 3k столбов цвета А, и в конце еще 4 столба - AXYC (один из N и 3 новых). Задача - получить в конце 4 одинаковых цвета. У нас уже есть решение для N=4 в примере. Просто примените его к 4-м последним столбцам. Теперь у нас есть ...AAAZZZZ. Если A=Z, то все наши операции ничего не сделают. Рассмотрим только случай A!=Z. Красим A+Z, получаем AAYYZ..Z на конце Красим 2 раза A+Y. Т.е. за 3 операции мы перекрасили 3 последние A в Z. Повторяем операцию, пока все A не перекрасим (их же 3k, напоминаю).

Теперь случай N=3k+2. У нас есть 3k A, и в конце AAXYC. Если у вас есть решение для 5, то получаете на конце 5 Z и аналогично предыдущему случаю перекрашиваете 3 последних A в цвет последних столбов.

Т.е. отдельно рассматриваете случай разных остатков N%3. Потом решаете задачу для N=4 или 5 первых столбцов, потом добавляете по 3 столба: решаете задачу для 4/5 последних столбов и итеративно перекрашиваете по 3 столба из предыдущих.

Это решение потребует максимум N/3*(F(5)+N) шагов, где F(5) - сколько нужно операций для решения N=5.

Теперь решение для N=5. Тут и надо будет воспользоваться наблюдением о дополнении плана для разных входных данных. Вот есть 5 столбов. Покрасим 1+2 и 3+4. Теперь у нас есть AABBC. Возможно какие-то цвета одинаковые. Но сначала допустим, что они все три разные. Красим попарно A+B(1+3 и 2+4). Все. Но что, если B=C, B!=A? У нас было AABBB. Мы покрасили 1+3 и 2+4 - получили ССССA. Красим 4+5 - CCCBB. Теперь, как раньше, перекрасим 3С в B: 3+4 (CCAAB), 1+3(BCBAB), 2+4 (BBBBB).
Теперь надо рассмотреть случай B=A, C!=A: AAAAC. Надо аккуратно повторить все операции выше - получим BBBBB. План для этого случая работает, ничего дописывать не надо. Остался случай A=C, C!=B. Т.е. дано AABBA. Применяем шаги выше и получим (перепроверьте!) AAAAA.

Т.е весь план для N=5 1+2, 3+4, 1+3, 2+4, 4+5, 3+4, 1+3, 2+4.

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

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

Возьмите максимальную степень двойки, помещающуюся в N. Пусть это k (2k > N, k <= N). Примените план для первых k. потом для последних k. Итого вы получите N-k столбов одного цвета и k столбов (возможно) другого цвета в конце. Если N-k делиться на 3 то, по известному плану "перекрашивания по тройкам" перекрасьте первые N-k в цвет последних k. Если же N-k не делиться на 3, то покрасьте попарно столбы цвета первых N-k и цвета вторых N-k. Потом останутся какие-то столбы в конце другого цвета, но их количество точно будет делиться на 3 (доказательство этого факта придумайте сами. Рассмотрите какие могут быть остатки от деления на 3 у k и N-k). Раз у нас группа другого цвета состоящая из троек, то мы умеем ее перекрашивать.

Этот вариант будет требовать не квадратичное, а O(n log n) количество операций.