Mercury13

У генератора псевдослучайных чисел есть такое понятие, как «случайная затравка» (random seed). Затравку берут из истинно случайных мест вроде счётчика тактов процессора. Достаточно сохранить затравку — и последующие запуски генератора дадут те же результаты.

Допустим, манипуляции с затравкой есть вот тут.
php.net/manual/ru/function.mt-srand.php

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

Потому криптографические хэши огромные (устаревший MD5 — 16 байтов, большинство современных — 32 или 64). Как его записать в БД, если и тип такой не всегда есть, а BLOB’ы — пальба из пушки по муравьям? Как-то закодировать в строчку. К тому же в вебе есть места, где двоичные данные не катят и без строчного кодирования никак (например, URL’ы).

Автор, очевидно, мэн из лагеря Perl/PHP и в дополнение к вычислению хэша взял и закодировал его. Вероятно, методом BASE64 (8 символов BASE64 соответствуют 6-байтовому хэшу). Для чего так кодировать обычные, не криптографические хэши — я вообще не знаю!

Замкнуть выход на вход. Каждой вершине придумать вероятности (да хоть 1/n).
Получаем цепь Маркова, остаётся найти её эргодическое распределение.
Надо только придумать разглючку на случай, если ЦМ будет периодической — но, возможно, стандартные методы регуляризации СЛАУ с этим справятся.

По очереди для каждого из элементов.
1. Поставить его на последнее место.
2. Вызвать функцию рекурсивно с длиной на 1 меньшей.

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

Задача сложна и требует серьёзного исследования. Дело тут в том, что второй эшелон — склад промежуточного хранения — добавляют, если затраты НЕлинейны и в больших объёмах развоз товара дешевле. Это, конечно, можно сымитировать более дешёвым завозом на склады. (А также чтобы разгрузить «мёртвые запасы» магазинов и законом больших чисел скомпенсировать случайные колебания спроса, но это, как я понял, не ваше дело.)

У вас написано: «Стоимость доставки это расстояния между точками». Таким образом, стоимость доставки не зависит от объёма подвоза, а зависит только от расстояния? Тоже, так сказать, нелинейное поведение. Приближённое решение ищите в алгоритмах кластеризации: зона, охватываемая одним складом — и есть кластер. Если же нужно точнее, приходится использовать какие-нибудь эвристики.

Например, расположим семь складов в каких-нибудь городах, вычислим вытекающую стоимость. А теперь вопрос: можно ли перенести какой-нибудь склад в соседний город, чтобы было дешевле? Итерационно работаем, пока не уляжемся в «оптимальное положение». Случайно набрасываем семь точек — и «скатываемся вниз», пока не успокоимся, и так много-много раз.

Лучше выводить не одно решение, а несколько — например, до 120% от оптимального. Дело в том, что после компьютерного вычисления возникнут какие-то человеческие факторы: узнав, что восточный склад только в Комсомольске-на-Амуре, а северо-западный можно ставить где угодно в окрестностях Ленинграда, принимаем решение ставить склады в Комсомольске и недалеко от ленинградского метро.

Алгоритм такой.
1. Реализуй двоичный поиск с указанием места, куда вставить (см. Википедию).
2. Если вставить до первой позиции или за последнюю — return соотв. первое или последнее число.
3. В противном случае выяснить, какое ближе из (i−1)-го и i-го.

Дома проверю, где там ошибка в двоичном поиске, в нём любят ошибаться.

К тому же код у вас чисто олимпиадный, я бы отделил рабочую логику от генерации выходного файла.

Критерий таков.
1. Баланс ( и ) должен сохраниться.
2. а) Либо вырожденный случай (скобку меняем дважды на противоположную);
б) либо ) → ( идёт перед ( → );
в) либо уровень вложенности обеих скобок не менее 3, при этом они сидят в общих скобках 2-го уровня.

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

Очередь, физически не перемещающая элементы (кольцевая или некое подобие std::deque) и позволяющая по указателю быстро определить позицию.

Плюс любой индекс (хэш- или деревянный), элементы которого — указатели на элементы очереди. Если элементы очереди unique_ptr, то указатели будут именно на unique_ptr! Для «мусорных» языков (C#, Java) вместо указателей можно придумать какие-то идентификационные коды — например, сочетание из номера в пуле массивов и номера в массиве.

Enqueue — вписываем элемент в индекс. Dequeue — удаляем из индекса. Обмен позициями — корректируем эти два элемента индекса.

Это значит: объект класса B должен иметь (или не иметь) «товарища» класса C. Иметь не во владении, а по ссылке. А лучше не класса C, а его подмножества, реализованного как интерфейс (я его назвал IC). На A вообще чхаем — его задача собрать B и C в нужном виде, и всё.

Смотрите шаблон проектирования Dependency Injection.

class IC {   // interface
public:
  virtual int getC() = 0;
  virtual ~IC() = default;
};

class C : public IC {
public:
  int getC() final { return 42; }
};

class B {
public:
  IC* buddy() const { return fBuddy; }
  void setBuddy(IC* aBuddy) { fBuddy = aBuddy; }
  void someJob() const { if (fBuddy) std::cout << fBuddy->getC() << std::endl; }
private:
  IC* fBuddy = nullptr;
};

class A {
public:
  A() { b.setBuddy(&c); }
private:
  C c;
  B b;
}

Специально для тех, кто на Си++: в таком виде A неперемещаем из-за указателя c.fBuddy. Есть много способов исправить это — например, подправить конструктор копирования и операцию «присвоить» класса A.