Wataru

Вы правильно поняли, какого вида числа будут в последовательности (перемноженные степени 2, 3 и 5).

Проблема в том, что вы, например, пропустите число 2^23, которое входит в первые 10000.

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

Но скорее всего, придется поменять алгоритм. Поскольку ограничения маленькие, то тут можно делать что-то типа BFS. Вы вычисляйте числа в последовательности по порядку. И поддерживайте множество возможных следующих чисел. Каждый раз дописывайте минимальное число из кандидатов к последовательности и добавляйте к кандидатам это новое число, умноженное на 2, на 3 или на 5. Это будет квадратичный алгоритм. Можно использовать heap или какой-нибудь set, тогда будет за O(n log n).

Еще есть линейный алгоритм. Он получается из предыдущего так: все кандидаты разбейте на 3 множества - те, которые получены домножением на 2, на 3 и на 5. Каждое такое множество в итоге будет тупо сама же последовательность, домноженная на 2, 3 или 5. Поэтому единственное, что вам надо знать для полного описания кандидатов - это какое число из последовательности было домножено на 2,3 или 5. Это три индекса.

Т.е. решение будет поддерживать три индекса в уже сгенерированном массиве. Потом смотреть, какое число, домноженное на соответсвующий множитель минимально, это число дописывать в последовательность и этот индекс сдвигать на 1.

Вам придется работать с winapi.

Вам нужно создать прозрачное окно и рисовать в него то, что идет поверх рабочего стола (гуглите "winapi draw in transparent window").

Чтобы не рисовать поверх каких-то окон - надо в каком-то битмапе нарисовать черным цветом силуэты всех этих окон (надо все окна в системе перебрать - тут вам помогут всякие всякие GetWindowRect, EnumWindows, IsWindowVisible.). И при проприсовке надо этот битмап брать как маску (гуглите "winapi clip region").

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

Простой в реализации метод: держите отрезки в каждом элементе отсортированными и непересекающимеся (если два отрезка пересекаются - объедените их).

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

Если же список очень длинный, а ответ ожидается маленький, то есть более быстрый метод. Но он сложный в реализации. Нужно реализовать персистентное дерево поиска. Можно его реализовать на основе персистентного дерева отрезков. Это такая структура, в которую можно добавлять элементы, и удалять их за O(log n). Также можно обходить все элементы за O(log n + (их количество)). Кроме того, сохраняются все версии дерева после каждой операции и общее количество памяти будет O(к log n), где к - количество операций.

Эта структура будет использоватся для хранения предподсчитанных ответов. Если все ваши отрезки нарисовать на одной прямой, то она разобъется на O(n) отрезков, все точки которого будут давать один и тот же ответ при запросе. Мы эти все ответы компактно сохраним.

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

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

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

Это решение требует O(n log n) памяти (где n - количество всех отрезков) и O(n log n) времени на предподсчет и O( log n + (ответ)) времени на обработку ответа.

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

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

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

// пусть x = 00001011b
x = ~x;  // 11110100b
x = x ^ (x-1);  // 11110100 xor 11110011 = 00000111
x = ((x >> 1) & 01010101b)+(x & 01010101b);  // 00 00 01 10
x = ((x >> 2) & 00110011b)+(x & 00110011b);  // 0000 0011
x = ((x >> 4) & 00001111b)+(x & 00001111b);  // 00000011 = 2
x -= 1; // индексация с 0

Отдельно надо проверить, вдруг изначальное число было 255 - в таком случае искомого бита нет, но этот код вернет 7.

Можно сделать для большего количества бит, надо только еще операций добавить и маски расширить. Для 32-битных чисел надо будет добавить еще 2 операции.

Еще есть вариант с ассемблером в x86 есть операция popcnt.

У вас цикл на 10 итераций (for (int count=0; count < 10; ++count)). С возможным ранним выходом (break).

Что вы подразумеваете под словом "эффективный"?

Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

Обычно под словом "эффективный" подразумевают полиномиальный алгоритм. Такой алгоритм тут, очевидно, не существует (потому что надо перебрать экспоненциальное количество объектов).

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

Попробуйте удалить и скомпилировать. Компилятор что говорит?

Константный вектор. Можно вызывать только константные методы, переприсваивать или как-то изменять нельзя.

Но откуда тут вообще может быть непонимание? В C++ никогда нельзя менять, на что ссылаются ссылки. const/не const может быть только то, на что оно ссылается.

Edit: изначально я тут некорректно назвал это константной ссылкой, но по хорошему, оно называется ссылка на константу.

Используйте функцию max.

Значение в каждой ячейке будет

max(0, (тукущее значение) - max(0, (платеж) - (сумма всех следующих ячеек)))

Поскольку нужны будут все частичные суммы, то есть смысл в соседних ячейках подсчитать все эти суммы.

Вы сами ответили на свой вопрос - "Обычные однобайтовые символы". Какая разница, в каком порядке этот один байт записывать?

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

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

Простейшая задача на bfs. Без кода сложно сказать, где накосячено.

Никакого переполнения быть не может, bigInteger вам не нужен. Даже long не нужен: максимальная длина пути - 10000.

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

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

Или файл не открывается, потому что его нет, или у вас компилируется через C++98.
В документации написанно (примечание после параметров):

If the mode has both trunc and app set, the opening operation fails. It also fails if either is set but out is not, or if both app and in are set.

Вы же, судя по комментариям, открываете с app и in вместе.

Вам точно надо читать и писать из этого файла да еще и увеличивать его размер?

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

Динамическое программирование.

F(i,k) - максимальная сумма, которую можно получить из первых i троек, такая что ее остаток от деления на 4 равен k.

База: F(0,0) = 0, F(0,k) = -infinity.
Ответ: F(n, 0).

Пересчет

F(i,k) = max(F(i-1, ((k-a[i][0]-a[i][1])%4+4)%4)+a[i][0]+a[i][1], 
             F(i-1, ((k-a[i][1]-a[i][2])%4+4)%4)+a[i][1]+a[i][2], 
             F(i-1, ((k-a[i][0]-a[i][2])%4+4)%4)+a[i][0]+a[i][2])

Только лучше вместо -infinity как-то отмечать, что позиция (i,k) недопустима (нельзя первыми i тройками набрать сумму с остатком k. И недопустимые варианты при выборе максимума выбирать ненадо.

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

Сравнивайте дальше третии символы в строках, если первые совпадают.
Или сравнивайте строки через strcmp.