Wataru

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

Советую посмотреть в сторону Burrows-Wheeler transform и потом попробовать RLE или LZ присобачить сверху. Может, ваши данные будут им хорошо сжиматься.

Еще вам тут сильно помогло бы что-то вроде Base64 encode/decode. Допустим у вас k символов в алфавите. Значит каждый символ несет log_2(k) бит. И если у вас символов N, то ваша входная строка содержит N*log_2(k) бит информации. Округлите это число вверх и сгенерируйте столько битов. Это фактически преобразование из k-ичной системы счисления в двоичную. На больших строках будет тормозить, потому что пока мне не очевидно, как для произвольного k делать преобразование быстро, а не делить большое число на 2 с остатком. Если только у вас k не степень двойки, тогда как в base64 можно быстро преобразовывать по блокам.

Потом можно эту битовую строку сжать каким угодно алгоритмом (разбить на блоки, скажем, 8 бит и хоть хаффманом, хоть lz). Потом надо сжатую битовую строку преобразовать назад в k-ичную систему счисления.

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

Читайте строку std::string. Проверяйте,что в ней максимум 1 '-' в самом начале, далее первая цифра не '0' (если второй не ',', есть максимум один символ ',' и он не первый. Потом используйте stringstream чтобы прочитать double.

Нужен генератор случайных чисел. в JS есть Math.random();

Далее, чтобы сгенерировать один массив пройдитесь по всему массиву строк и добавляйте текущую строку к ответу, если random() < kThreshold. kThreshold подбирайте исходя из того, какой длины вам нужны случайные массивы. В среднем в ответе будет kThreshold*array.length() элементов. Т.е. при kThreshold=0.5, в среднем сгенерированные массивы будут содержать по половине всех строк.

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

Умение программировать - это прежде всего некоторая разновидность умения мыслить абстрактно. Это возможность в уме составить последовательность действий приводящих к нужному результату и записать ее на языке программирования.

Сверху к этому добавляется знание структур данных и алгоритмов и хорошее знание языка программирования, его библиотеки и конструкций. Но эти все знания второстепенные. Не нужно все это знать наизусть. Достаточно иметь представление, что в языке есть vector для массивов и set для множеств. Конкретные функции можно подсмотреть в справке или гугле.

По мере приобретения опыта эти стандартные части языка и алгоритмы станут базой и запомнятся.

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

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

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

Функция берет из текущего массива один из элементов в цикле и добавляет его к ответу и запускается рукурсивно от следующего массива. Еще функция не берет ничего из текущего массива и запускается рекурсивно.

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

Псевдокод примерно такой (не php, чтобы не позориться):

function Generate(result, array_index, arrays) {
  if(result >= len(arrays)) {
    print(result)
    return
  }
  if (min_length - len(result) < len(arrays)-array_index-1) {
    Generate(answer, array_index+1, arrays);
  }
  if (len(answer) < max_length) {
    for i = 0...len(arrays[array_index]) {
      answer.push_back(arrays[array_index][i]);
      Generate(answer, array_index+1, arrays);
      answer.pop_back();
    }
  }
}

Формально по законам логики и определениям.
Что значит какой-то элемент принадлежит правому множеству?
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