Wataru

Формально по законам логики и определениям.
Что значит какой-то элемент принадлежит правому множеству?
x in A\(A\B), тогда и только тогда, когда x in A И x not in (A\B),
Чтобы вторая половина после И выполнялось, надо наложить отрицание не x in (A\B) что тоже самое, что (x in A И x not in B). По законам логики это будет (x not in A ИЛИ x in B). добавляем к этому первую часть и раскрываем скобки:

x in A И (x not in A ИЛИ x in B) = (x in A И x not in A) ИЛИ (x in A И x in B).

Первая часть - всегда ложна и сокращается, остается только (x in A И x in B), что по определению x in A и B. Мы везде использовали только эквивалентность и из определения, что элемент принадлежит правому множеству, получили определение, что элемент принадлежит левому множеству. Значит эти 2 множества равны.

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

[1=>{cost:1, name:"name1"} .... 117=>{cost:55233, name:"name555"}]

(не уверен, что правильно описал на js).

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

Можно поискать какие-нибудь js библиотеки с нормальным ассоциативным массивом, который это умеет.
Будет также работать за логарифм.

Проблема в том, что числа повторений в задаче ОЧЕНЬ большие.
Правильное решение должно не строить строку, а хранить ее в виде пар (символ, количество), как в RLE.
Самое быстрое решение - хранить список таких пар (или 2 списка). Но проще, и должно проходить по времени другое решение: Можно просто хранить массив этих пар (или 2 массива, один для символов, другой - для количества повторения).

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

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

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

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

| - это побитовое ИЛИ. & - побитовое И. Т.е. каждый разряд отдельно обрабатывается и, в случае ИЛИ, если хоть одно число имеет единицу в данном разряде, то и результат будет 1. Соответственно, 00001 | 00010 = 00011.

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

Чтобы проверить, что бит в числе установлен, надо взять побитовое И и убедиться, что результат не 0 (он может быть либо 0 либо какой-то степенью двойки.

Есть - перебирайте следующее число, начиная с p_(n-1)+1, потом проверяйте делимость на все простые числа, пока они меньше корня и текущего числа.

Можно применить следующие оптимизации - начинать с p_(n+1)+2 и идти с шагом 2 (только нечетные числа). Перебирать числа только вида 6k-1 и 6k+1 (k изначально floor(p_(n-1)+3) / 6). Вместо высчитывания корня, в коде должно быть возведение в квадрат - что-то вроде while (i < n && p[i]*p[i] <= x) ... i++;.

Это если вам уже дан список предыдущих простых чисел. Если же вы думаете над шагом алгоритма, который находит первые n простых чисел или все простые до какого-то K, то быстрее будет использовать решето эратосфена.

Если считается, что зависимость выхода от входа линейная, то ее можно составить так:
y = k*x+b

И вам даны 2 значения для x и y:

0 = k*2.3+b
400 = k*40.6+b

Вам надо найти k*11.6+b.

Система из двух линейных уравнений просто решается аналитически, без конкретных значений:

y1 = k*x1+b
y2 = k*x2+b

y1-y2 = k*(x1-x2) +(b-b)
k = (y1-y2)/(x1-x2)
b = y1 - k*x1 = y1 - (y1-y2)/(x1-x2)*x1

y = (y1-y2)/(x1-x2)*(x-x1) + y1

Подставляем туда ваши значения при x = :

y = (0-400)/(2.3-40.6)(11.6-2.3) + 0 = 400/38.3*9.3 = 43.81

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

Я там вам ответил, что это класическая задача на нахождение компонет связности в графе. Гуглите 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++, если это не ваш любимый уже язык программирования. В питон порог входа пониже.