Mercury13

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

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

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

Лучше выводить не одно решение, а несколько — например, до 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.

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

Заводим три переменных: firstDay, lastDay, workHours. Поначалу они пустые строки.
Проходимся по всем элементам.
• Если рабочие часы совпадают с workHours — перезаписываем lastDay, и всё.
• А если нет — проводим функцию dump, перезаписываем все три.
После цикла принудительно проводим dump.

Как должна работать функция dump.
• Если workHours пусто — ничего не делаем.
• Если результирующая строка непуста — добавляем разделитель.
• В зависимости от того, совпадают ли firstDay и lastDay, добавляем «Пн» или «Пн-Пт».
• Ну и, наконец, добавляем рабочие часы.

Неплохие результаты получились с одной из первых версий с простейшим патчем на повторы.

#include <iostream>

struct Sector
{
    char name;
    int total, counter, remainder;
    bool allowNearby;
};

enum { N = 3 };
Sector secs[] { { 'A', 3 }, { 'B', 6 }, { 'C', 30 } };

int main()
{
    int nTotal = 0;
    for (int i = 0; i < N; ++i) {
        Sector& sec = secs[i];
        nTotal += sec.total;
    }
    for (int i = 0; i < N; ++i) {
        Sector& sec = secs[i];
        sec.counter = sec.total;
        sec.remainder = sec.total;
        sec.allowNearby = (sec.total * 2 > nTotal);
    }

    Sector* repeatS = nullptr;
    for (int iSec = 0; iSec < nTotal; ++iSec) {
        Sector* bestS = nullptr;
        for (int i = 0; i < N; ++i) {
            Sector& sec = secs[i];
            if (sec.remainder != 0 && &sec != repeatS) {
                if (!bestS) {   // первый подходящий?
                    bestS = &sec;
                } else {    // лучше bestS?
                    if (sec.counter < bestS->counter
                            || (sec.counter == bestS->counter && sec.total > bestS->total))
                        bestS = &sec;
                }
            }
        }
        if (!bestS)     // так и не нашли, что брать — берём repeatS
            bestS = repeatS;

        // пересчитаем счётчик и остаток
        bestS->counter += nTotal * 2;
        --bestS->remainder;

        for (int i = 0; i < N; ++i) {
            Sector& sec = secs[i];
            sec.counter -= sec.total * 2;
        }
        repeatS = bestS->allowNearby ? nullptr : bestS;
        std::cout << bestS->name;
    }
    std::cout << std::endl;
}

Пишу на «си с крестами». Раз уж вы работаете на PHP, вместо указателей придётся держать «лучший индекс» и «последний индекс».

Принцип программы прост. Счётчики считают вниз с разной скоростью; чем чаще встречается сектор, тем быстрее. Приоритет взятия такой: не исчерпан → без повторов → у кого счётчик меньше → какой встречается чаще. Однако если какого-то сектора больше 50%, для него повторы вполне себе разрешены.

Упаковка параллелепипедов. NP-полная задача, точное решение — перебор. Сам решал упаковку прямоугольников (т.е. в 2D) генетическим алгоритмом с переменным успехом.
Скорее всего, у вашей службы доставки есть ящики стандартного размера — потому стоило бы приспосабливаться к этим ящикам.

Твоё дело — перебор с кэшированием.
Для каждой кнопки вручную закидываем в массив конских «соседей» — ни одного для 5-ки, три для 4 и 6, два для остальных.
Затем заведи массив 10×7 (стартовая кнопка×длина) и устрой рекурсию с одним небольшим добавлением: если оно закэшировано, брать из кэша. Правила — f(b, 1) = 1, для остальных — sum{c=сосед(b)} f(c, i−1).
Можно и динамическим программированием, без рекурсии — всё равно расход вычислительной мощи незначительный. Сначала f(b, 2), затем f(b, 3), и т.д. до 7.

По Википедии…

Резисторно-транзисторная
Эмиттерно-связанная
Диодно-транзисторная
Транзисторно-транзисторная
Интегрально-инжекционная
На диодах и транзисторах Шоттки (традиционно и неверно тоже считается ТТЛ)
n-МОП
КМОП

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

Смысл транзистора (в ключевом режиме) — переключением одной цепи мы переключаем другую. Это же можно сделать и на радиолампах, и на реле.

Копаясь по Википедии, я выяснил, что нелинейные элементы, пригодные для логики, должны обладать такими свойствами.
• Восстановление логических уровней — если на вход придёт плохой «0» или плохая «1» (но всё же он примет её за 0 или 1), на выходе будет «0» или «1» значительно лучшего качества.
• Каскадируемость: можно наладить g(f(x)).
• Fan-in: возможность использовать несколько сигналов одним элементом.
• Fan-out: выдача сигнала на несколько элементов.
• Изоляция между входами и выходами.

Говорят, будущее — оптические компьютеры, но на входах и выходах таких компьютеров один хрен придётся свет преобразовывать в электричество.

Если что-то сделать, не используя процессоры — к вашим услугам аналоговые вычислительные машины. Без транзисторов и тиристоров в них (электронных, естественно) тоже никуда, но процессора в них нет. А ведь есть и механические АВМ (гуглите, например, ПУАЗО, немало крови попортивший немецким бомбовозам), и гидравлические АВМ (гуглите гидроинтегратор, MONIAC).

ЗЫ. На резисторах, конденсаторах и прочих пассивных не получится: нужен активный элемент, т.е. который умеет управлять потоками энергии, а не только рассеивать или накапливать. На диодах, думаю, можно, но тяжело.

Тут чёткое динамическое программирование. У нас N+1 операнд, и N операций.
Создаём кэш: для всех L и R, 0<=L<=R<=N, мы храним:
• Операцию: null, +, ×, many.
• Ассоциативный массив:
•• Ключ — число (целое/рациональное/плавающее/фиксированное — с какими хотите работать).
̃•• Значение — тройка:
••• Номер операции с макс. приоритетом.
••• Значение слева (такое же число).
••• Значение справа (такое же число).
Для всех L=R кэш заполнен такой величиной:
• Операция — null.
• В массиве один элемент: ключ — операнд, значение — любая затычка.
Для кэша годится, например, матрица (N+1)×(N+1).

После этого проходимся по диагоналям нашего кэша, обрабатывая сначала L=0..N−1, R=L+1, затем L=0..N−2, R=L+2, и т.д., пока на дойдём до диагонали из одного элемента: L=0, R=N. Как именно обрабатываем?
1. Смотрим операцию, записанную в кэше (L+1, R), и L-ю операцию в выражении. Если вторая — «сложить» или «умножить», а первая — null или совпадает, записываем эту операцию в кэш на место (L, R). Иначе — пишем many.
2. Вычисляем R1: если в кэше на месте (L, R) есть какая-то операция, то L; если many — то R−1 (оптимизация по ассоциативности).
3. Проходимся по всем M=L…R1.
3.1. Двойным циклом проходимся по содержимому кэша в (L,M) и (M+1, R). Обозначим переменные u и v.
3.1.1. Записываем в кэш на место (L,R), если таковое отсутствует:
       • ключ u (+−×/) v
       • номер операции — M
       • значения слева и справа — u и v.
Рассмотрим, например 1 + 2 + 3 − 4.
(0, 0) — null; (1 → ? ? ?)
(1, 1) — null, (2 → ? ? ?)
(2, 2) — null, (3 → ? ? ?)
(3, 3) — null, (4 → ? ? ?)

UPD: Операнды у наc { 1 2 3 4 }, орерации { + + − }. Ну разумеется.

Теперь смотрим, что будет в (0, 1). В (1, 1) в кэше null, нулевая операция + — операция +. Одна итерация, R1=0.
Прокрутив эту итерацию, получаем…
(0, 1) — +; (3 → 0 1 2). Это означает: получили 3, сложив 0-м плюсом 1 и 2.
Аналогично…
(1, 2) — +; (5 → 1 2 3)
(2, 3) — many; (−1 → 2 3 4)

Вторая диагональ. (0, 2). В позиции (1, 2): в кэше +, 0-я операция +. Записываем + и прокручиваем одну итерацию, от 0 до 0. Т.е. складываем (0, 0) и (1, 2).
(0, 2) — +; (6 → 0 1 5).
Теперь (1, 3). Операция будет many; прокручиваем и получаем:
для M=1 — складываем (1, 1) и (2, 3), и получаем (1 → 1, 2, −1).
для M=2 — вычитаем (1, 2) и (3, 3), и получаем (1 → 2, 5, 4).
Если без дублей…
(1,3) — many; (1 → 1 2 -1)

Ну и, наконец, пошли (0, 3). Операция будет many…
для M=0 — складываем (0, 0) и (1, 3), и будет (2 → 0 1 1).
для M=1 — складываем (0, 1) и (2, 3), и будет (2 → 1 3 −1).
для M=2 — вычитаем (0, 2) и (3, 3), и будет (2 → 2 6 −4). Повторим, что это значит: получилось 2, из-за того, что вычли 2-м минусом 6 и −4.
Итого, без дублей, (0, 3) — many, (2 → 0 1 1).

Так «повезло», что у нас вышел один результат. Но в результате объединения может быть и множество.

А теперь вопрос: откуда мы получили 2-ку? Смотрим в (0, 3) и получаем: 2 = 1 +₀ 1. Левую единицу раскрываем через (0, 0), правую — через (1, 3): 2 = 1 +₀ 2 +₁ (−1).
Остаётся раскрыть −1, и получаем 2 = 1 + 2 + 3 − 4.
Это можно сделать рекурсивно.

Если точный путь вычислений не нужен, ассоциативный массив превращается в множество без повторов. Не (2 → 0 1 1), а просто 2.
Во многих вариантах динамического программирования, если прямой ход не нужен, двухмерный кэш можно превратить в одномерный. Тут я не вижу способа. Написал, да понял, что ошибся.

UPD. А сложность какая? — у меня выходит 2ⁿ·n². Почти уверен, что реально цифра меньше, просто думать над этим облом.