Минутка великодержавнаго шовинизьму

Пяток забавных заимствований из польского языка в русский.

русский польский перевод происходит от
скарб skarb сокровище праслав. *skъrbъ
малевать malować рисовать нем. malen
огульный ogólny всеобщий праслав. *golъ
гонор honor честь лат. honor

Хотел было добавить сюда слово «гроши», бо на украинском то «деньги», но на польском «grosze» то же, что и в русском — ничтожная сумма денег, «za grosze» — «за гроши», «дёшево». В конечном итоге, «грош» от лат. «denarius grossus» — «большой денарий».

Реклама

Игла и rota

Продолжаю свои дилетантские лингвистические изыскания. Речь пойдёт о двух не связанных друг с другом словах: славянском «игла» и латинском «rota» (колесо). Впрочем, есть у них кое-что общее…

Итак, «игла» — праслав. *jьgъla. Цитируя Фасмера в переводе Трубачёва:
«Праслав. *jьgъla сравнивают кельт. *joug- в кимр. gwnïо «шить», ирл. conōigim «шью», возм., относится сюда же. Сюда же относят лат. аеgеr «больной», латышск. îgstu, îgt «чахнуть, изнывать», которые связаны с лит. ingzdù «жалуюсь», польск. jędzа «фурия, ведьма» (см. яга́). Др.-прусск. аусulо «игла» нельзя отрывать от греч. αἶκλοι ̇αἱ γωνίαι τοῦ βέλους (Гесихий), αἰχμή «остриё», которые связаны с лит. iẽšmas, др.-прусск. aysmis «вертел». Также сближают слав. jьgъla с нем. Nаgеl «гвоздь».»

Заметим ссылку на древнепрусский язык, все остальные сближения, по большому счёту, гадательны.
Др.-греч. αἰχμή связывают с латинским īcō «колю». В базе Starling эти слова возводятся к корню *ayḱ-, который сам по себе выглядит сомнительно (*ay-?), и даёт лит. iẽšma, лтш. iesms, др.-прусск. aysmis (по тому же словарю) со значениями вроде «пика, вертел». Славянский аналог мог бы выглядеть как **ѣс/ш- (например, ѣсма/ѣшма) или **ис/ш- (исма/ишма), но такого слова вроде как нет. Получить из этого корня (даже если признать его существование в ПИЕ) «иглу» можно лишь со множеством предположений, что делает связь крайне гипотетичной.

ЭССЯ предлагает экстравагантную версию происхождения «иглы» от слова «иго» < праслав. *jьgo < ПИЕ *yugóm. «Иго» — это перекладина, позволяющая соединить пару волов и груз, который они должны тащить. По версии ЭССЯ, «игла» — это остриё + «иго» (игольное ушко) — инновация, позволяющия совместить процесс протыкания материала и протягивания нити через отверстие, повысив производительность труда. Действительно, в языках слова для обозначения иглы нередко производятся от глагола со значением «шить» (связывать нитью). Пример — англ. needle (однокоренное, кстати, с русским «нить») от ПИЕ *(s)neh₁-. В славянских же языках инструмент для шитья называется «шило» (*šidlo). Шило используется только для проделывания отверстий, оно не имеет ушка для нити.

Однако, предположив, что славянский язык таким образом отражает древнюю инновацию — изобретение иглы — и производит это слово самостоятельно, мы должны датировать славянский язык палеолитом — именно тогда появились иглы с ушком, выполненные из кости. В то же время собственно праиндоевропейский язык относится к медному веку. Возраст медных игл из Египта оценивается в 6 тыс. лет и более. Всё это заставляет меня усомниться в изобретении особого слова для названия иглы на славянской почве уже после распада ПИЕ и предположить заимствование данного слова. Что же, в каменном веке люди уже делали иглы с ушком, а у славян не было для них слова? Отдельного слова действительно могло не быть (например, «шило» могло использоваться более широко). Но даже наличие своего слова порой не препятствует замещению этого слова импортированным. Это происходит либо из-за влияния суперстрата (хороший пример — современный английский, в котором множество древнеанглийских слов вытеснены др.-нормандскими словами латинского происхождения), либо под влиянием торговли и «культурного обмена» (характерно для русского языка). Римско-греческий мир к моменту великого переселения народов достиг высокого уровня материальной культуры, что, естественно, должно было способствовать распространению слов даже к народам, никогда не входившим в Римскую империю. Примеры таких слов я уже описывал.

Итак, как называлась игла в латинском языке? Acus. Слово, происходящее от того же корня, что и русские «острый, оселок». Маленкая игла — «иголка», по-латински «acula». Пора вспомнить др.-прусское слово аусulо или aīkula. Если предположить заимствование из латыни и др.-прусского и славянского слова, то надо ответить на вопрос о начальном ai-, i- (переход k > g между гласными, в общем-то, даже сам по себе вполне вероятен для заимствованного слова). Очевидно, источником послужила не классическая латынь, а некоторый вариант народной латыни. И тут имеем раздолье: др.-фр. aiguille, нормандск. aigùule выглядят наиболее интересно. Непосредственным источником мог послужить какой-то вымерший романский диалект, например, паннонский.

Теперь о латинском rota. Данный корень для обозначения колеса или вращения присутствует в ряде ИЕ языков, причём, порой наряду с другим корнем *kʷel-. Я когда-то где-то видел версию, что это связано с инновацией: изобретением колеса со спицами. Т.е. «коло» — колесо, сбитое из досок для медленной воловьей повозки, «рата» — колесо со спицами для быстрой конной колесницы. Отсюда выводилась потенциальная связь со словами «рать» и «ратище/ратовище» — древко копья (или также и спица колеса?). Впрочем, как минимум со времён Фасмера принято выводить «ратище» из «рати», а «рать» — от совсем другого корня *h₃ér-, вероятно, означающего «враждовать».

Интересно, что изобретателями колесницы могли быть даже не древние арии («индо-иранцы»), а ещё ранее отделившиеся от индоевропейского массива «тохары«, дошедшие на восток до Китая и, возможно, принёсшие в древнекитайский язык «kla» — «колесница» (а вовсе не rot-). Насчёт же корня *(H)ret-/(H)rot- и его отсутствия в славянских у меня есть своя версия, причём очень простая. Мы можем видеть здесь результат метатезы e-r: *wer-t- > *wret- > *ret. Позиция *w перед r во многих языках делает w немой. В пользу данной версии говорит др.-перс. производное uraθa-, где w- ещё сохранялось. В славянском имеем исходный *wert-/wort- («вертеть», «ворочать», «ворота» и т.д.).

Чтение файла в строку

Иногда бывает нужно прочитать всё содержимое потока ввода или файла в строку. В C++ это можно сделать по-разному. Для начала рассмотрим ситуацию произвольного потока ввода, размер данных в котором нельзя определить заранее стандартными средствами.

Я написал три функции, выполняющие чтение.

Вариант 1 наиболее краткий и элегантный — использовать итератор чтения из буфера потока:

string read_file_v1(istream & is)
{
  return string(istreambuf_iterator<char>{is}, {});
}

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

Вариант 2 через вывод буфера потока в строковый поток:

string read_file_v2(istream & is)
{
  stringstream buf;
  buf << is.rdbuf();
  return buf.str();
}

Недостатком данной реализации является, по крайней мере, тот факт, что строку нельзя «забрать» из строкового потока, можно только скопировать его содержимое в новую строку. Это значит, что если файл большой, то потребуется не менее, чем двукратный объём памяти. В худшем случае можно ожидать трёхкратный объём, так как хранилище строкового потока увеличивается в геометрической прогрессии (аналогично поведению vector::push_back).

Вариант 3 через чтение в список блоков памяти. Самый сложный код:

string read_file_v3(istream & is)
{
  constexpr streamsize BUF_SZ = 65536 - 4*sizeof(void*);
  list<array<char, BUF_SZ>> buffers;
  streamsize last_read_size = 0, total = 0;

  do
  {
    buffers.emplace_back();
    // Здесь хорошо подошла бы функция readsome,
    // но она может вообще ничего не прочитать!
    last_read_size = 
      is.read(buffers.back().data(), BUF_SZ)? 
                         BUF_SZ: is.gcount();
    total += last_read_size;
  } while (last_read_size == BUF_SZ);

  string result;
  if (total > 0)
  {
    result.resize(total);
    auto dest = result.data();
    {
      auto last = buffers.back().data();
      copy_n(last, last_read_size, 
        dest + (total - last_read_size));
      buffers.pop_back();
    }

    for (auto & block: buffers)
    {
      auto from = block.data();
      copy_n(from, BUF_SZ, dest);
      dest += BUF_SZ;
    }
  }

  return result;
}

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

Я не знаю практичного способа избежать перерасхода памяти при чтении неизвестного объёма данных из абстрактного потока ввода. Однако, если требуется прочитать файл, то можно узнать его размер заранее и выделить место в строке. До C++17 для этого обычно пользовались tellg — открыть файл, установив курсор чтения в конец (ios::ate), прочитать текущую позицию курсора. К сожалению, данный способ не обязан работать корректно: по стандарту tellg вполне может вернуть -1. В C++17 стандартная библиотека пополнилась библиотекой filesystem, в которой есть функция file_size. (Эта библиотека происходит из Boost, поэтому можно использовать Boost, если стандартная версия недоступна.)

Boost-версия (использовавшаяся мною в тесте, «вариант 4»):

string read_file_by_name(char const * fn)
{
  namespace fs = boost::filesystem;
  string result;
  if (auto const sz = fs::file_size(fn))
  {
    result.resize(sz);
    ifstream f(fn, ios::binary);
    f.read(result.data(), sz);
  }
  return result;
}

При использовании стандартной библиотеки, наверно, лучше написать несколько иначе:

namespace fs = std::filesystem;
string read_file_by_name(fs::path const & fn)
{
  string result;
  if (auto const sz = fs::file_size(fn))
  {
    result.resize(sz);
    ifstream f(fn, ios::binary);
    f.read(result.data(), sz);
  }
  return result;
}

Обратите внимание на флаг ios::binary. В общем случае его желательно ставить, если надо получать файл «как есть» байт-в-байт. Если у вас возникают непонятные проблемы при чтении файлов, попробуйте установить флаг binary.

К сожалению, стандартная библиотека не содержит средств отображения файлов в память. Использование таких средств, возможно, является наиболее эффективным способом чтения файлов в настоящее время.

Итак, теперь результаты замеров (секунды, g++ 8.2, Windows 7 x64, HDD, файл размером 1.1Gb, взят минимум из пяти прогонов):

№ вар. -O0, sync -O3, sync -O3
1 142.9 19.72 19.70
2 15.63 15.49 15.45
3 2.359 2.316 2.313
4 1.333 1.324 1.323

Как видно, от включения оптимизации значимо выигрывает лишь первый, самый медленный (ужасно медленный, при выключенной оптимизации) вариант. В случае остальных разницу между «оптимизированным» и «неоптимизированным» надо искать с лупой. Слово sync означает работу по умолчанию — синхронизация с вводом-выводом в режиме C не была выключена. В последнем столбце даны результаты для случая, когда перед тестом была выполнена строчка, выключающая данную синхронизацию:

ios::sync_with_stdio(false);

Следует отметить, что гигабайт с жёсткого диска нельзя «честно» считать за 1-2 секунды. В данном случае, очевидно, файл был закэширован операционной системой. Но для нашего теста так даже лучше.

Проверка попадания точки в симплекс

Предположим, есть d точек \{a_i\}_1^d в пространстве \mathbb R^{d-1}.
Требуется проверить, принадлежит ли произвольное p \in \mathbb R^{d-1} выпуклой оболочке \{a_i\}_1^d.

Для простоты предположим, что объём \mathrm{co}\,\{a_i\}_1^d не равен нулю, тогда это симплекс, вершинами которого выступают \{a_i\}_1^d. Возможное технически простое решение данной задачи подсказывает теорема Каратеодори о выпуклой оболочке. В соответствии с этой теоремой, если p \in \mathrm{co}\,\{a_i\}_1^d, то p можно представить в виде выпуклой линейной комбинации: p = \sum_{i=1}^d{c_i a_i}, где \{c_i\}_1^d есть некоторый набор неотрицательных чисел такой, что \sum_{i=1}^d{c_i} = 1.

Теперь исходную задачу можно представить в виде задачи решения системы линейных уравнений:

\begin{bmatrix}  a_{11} & a_{21} & \cdots & a_{d1} \\  \vdots & \vdots & \cdots & \vdots \\  a_{1,d-1} & a_{2,d-1} & \cdots & a_{d,d-1} \\  1 & 1 & \cdots & 1  \end{bmatrix}  \begin{bmatrix}  c_1 \\ \vdots \\ c_{d-1} \\ c_d  \end{bmatrix} =  \begin{bmatrix}  p_1 \\ \vdots \\ p_{d-1} \\ 1  \end{bmatrix}.

Решив данную систему относительно \{c_i\}_1^d, можно проверить, что все они неотрицательные. Если это так, то точка p лежит в \mathrm{co}\,\{a_i\}_1^d.

Также можно заметить, что если c_i = 0, то p лежит на грани симплекса, противолежащей вершине a_i.
Если c_i < 0, то p лежит в наружном полупространстве, находящемся за этой гранью.
Если же все c_i > 0, то p лежит во внутренности симплекса.

Групповая операция на основе операции возведения в степень

Недавно наткнулся на пусть очевидный в общем-то при ближайшем рассмотрении, но всё же интересный факт:

(\forall a\in R)(\forall b\in R)\ a^{\ln{b}} = b^{\ln{a}},
R = \{\,x\in\mathbb R\mid x>0 \land x\neq 1\,\} = \mathbb R_+\setminus\{1\}.

Коммутативность данной операции

a\ast b\colon R\times R \to a^{\ln{b}}\colon R

очевидна ввиду тождества

a^{\ln{b}} \equiv \exp(\ln{a}\ln{b})

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

Нейтральный элемент e = \exp 1 (можно ввести аналоги для других оснований):

a\ast e = e\ast a = \exp{\ln{a}} = a.

Обратный элемент для некоторого a также получить не трудно:

a\ast b = e \Leftrightarrow b = \exp\dfrac{1}{\ln b} = e\ast \log_b{e}.

Обычная единица может играть роль нуля кольца (не имеет обратного элемента, аналогом сложения тогда выступает умножение, легко показать дистрибутивность) и при подстановке 1 в определение операции получаем:

1\ast a = a\ast 1 = 1.

Вообще, вся конструкция (\mathbb R_+, \cdot, \ast) образует поле.

Об использовании Visual Studio Code для учебных примеров

Visual Studio Code — редактор на основе платформы Electron, который можно использовать как минималистичную IDE. Мне требовалась поддержка C++17 и переносимость всего «на флешке». Что меня приятно удивило, так это «шустрость» VSCode.

Итак, порядок действий, предпринятых мной был таков:

  1. Скачать VSCode в архиве (в моём случае это была версия 1.27.1 для Windows/x64). Распаковать его, допустим, в папку vscode. Внимание! Путь к vscode не должен содержать не-ASCII символы и пробелы.
  2. Создать пустую папку vscode/data. Там будут плагины и общие настройки. При обновлении VSCode можно просто распаковать новую версию и переместить туда свою папку data из старой.
  3. Распаковать сборку MinGW рядом с vscode, допустим, в папку mingw (mingw/bin содержит g++.exe). В качестве таковой я брал сборку отсюда, там уже есть Boost и ряд других библиотек. Я к ним ещё добавляю Eigen и кое-что своё. Добавляю, просто складывая соответствующие папки в mingw/include.
  4. Создать рядом с vscode пустую папку для примеров. Допустим, cpp.
  5. Запустить VSCode (vscode/code.exe) и установить плагин C/C++ for Visual Studio Code от Microsoft (с Microsoft Intellisense).
  6. Открыть в VSCode папку cpp.
  7. Настройки создаются в виде JSON-файлов в папке cpp/.vscode. Ниже я опишу возможное их содержимое. Их можно создать непосредственно в VSCode, заполнить в нём же, и затем перезапустить VSCode.
  8. После того, как файлы настроек созданы, и VSCode перезапущен, следует протестировать его. Создать cpp/test.cpp с произвольным содержимым на C++ (например, helloworld). Terminal/Run build task… или Ctrl+Shift+B должно запускать сборку и завершаться без ошибок. F5 запускает сборку и результат в отладчике (gdb). Заголовочные файлы должны успешно открываться (правой кнопкой мыши и Go to definition). Intellisense должен работать адекватно.
  9. Полученный «пакет» в составе vscode, mingw, cpp можно упаковать в архив и развернуть на другой системе или просто скопировать на внешний носитель и запускать с него.

Итак, файлы настроек.

Плагин C/C++ использует файл c_cpp_properties.json.
Его содержимое в моём случае:

{
    "configurations": [
        {
            "name": "MinGW",
            "intelliSenseMode": "gcc-x64",
            "compilerPath": "${workspaceFolder}\\..\\mingw\\bin\\g++.exe",
            "cppStandard": "c++17",
            "cStandard": "c11",
            "includePath": [
                "${workspaceFolder}",
                "${workspaceFolder}\\..\\mingw\\include"
            ],
            "defines": [
                "__cplusplus=201703L"
            ]
        }
    ],
    "version": 4
}

Строго говоря, дефайн стандартного макроса __cplusplus, может, и не понадобится, просто у меня в начале без него плагин не видел правильное содержимое стандартных заголовков.

Для сборки требуется создать «задачу сборки». В простейшем случае это компиляция одной единицы трансляции (cpp-файла) сразу в исполняемый файл (в моём случае всегда один и тот же с названием lab.exe).
Описание задач сборки располагается в файле tasks.json. Его содержимое в моём случае:

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
        {
            "label": "build lab",
            "type": "shell",
            "command": "${workspaceFolder}\\..\\mingw\\bin\\g++",
            "args": [
                "-g", "-Og", // "debug" build
                //"-O3",
                "${file}", 
                "-march=native", "-Wall", "-pedantic",
                "-std=c++17",
                "-olab.exe"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

Наконец, описание запуска отладчика по F5 располагается в launch.json.
Его содержимое в моём случае:

{
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(gdb) Launch",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}\\lab.exe",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": true,
            "MIMode": "gdb",
            "miDebuggerPath": "${workspaceFolder}\\..\\mingw\\bin\\gdb.exe",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                },
                {
                    "description": "Enable break on exception for gdb",
                    "text": "catch throw",
                    "ignoreFailures": true              
                }
            ],
            "preLaunchTask": "build lab"
        }
    ]
}

Вторая команда catch throw активирует перехват исключений отладчиком gdb.
Вообще, к сожалению, я не могу сказать, что с отладкой всё хорошо: есть ряд странностей. Например, точка останова, поставленная в одном месте, может сработать ниже (как будто поставленная в другом месте — может быть, это можно исправить, если заменить -Og на -O0). Точку останова нельзя поставить внутри шаблона (не срабатывает вообще). Не даёт ставить новые точки останова во время отладки. Если во время отладки нажать паузу, то продолжение может не срабатывать (останется только остановить исполнение).

Для меня проблемы с отладчиком не являются критичными, так как я привык к отладке через проверку условий и протоколирование. Но тем, кто привык к отладчику в «нормальной» Visual Studio такое, конечно, будет не по нраву.

UPD. Если всё это запускать на Windows 10, то в качестве терминала может быть по умолчанию выбран PowerShell. Почему-то он «не понимает» относительные пути через .. и не может запустить компилятор. В этом случае рекомендуется заменить его на cmd.exe (в VSCode можно выбрать терминал).

UPD2. Замена флага оптимизации -Og на -O0 всё же помогает отладчику, по крайней мере, точки останова не «убегают» с тех мест, куда они были поставлены.

Граница Парето в 2D: STL-версия

Почти пять лет назад я описал алгоритм вычисления границы Парето множества точек на плоскости.

С тех пор я использовал данную задачу как задачу по программированию на первом курсе (на алгоритмы STL). Всё дело в том, что этот алгоритм очень просто записывается с помощью STL. Требуется применить два алгоритма (sort и unique) и адаптер компаратора (not_fn или самописный, например, переставляющий аргументы местами). Бывают простенькие задачи, к которым невозможно адекватно применить STL без написания своих компонент, а бывает и наоборот. Итак, код.

#include <algorithm>
#include <functional>

template 
  <
    class RanIt, 
    class Comp1, 
    class Comp2
  >
RanIt remove_dominated
  (
    RanIt from,
    RanIt to,
    Comp1 compare1,
    Comp2 compare2
  )
{
  std::sort(from, to, std::not_fn(compare1));
  return std::unique(from, to, std::not_fn(compare2));
}

////////////////////////////
#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool test_remove_dominated()
{
  vector<string> input
  {
    "look",
    "after",
    "the",
    "raven",
    "star"
  };
  
  input.erase(
    remove_dominated(
      input.begin(), input.end(),
      std::less<>{},
      [](auto & a, auto & b)
      {
        return a.size() < b.size();
      }),
    input.end()
    );
    
  sort(input.begin(), input.end());
  return input == vector<string>
    {
      "raven",
      "star",
      "the"
    };
}

int main()
{
  cout << test_remove_dominated() << '\n';
  return 0;
}

В примере два критерия сравнения строк: лексикографический и по длине. Так «raven» доминирует «look» (и лексикографически, и по длине), но не «star».

О задаче разложения числа в сумму

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

Дано: x \in \mathbb R, n \in \mathbb N, \{\underline{x}_i\}_{i=1}^n \subset \mathbb R, \{\overline{x}_i\}_{i=1}^n \subset \mathbb R, \forall i \in \overline{1,n}\, (\underline{x}_i \leqslant \overline{x}_i).

Найти \{x_i\}_{i=1}^n такие, что \sum_{i=1}^n{x_i} = x и \forall i \in \overline{1,n}\, (\underline{x}_i \leqslant x_i \leqslant \overline{x}_i), или определить, что таких x_i не существует.

Задача легко решается, если догадаться сделать замену переменных:

y_i = x_i - \underline{x}_i, \quad \overline{y}_i = \overline{x}_i - \underline{x}_i.

y = \sum\limits_{i=1}^n{y_i} = \sum\limits_{i=1}^n{(x_i - \underline{x}_i)} = x - \sum\limits_{i=1}^n{\underline{x}_i}.

Она позволяет перейти к более простой постановке:

Дано: y \in \mathbb R, n \in \mathbb N, \{\overline{y}_i\}_{i=1}^n \subset \mathbb R, \forall i \in \overline{1,n}\, (0 \leqslant \overline{y}_i).

Найти \{y_i\}_{i=1}^n такие, что \sum_{i=1}^n{y_i} = y и \forall i \in \overline{1,n}\, (0 \leqslant y_i \leqslant \overline{y}_i), или определить, что таких y_i не существует.

Сразу видно, что решение существует тогда и только тогда, когда 0 \leqslant y \leqslant \sum_{i=1}^n{\overline{y}_i} и получить его можно простым линейным жадным алгоритмом, вычитая из y на каждом шаге максимально возможный очередной недостаток y_i = \min\{\,y - \sum_{j=1}^{i-1}{y_j}, \overline{y}_i\,\} (естественно, y_1 = \min\{\,y, \overline{y}_1\}).
Если мы быстро исчерпаем y, то последние y_i могут быть просто нулями.

Приведу код решения данной задачи на C++ (аж с ноября не публиковал здесь кода C++!).

#include <cassert>
#include <iterator>
#include <algorithm>
/**
 * @brief Decompose a number into a sum of non-negative terms.
 * @param value the value to be decomposed
 * @param ubound non-negative upper bounds for decomposition terms
 * @param decomp decomposition terms, of the same size as ubound!
 * @return success (whether a decomposition exists)
 */
template 
  <
    class NT,       // number type
    class NTArrayU, // number type array for ubound
    class NTArrayD  // number type array for decomp
  >
bool scalar_sum_decompose
  (
    NT               value,
    NTArrayU const & ubound,
    NTArrayD       & decomp
  )
{
  if (value < NT{})
    return false;
  
  using std::size;
  auto const n = size(ubound);
  assert(n == size(decomp));
  
  NT s {}; // accumulated sum.
  for (auto i = n-n; i < n; ++i)
  {
    assert(!(ubound[i] < NT{}));
    NT const term = std::min<NT>(value - s, ubound[i]);
    decomp[i] = term;
    value -= term;
  }
  
  return value == NT{};
}

(Код «auto i = n-n» есть маленький костыль ввиду нежелания городить извлечение типа размера.)
Теперь несложно написать и обёртку, решающую первую задачу.

#include <vector>
#include <numeric>
#include <functional>
/**
 * @brief Decompose a number into a sum of bounded terms.
 * @param value the value to be decomposed
 * @param lbound lower bounds for decomposition terms
 * @param ubound upper bounds for decomposition terms
 * @param decomp decomposition terms, it must have the same size as ubound and lbound!
 * @return success (whether a decomposition exists)
 */
template 
  <
    class NT,       // number type
    class NTArrayL, // number type array for lbound
    class NTArrayU, // number type array for ubound
    class NTArrayD  // number type array for decomp
  >
bool scalar_sum_decompose
  (
    NT               value,
    NTArrayL const & lbound,
    NTArrayU const & ubound,
    NTArrayD       & decomp
  )
{
  using std::size;
  auto const n = size(ubound);
  assert(size(lbound) == n && size(decomp) == n);
  
  using std::begin;
  using std::end;
  std::transform(
    begin(ubound), end(ubound), begin(lbound),
    begin(decomp), std::minus<>{});
  NT const lsum = std::accumulate(
    begin(lbound), end(lbound), NT{});
  std::vector<NT> buffer(n);
  if (!scalar_sum_decompose(value - lsum, decomp, buffer))
    return false;
  std::transform(
    begin(buffer), end(buffer), begin(lbound),
    begin(decomp), std::plus<>{});
  return true;
}

Вспомогательный буфер возник из-за запрета алиасинга итераторов в transform. Конечно, можно написать без transform и без буфера. И вообще одной функцией. Из-за вычисления сумм и разностей в плавающей точке теоретически могут возникнуть неприятности.

Имя/enmen

Прокрастинация основной деятельности вызвала у меня нижеследующий поток лингвистического дилетантизма.

Начнём с предлога в : в < въ < *vъn/*vьn (-n сохранено в некоторых производных: внутрь = вн-утрь (ср. утроба), вниди = вн-иди; протетическая в- как в вострый, вогнь, восемь) < *en < *h₁én (см. там также другие производные).

Сюда, может быть, также вон (вънъ), вне (вънѣ) (у Фасмера по-другому).
Последняя ассоциация у меня возникла через другую ассоциацию с местоимением он < *h₁ónos («тот, удалённый от меня и от тебя»; «некий», «какой-то»). Ещё варианты этого местоимения по ссылке: *h₁énos (*h₁én-o-s?), *h₁nós.

О, эта последняя форма прекрасна. Она мне сразу напомнила слово *h₁nómn̥ «имя» (см. также спор в обсуждении о возможном корне этого слова).

Обычно предполагается, что *-mn̥ (-men) — суффикс отглагольного существительного, тогда *h₁nó-mn̥ должно быть производным некоего глагола со значением «давать имя» или «звать», ср. прозвище от прозвать. Думаю, можно найти множество подобных примеров в существующих языках. Попытка истолковать данное слово на индоевропейской почве отягощается сравнением с материалом других языковых семей, например, с прауральским *nime «имя».

Балтослав. реконструкция *inˀmen может быть объяснена влиянием форм косвенных падежей (форм вроде *h₁n̥mén, см. таблицу склонения по ссылке выше). Действительно, примеры похожих замен имеются: например, слова язык и земля (впрочем, это, по сути, упрощения исходных сложных слов).

Ввиду древнепрусского emmens ЭССЯ (т.8, с.228) предлагает понимать «имя» как *en-men «влагаемое» > «имя» и считает его параллельным образованию *ano-men «возлагаемое» > «имя». Наличие различных (но похожих) параллельных образований объясняет невозможность единой непротиворечивой реконструкции. Уральские формы там объяснены как ИЕ заимствование (это утверждение не будет таким уж сильным, если принять возможную датировку позднего прауральского языка 4000 лет назад).

Можно потеоретизировать, что форма *h₁nós даёт возможность некоего подобного толкования, но уже на основе указательного местоимения. Вообще, наверно, не будет ошибкой считать указательные местоимения наиболее примитивной частью речи. И как таковые, они могли служить на некоем древнем этапе базисом для других слов, например, для предлогов направления («в» и «на»).

Наконец, интересно сходство слав. имя с глаголом иметь (атематический ять < *imtei < *h₁em-). Это можно было бы назвать случайностью, но последний корень сравнивают с корнем *nem-, имеющим аналогичное значение. Отглагольное производное с корнем *nem/nom могло бы значить «данное (имя)».

Чё и что

В современном русском языке слово чё считается просторечным вариантом что. Тем не менее, оно является прямым продолжением индоевропейского вопросительного слова. Для пояснения приведу таблицу изменений по этапам (включая также местоимения 3л.).

Этап что кто он, оно, она
ПИЕ *kʷid *kʷos *éy, *Hyós, *Hyéh₂
сатемизация *kid *kos *ey, *yos, *ya
славизация *kь *kъ *jь, *je, *ja
первая палатализация *чь *къ (ѥго), (ѥго), (ѥѩ)
падение еров че **ко (им.п. заменён)

Последний исторический этап: переход подударного е в ё в русском языке (к XVIII веку?).

Видимо, из-за того, что формы именительного падежа стали в процессе изменения слишком короткими и омонимичными (например, къ — предлог, и — союз), они были заменены, соответственно, на что (чьто, чь+то), кто (къто, къ+то), он, оно, она.

Другие составные местоимения: чей (чь+и), кой (къ+и), где (къ+дѣ/де), когда (возможно, *кого года, т.е. в какое время) и т.д. Комбинирование местоимений в славянском дало комбинаторный взрыв числа их вариантов, из которых в современных языках закрепились не все (порой, разные слова для одинаковых значений).