Mercury13

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

#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². Почти уверен, что реально цифра меньше, просто думать над этим облом.

Создадим массив на 2N событий. Событие — эти тип («начало»/«конец»), № круга и координата. Каждый круг создаёт два события: начало на i−R и конец на i+R.
Массив сортируем по X, с таким уточнением, если X равны.
• Если касание считать пересечением, начало < конец (т.е. для точки X идут начала, затем концы). В такой ситуации нам не важны номера кругов.
• Если нет — сначала номера кругов (aka x-координаты центров) по возрастанию, затем начало < конец.
Заводим счётчик кругов. Проходимся по массиву.
• Если видим начало — к результату +счётчик, к счётчику +1.
• Если видим конец — к счётчику −1.

В нашем примере:
Счётчик 0, результат 0
Начало №1 на x=−4: результат 0, счётчик 1
Начало №0 на x=−1: результат 1, счётчик 2
Начало №2 на x=0: результат 3, счётчик 3
Начало №4 на x=0: результат 6, счётчик 4
Конец №0 на x=1: счётчик 3
Начало №3 на x=2: результат 9, счётчик 4
Затем аж два конца на x=4, счётчик опустился до 2
Начало №5 на x=5: результат 11, счётчик 3
Конец №5 на x=5: счётчик 2
И ещё два конца сбрасывают счётчик до 0.

UPD. Уточнил для случая, если касание — не пересечение.

Алгоритмы. Немного олимпиадного программирования ОЧЕНЬ не помешает. Алгоритмы там предлагают несложные, но очень нетривиальные, надо чувствовать, как решить задачу. Элементы сложности алгоритмов. Две задачи из восьми гарантированно будут.

Алгебра и дискретная математика. Первый курс, всё скопом, без доказательств. Линейные уравнения, квадратичные формы, матрицы, собственные векторы, жорданова форма, перестановки, графы, теория множеств, комбинаторика, алгебра логики…

Интегралы (не слишком «злые», но приёмы «подстановка», «по частям» и «тригонометрический интеграл» всё же освоить стоит). Интеграл средней сложности — постоянный гость в ШАДý. Может быть и ещё одна задача из мутьанализа — но это как повезёт и задача будет гарантированно нетривиальная, но решающаяся на «том, что помнишь с института» — дифференцирование, ряды Тейлора, основы топологии, простейшие пределы, правило Лопиталя. Вспомни, как берутся простейшие двойные интегралы, может попасться, например, на теории вероятностей.

ФКП. Самое начало. Аналитических функций и рядов Лорана точно не будет. А вот то, что в комплексном поле многочлен n-й степени имеет n корней, знать надо.

Теория вероятностей. Непрерывные и дискретные вероятности. Нечто несложное, почти что на уровне кубиков и карт, но одна-две из восьми будет. Хотя статистика — важная часть ШАДа, на экзамене не требуют. И пекла типа белых шумов и интегралов Ито не будет. Хотя что-то типа дискретной марковской цепи — а вдруг, хотя знакомые мне три экзамена не было.

Школьные олимпиадные задачи. Возможна одна.

Итого.
Две — алгоритмы.
Одна-две — вероятность.
Одна — интеграл.
Две-три — что угодно из школьной математики, дискретной математики, матанализа, алгебры, ФКП…

P.S. Очень хороший приём, который мне помог. Конечно, вам придётся держать скан какого-нибудь справочника или распечатку Википедии (это не возбраняется, но электроника запрещена — впрочем, калькулятора задачи не требуют). Печатайте на одной стороне, вторую — на черновик!

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

Для быстрой убывающий массив — один из лучших случаев, будет сделано ровно [n/2] обменов. Легко показать, что элементы в начале и конце массива, стоящие на своих местах, быстрая сортировка не сместит никогда. Так что первое, что сделает сортировка,— разобьёт на меньший (отсортированный) и больший (частично отсортированный как надо, частично — в обратном порядке). Ту часть, которая как надо, сортировка не тронет. А ту, которая наоборот — задействуем трансфинитную индукцию, и получаем, что ровно [n/2].

Разумеется, будем считать, что слова не должны быть осмысленными (иначе это другая задача, где этот алгоритм, с одной стороны, тяжеловат, с другой — совсем не нужен). Если между словами «коза» и «волк» расстояние 3, то промежуточные слова — «коза → воза → вола → волк». Или, если не против, «коза → козк →колк → волк».

Итак, перед нами типичный алгоритм динамического программирования. В алгоритме динамического программирования есть два этапа: обратный ход и прямой. Этот алгоритм страдает двумя недостатками, мешающими взять и написать прямой ход.
1. Матрица сжата. Вместо матрицы (M+1)×(N+1) мы имеем два массива длины N+1, хранящие одну строчку и потихоньку перезаписываемые.
2. Нет второй матрицы, которая указывает направление, куда идти. В нашем случае направления — это три действия над строкой: замена, вставка и удаление.
ну и 3) В сокращённом варианте хватит двух массивов, обмениваемых местами. К делу отношения не имеет, просто вопросы умелого программирования. Кажется, перед нами Java и утечек памяти тут нет — тем лучше.

С задачами 1 и 2 надо сделать три вещи.
1. Массивы D1 и D2 превратить в единую матрицу (M+1)×(N+1).
2. Добавить второй такой же. Элементы его — enum: удалить/вставить/заменить.
3. Написать прямой ход. Мы находимся в точке (M, N); смотрим, куда идти. Заменить — идём туда-то, вставить — идём туда-то, удалить — идём туда-то. Ну и, разумеется, выполняем нашу операцию на строках и выводим, что получилось. Продолжаем путь, пока не попадём в (0, 0).

Для 98% существительных — есть, и для этого копай шаблоны Викисловаря. Правда, так просто, по одному только слову «автомобили», нельзя, ведь тупая машина никак не поймёт, что «вижу автомобилев» — это вдвойне неверно (не угаданы группа и одушевлённость).
Надо задать:
• склонение (первое / второе / третье / разносклоняемое / несклоняемое);
• группу склонения (десятка полтора на каждое склонение);
• одушевлённость (влияет на дательный и винительный падежи, в зависимости от склонения).

Варианты.
1. Если граф циклический, максимальный путь — ∞.
2. Если циклический, но путь обязан быть несамопересекающимся — Дейкстра не подойдёт. Подобную олимпиадную задачу я решал и там решением был перебор с кэшированием (вершин вроде до 15).
3. Если граф циклический, но есть отрицательные веса, которые в определённых случаях дают-таки точный максимум — меняем знак, применяем модификацию Дейкстры для отрицательных весов. Он либо скажет, что есть цикл, позволяющий сколь угодно уменьшить сумму, либо даст точный минимум.
4. Если ациклический ненаправленный — то либо один, либо нет вообще (т.н. лес);
5. Если ациклический направленный — должен работать совсем другой алгоритм: отсортировать в топологическом порядке, убрать те элементы, которые перед началом и за концом, а на оставшихся пустить динамическое программирование.