Wataru

Бинарный поиск

Только надо чуть чуть изменить. В конце вы останетесь на каком-то элементе ближайшем к искомуму слева или справа.
Так что провертьте left и 2 соседних элемента на ближайшесть.

Вы пробовали подставлять в вашу формулу a=-1, b=1?

При x=-1, ваша формула выдаст y= 1.

Почему она не рисует ничего, я не могу сказать, не видя весь ваш код. Возможно у вас там что-то ломается из-за корней из отрицательных чисел. Надо сначала проверить. что x^3+ax+b >= 0, и только в этом случае вычислять y и рисовать точки. И, да, вам надо цикл по x гнать с отрицательных чисел тоже.

Можно сначала решить уравнение x^3+ax+b = 0, чтобы понять область определения функции.

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

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

Функция перебирает 2 варианта. Пусть отсавшаяся сумма s, а разрешенное максимальное число имеет номер i (они хранятся в каком-нибуть отсортированном a[]).

1) Берем текущее максимальное слагаемое. Естественно, если оно помещается в остаток s >= a[i]. Кладем его к текущим слагаемым в массив и рекурсивно вызываемся от уменьшенного остатка, не меняя максимальное число - (s-a[i], i). Важно - если слагаемые хранятся в глобальной переменной, то надо после рекурсивного вызова "вернуть как было" - удалить только что добавленное слагаемое из массива.

2) Пропускаем текущее максимальное число. Значит, больше его брать вообще нельзя. Вызываемся от (s, i-1). Естественно, этот вариант есть только если i>0.

Если мы получили, что оставшаяся сумма s равна нулю, то мы подобрали разбиение, надо вывести текущие слагаемые.

Ах да, чтобы этот метод хорошо работал имеет смысл слагаемые отсортировать по возрастанию. Чтобы сначала брались самые большие.

Если среди возможных слагаемых нет 1, то этот полный перебор может заходить в тупики. На пример, доступны слагаемые 6 и 11, надо набрать 29. Алгоритм может пропустить 11 и попытаться набрать 29 одними шестерками, но этого никогда не получится. Эти лишние тупиковые ветки можно обрезать и ускорить таким образом решение в некоторых случаях.

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

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

EDIT: Только заметил, что вам порядок важен и 1,2,3 считается отдельно от 3,1,2

Изменения просты - рекурсивная функция теперь принимает только один параметр - сколько осталость добрать. Вместо двух вариантов она перебирает N вариантов - какое именно число из разрешенных взять.

Оптимизация такая же. реализуете ДП, которое считает, сколько способов собрать заданное число и, если способов нет, возвращаемся из функции.

Не совсем понял вопрос, но, если вы имеете ввиду переписывания указателя на удаляемый элемент, то тут 2 подхода.

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

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

prev = cur;
cur = cur->next;

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

Можно писать так:

if ((i > 0 && a[i-1][j] > a[i][j]) || (i < n-1 &&  a[i+1][j] > a[i][j])) {
  // текущий элемент меньше хотя бы одного соседа в том же столбце.
}

еще можно так:

if ((i == 0 || a[i-1][j] > a[i][j]) && (i == n-1 ||  a[i+1][j] > a[i][j])) {
  // текущий элемент меньше всех соседей в том же столбце.
}

Комбинируя условия на циклы через || и && можно составить любое нужное вам условие, которое смотрит только на существующих соседей. Но тут важен порядок операций. В C++ (да и почти везде, на самом деле) условия выполняются слева направо и прекращают выполнение, как только результат становится известен. Вот, в первом примере сначала идет проверка на i>0 а потом обращение к массиву через логическое И. Поэтому, если программа будет обрабатывать первый элемент в строке уже на первом условии она заметит, что все условие обязательно false, ведь там стоит &&. И условие с обращением к массиву не будет произведено никогда.

Тут не важно, что массив двумерный. Фактически, вам надо вывести один массив символов с переносами. Только надо решить эту задачу отдельно для каждой строки двумерного массива.

Самое простое решение - в цикле вывода символов выводить '\n', если текущий символ 20-ый, 40-ой и т.д. Например, можно проверять (i+1) % 20 == 0.

Вариант простой - перебрать все участки 3x3 (смотрите левый верхний угол - это 2 цикла от 0 до width-3 и от 0 до height-3) и проверить, что они хорошие.

Для проверки можно или 1) проверить, что все числа от 1 до 9 и разные, или 2) проверить, что там ровно один раз каждая из цифр встречается. Второй вариант короче и быстрее, но для него вам придется завести массив счетчиков от 0 до 9. Перед каждой проверкой он занулен. Обойдите ваш 3x3 блок и увеличьте соответствующий счетчик (что-то типа count[a[beg_x+i][beg_y+j]]++). Только не забудьте проверить, что число от 1 до 9, чтобы не вылезать за границы массива. Потом пройдитесь по массиву счетчиков циклом от 1 до 9 и проверьте, что там везде стоят единицы.

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

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

Вот и считайте, сколько вариантов поставить палку перед каждой единицей. Надо подсчитать расстояния между каждой парой единиц и перемножить. Если единиц вообще нет - ответ 0, если одна - то 1.

Можно сделать за один проход, если запоминать, где стояла предыдущая единица.

int64_t CountWaysToSplit(std::string s) {
  int last_one = -1;
  int64_t res = 1;
  for (int i = 0; i < s.length(); ++i) {
    if (s[i] == '1') {
      if (last_one >= 0) res *= i - last_one;
      last_one = i;
    }
  }
  return last_one >= 0 ? res : 0;
}

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

Если же от вас требуется что-то более самостоятельное, то делайте так - найдите в строке операцию с наименьшим приоритетом (ту, которая будет выполнена последней). Рекурсивно выведите обратную польскую запись для левой и правой половины, потом выводите/выполняйте операцию.

Чтобы найти операцию - проходитесь по строке, считая сколько сейчас открыто скобок. Запомните позицию самого правого встреченного "+"/"-" и "*"/"/". Если ничего не нашли - значит можно откусить внешнюю пару скобок (если скобок нет, то вся строка - число). Иначе, если есть + или - - это та самая последняя операция. Если таковой нет - то будет * или / - берите ее.

Это работает за квадрат в отличии от алгоритма по ссылке, но зато пишется элементарно.