Wataru

Вы уже задавали этот вопрос.

Я там вам ответил, что это класическая задача на нахождение компонет связности в графе. Гуглите DFS, компоненты связности, графы. Я там даже технических деталей кучу привел.

*offtopic* Лет 15 назад делал такое для записывания анимешных сериалов на CD-диски, только там было сложнее, потому что сериалы можно разбивать по нескольким дискам и записывать можно толко сериалы целиком. Эх... было время. Сейчас эти 300 дисков даже и прочитать-то нечем. И исходники пропали лет 10 назад =(.

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

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

Потом сморите в конце массива для всех файлов - это оптимальные заполнения одной флешки.

Удалите файлы определенные на эту флешку из рассмотрения и повторяйте процесс.

Можно навесить сверху полный перебор с отсечениями. Из массива ДП идля задачи о рюкзаке можно случайным образом получить несколько хороших заполнений.

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

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

Альтернативно - составьте задачу целочисленного линейного программирование (integer linear programming) и натравите на нее какой-то из солверов. Они сейчас очень продвинутые. Правда тут уж как повезет. Может на вашей задаче вы ответа так и не дождетесь. В качестве переменных берите, что такой-то файл относится к такой-то флешке. Сумма по каждому файлу - ровно один. По каждой флешке сумма размеров файлов * на переменные <= размер флешки. Сумма свободных мест - минимизируется.

Возможно, можно составить квадратичную целевую функцию, я не знаю, что сейчас солверы умеют. Гуглите quadratic integer programming solver.

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

У вас решение за куб, хотя тут должно быть решение за квадрат. Скорее всего вы получаете time limit.

Заведите 2 массива - min_row и max_column и одним проходом заполните их, используя функции, которые у вас уже есть. И только потом приходитесь по всей матрице и сравнивайте текущий элемент с уже известными максимумом/минимумом.

В конце выводите тоже через writeln. Инициализируйте максимум/минимум самыми большими возможными значениями или первыми элементами строки/столбца. Что если в матрице все числа 92233720+1?

P.s В данном контексте строка - row, точка - point. Седловая точка - saddle_point.

У вас сильно наворочено - много где можно ошибиться. Какие-то indexOf() используете кучу раз, хотя можно просто сравнивать символы через CharAt(), субстиринги везде. Советую переписать ваше решение с нуля, искать в нем ошибки невозможно.

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

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

Что-то вроде этого (читайте как псевдокод, я джаву не особо знаю):

public static int isEqual(String firstString, String secondString) {
  int used = 0;
  int[] first = new int[256], second = new int[256];
  if (firstString == secondString) return 1;
  if (firstString.length() != secondString.length()) return 0;
  for (i = 0; i < firstString.lengt(); ++i) {
    int ch1 = Character.getNumericValue(firstString.charAt(i));
    int ch2 = Character.getNumericValue(secondString.charAt(i));
    if (first[ch1] == 0) {
      used++;
    }
    if (first[ch1] != second[ch2]) return 0;
    first[ch1] = i+1;  // +1, потому что изначальные 0 означают "символ не встречался"
    second[ch2] = i+1; 
  }
  if (used == 33) return 0;
  return 1;

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

Вот алгоритм для перемешивания массива, если у вас есть детерминированная функция rand(), которую вы каким-то seed проинициализровали.

for (i = 1; i<arr.length; ++i) {
 let j = floor(rand()*(i+1));
 let tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}

Можно использовать что-то вроде функции, предложенной twobomb, но именно той функцией пользоваться не советую - она выдаст максимум 67 различных вариантов, а на самом деле сильно меньше. Используйте, например, параметры отсюда:

function rand(){
 	seed = (16,807*seed) % 2,147,483,647;
 	return seed/2,147,483,647;
}

Если вам на практике - то неважно. Используйте готовую криптографию. Библиотеки есть на все популярные языки.

Если же вам для академических целей или интереса ради хочется самим написать какую-то криптографию, то лучше брать язык программирования, где есть удобная длинаая арифметика. Таким является, например, python. Код будет проще и понятнее. В Java можно было бы использовать BigInteger, но им пользоваться неудобно (всякие конструкции вида a.Add(b).Blablabla(c).Blablabla(d)). В C++ можно переопределить операторы для класса длинных чисел, но я не советую писать на C++, если это не ваш любимый уже язык программирования. В питон порог входа пониже.

тут много проблем.

1) не надо в конце part менять местами 0-ой и i-ый элементы. Это бессмысленно. Вы поддерживаете вариант, что элементы с 0 по i-ый <=x, c j-ого и дальше >=x

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

3) Что у вас с рекурсивными вызовами твориться? Вы хвостовую рекурсию руками схлопнули что ли? А зачем выбирать, с какой стороны рекурсивно вызваться, а с какую дальше в цикле обрабатывать? Там у вас что-то с вычислениями напутанно, всякие +-1 неверно распиханы. Вы там делаете k -= left+1 и k -= right+1. По логике в одной половине left элементов, в другой - right. Тогда почему вы -1 еще делаете и там и там?

Не совсем понятен ваш код слияния двух массивов отрезков. Я бы все промежуточные точки тупо загнал в один вектор и отсортировал. Ну или сделал стандартное слияние двух отсортированных массивов. Дальше в цикле считал бы на отрезке между двумя соседними точками (если длина отрезка хотя бы 1e-6), Параметры кривых ищутся легко - держите 2 счетчика, как у вас уже есть, и двигайте их, пока текущий отрезок для той или иной функции не станет закрываться позже начала текущего отрезка. Может ваш код и эквивалентен этому, но я в этом не уверен.

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

Еще, очевидная проблема вот: comp_a != 0. Флоаты нельзя никогда сравнивать точно. Только с епсилон:

x < y  ====> x < y - eps
x <= y ====> x < y + eps 
x == y ====> fabs(x-y) < eps
x != y ====> fabs(x-y) > eps

В тупую можно подсчитать 2-мя вложенными циклами.

ans = 0;
for (i = 1; i <= 3; ++i) {
  for (j = 1; j <= 3; ++j) {
    mn = max(n - i - j - 3, 1);
    mx = n - i - j - 1;
    if (mn <= mx)
      ans += mx - mn + 1;
  }
}

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

Но это если у вас параметры фиксированные (4 блока 1-3 символа). Если параметры могут меняться, то решение - динамическое программирование f(i,k) - сколько способов разбить первые i символов на k блоков.

База: f(0,0) = 1, f(0, k>0) = 0, f (i>0, 0) = 0;
Пересчет: f(i,k) = sum_{l=min_length...min(max_length, i)}(f(i-l,k-1)).
Ответ: f(n, num_blocks).

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

Перенумеруйте все емейлы и всех пользователей.
Код будет проще, если емейлы и пользователи хранятся в одном и том же пространстве номеров.
Это реализуется с одним hashMap, который будет давать номер по строке, и одним массивом строк, который будет хранить изначальную строку по номеру. Вам еще понадобится булевый массив, чтобы хранить, является ли данная вершина пользователем или мейлом. При вводе получаете какую-то строку, и вызываете от нее функцию GetID(s, is_user), которая проверяет, есть ли данная строка в мапе. Если есть, возвращает номер. Если нет - дописывает строку в массив строк, записывает ее индекс в мап и возвращает его.

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

Заведите массив пометок "обойденности" для всех вершин. Он будет int. 0 - непосещенные вершины, иначе номер компоненты связности.
Запустите на этом графе DFS/BFS от каждой пока не обойденной вершины в цикле и помечайте все достижимые вершины новым числом (можно передавать вторым параметром в DFS). Можно сразу же во время обхода заполнять структуру ответ - один номер для пользователя и список для емейлов. Или можно после цикла с DFS завести массив списков для ответа, пройтись по массиву и распихать номера вершин по спискам. Используйте булевый массив, чтобы понять какая вершина пользователь, а какая - мейл. Из пользователей возьмите только одного предстваителя, а все емейлы запихайте в список в ответ. Потом выводите, преобразуя номера в строки с помощью имеющегося массива.

Если зависимость может быть любая (например, числа фиббоначи) - то никак. Можно поискать последовательность на oeis.org

Если же возможна только зависимость вида +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... т.е. повторяющийся фиксированный паттерн приращений, то есть быстрое и простое решение.

Во первых, если вам дано 10 чисел, то всегда можно сказать, что есть паттерн длиной в 9 приращений.
Но можно найти кратчайший паттерн с помощью алгоритма поиска периода в строке. Буквально, по определению, нужный вам кратчайший паттерн (типа {+3, -2} для второго примера) будет периодом строки. Правда, тут не строка, а массив чисел, но это вообще никак не меняет алгоритмы. Просто у вас алфавит нестандартный.

Сначала от массива чисел перейдите к массиву приращений.

Потом можно применить жадное наивное решение - просто перебираете все возможные значения периода от 1 до n/2 и проверяете, что a[i] == a[i+str] для всех i. Как только все совпало - вы нашли период. Это решение за квадрат. Если чисел вам задано много, то можно применить префикс функцию: найдите значение префикс функции (p) для всей строки и, если ее значение больше половины длины строки, то у строки есть период n-p. Это будет линейное решение.

Еще можно применить алгоритм Дюваля. Тоже линейное решение, но более сложное в реализации и понимании.

Ваше решение не работает на примере "аб аа".

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

Но в ваше решение еще не рассматривает крайний случай - использованы все 33 буквы алфавита и есть надо что-то менять. Тут ответ 0, потому что замены делать никак не получится - после любой замены 2 разные типа букв станут одинаковыми и перемешаются. Разделить их после этого уже не получится.

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

И еще. Не надо разбивать строки через .split(''). В JavaScript можно узнать длину строк и обратиться к i-ому символу не преобразуя в массив.

Если все сайты не подключают какой-то один и тот же скрипт/шаблон, то единственный вариант - это обойти все папки и добавить код куда надо (в html шаблон или какой-то js файл, я хз, как ваша cms устроена).

Если такой файл есть, то допишите код окна туда. Если cms одна и та же и сайты сделаны однообразно, то есть надежда, что такой файл существует. Можно вообще извратиться (если решение временное), вдруг у вас один и тот же условный /jquery.js подключатся во всех подпапках. Вот в него и впихивайте хоть alert(), хоть dom-манипуляцию.

Если же в каждой папке полностью независимая копия, то - увы.

Раз все cms одинаковые, то, скорее всего, есть какой-то одинаково называющийся файл во всех, в который код окна и можно добавить. Но не обязательно это делать руками N раз.

Все эти файлы надо найти каким-то скриптом, а потом как-то в них вставить код.
Если на линухе, то можно файлы найти аж так - передайте "./*/some-fixed-path/file-we-need.js" в качестве параметра в скрипт и bash сам раскроет шаблон и найдет все файлы. А скрипт может вызывать тупо patch < diff.txt. Вы руками внесите изменения в один файл, сделайте diff, и его результат скармливайте patch. Если изменения можно внести в одно и то же место во всех файлах (в самое, начало, например), то все сработает без ошибок. Читайте man diff, man patch. Еще можно man find.