Реши на C++: Пока папа был на работе, маленькая де...

Ниже приведён один из возможных вариантов решения на C++. Идея следующая:

1. Представление трёхбуквенных подстрок в виде рёбер графа
   Каждую трёхбуквенную подстроку вида $\text{XYZ}$ можно интерпретировать как направленное ребро из вершины $\text{XY}$ в вершину $\text{YZ}$.

   • «Вершины» в таком графе — это все возможные пары символов (букв и цифр).
   • «Рёбра» — это все трёхбуквенные фрагменты, которые у нас даны.

2. Условия существования Эйлерова пути
   Нам нужен путь, проходящий по каждому ребру ровно один раз (Эйлеров путь). Для ориентированного графа условие существования Эйлерова пути такое:

   • Граф должен быть связным, если рассматривать его как неориентированный (после удаления «висячих» вершин, у которых нет рёбер, конечно).
   • Либо все вершины имеют одинаковую полустепень захода и выхода (в этом случае существует Эйлеров цикл),
     либо ровно две вершины отличаются на 1:
     • у одной вершины $\text{outdegree} = \text{indegree} + 1$ (начало пути),
     • у другой $\text{indegree} = \text{outdegree} + 1$ (конец пути).
       У всех остальных вершин должно быть $\text{indegree} = \text{outdegree}$.

3. Построение ответа
   Если подходящий Эйлеров путь найден (или цикл), то, двигаясь по нему, мы восстанавливаем строку:

   • Пусть первая вершина пути — это пара символов (например, AB), мы сразу добавляем A и B в итоговую строку.
   • Каждый следующий шаг даёт новую вершину вида BC, и мы добавляем только последний символ C.
   • Всего будет $n$ рёбер и $n+1$ вершин на пути, что даёт $n+2$ символа в искомой строке.

4. Реализация

   • Считаем все трёхбуквенные подстроки, строим граф (сохраняем рёбра в списках смежности, учитывая возможные повторения).
   • Проверяем связность (если игнорировать направление рёбер) для подграфа, задействованного в рёбрах.
   • Проверяем условия на полустепени захода/выхода.
   • Находим подходящую стартовую вершину (если есть одна вершина, у которой outdegree = indegree + 1, то начинаем с неё, иначе — с любой вершины, у которой outdegree > 0, когда все indegree = outdegree).
   • Выполняем стандартный алгоритм обхода (Hierholzer’s algorithm), получаем Эйлеров путь (или цикл).
   • Восстанавливаем строку из пути по описанной выше схеме.
   • Если что-то не сходится — выводим NO.

Ниже — полный код на C++. Комментарии внутри помогут разобраться в деталях.

cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Маппинг символов (общее количество 62 разных символа):
    '0'..'9'  ->  0..9
    'A'..'Z'  -> 10..35
    'a'..'z'  -> 36..61
  Пары символов (x, y) можно сводить к индексу pairIndex = x * 62 + y
  где x, y &isin; [0..61].
*/

static const int ALPH_SIZE = 62;

// Функция, которая переводит символ c в число от 0 до 61
int charToIndex(char c) {
    if ('0' <= c && c <= '9') {
        return c - '0';
    } else if ('A' <= c && c <= 'Z') {
        return c - 'A' + 10;
    } else {
        return c - 'a' + 36;
    }
}

// Функция, которая возвращает char, соответствующий индексу [0..61]
char indexToChar(int idx) {
    if (idx < 10) {
        return char('0' + idx);
    } else if (idx < 36) {
        return char('A' + (idx - 10));
    } else {
        return char('a' + (idx - 36));
    }
}

// Утилита для вычисления индекса пары (x, y)
int pairToIndex(int x, int y) {
    return x * ALPH_SIZE + y;
}

// Восстановим x, y из индекса пары pairIndex
pair<int,int> indexToPair(int p) {
    int x = p / ALPH_SIZE;
    int y = p % ALPH_SIZE;
    return {x, y};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    // Нам дано n трехбуквенных строк -> строка должна быть длины (n+2).

    // Для хранения графа:
    // inDeg[v] = сколько ребер заходит в вершину v
    // outDeg[v] = сколько ребер выходит из вершины v
    // adj[v] = список (стек) рёбер (вершин) куда можно пойти из v
    vector<long long> inDeg(ALPH_SIZE*ALPH_SIZE, 0),
                      outDeg(ALPH_SIZE*ALPH_SIZE, 0);
    // Храним списки смежности, причём каждый элемент - индекс вершины назначения
    // Вершины у нас - это пары (2 символа).
    vector<vector<int>> adj(ALPH_SIZE*ALPH_SIZE);

    // Считаем все 3-буквенные подстроки
    // И параллельно формируем граф
    vector<string> triples(n);
    for(int i = 0; i < n; i++){
        cin >> triples[i];
    }

    // Чтобы потом выбрать старт для связности, запомним вершины, в которых outDeg+inDeg>0.
    // Сначала преобразуем все строки в рёбра.
    // У нас ребро: XY -> YZ, где XYZ - данная трёхбуквенная подстрока
    // X, Y, Z - это символы. 
    // Индекс вершины1 = (X,Y), вершины2 = (Y,Z).
    auto getPairIndex = [&](char c1, char c2){
        return pairToIndex(charToIndex(c1), charToIndex(c2));
    };

    // Заполняем граф
    for (auto &s : triples) {
        int v1 = getPairIndex(s[0], s[1]);
        int v2 = getPairIndex(s[1], s[2]);
        adj[v1].push_back(v2);
        outDeg[v1]++;
        inDeg[v2]++;
    }

    // --- 1) Проверка связности (по ребрам) ---
    // Найдем любую вершину, которая участвует в графе (outDeg+inDeg > 0), 
    // и сделаем DFS/BFS в неориентированном смысле. Убедимся, что все вершины,
    // которые имеют (outDeg+inDeg) > 0, достижимы.

    // Ищем стартовую вершину для проверки связности
    int startVertex = -1;
    for (int i = 0; i < (int)adj.size(); i++){
        if (inDeg[i] + outDeg[i] > 0){
            startVertex = i;
            break;
        }
    }

    if (startVertex == -1) {
        // Нет ни одного ребра и вершины -> n=0, но по условию n>=1, значит противоречие.
        // Теоретически при n=1 мог бы быть случай, но если n=1,
        // тогда у нас ровно одна 3-буквенная подстрока, она всегда образует валидную строку длины 3.
        // Но раз мы сюда попали, что-то не так.
        cout << "NO\n";
        return 0;
    }

    // Делаем DFS в неориентированном смысле
    vector<bool> used(ALPH_SIZE*ALPH_SIZE, false);

    // Для удобства соберём "неориентированный" список смежности
    vector<vector<int>> undirected(ALPH_SIZE*ALPH_SIZE);
    for (int v = 0; v < (int)adj.size(); v++){
        // Добавляем ребра v->u и u->v (по outEdges)
        for (int u : adj[v]) {
            undirected[v].push_back(u);
            undirected[u].push_back(v);
        }
    }

    // Запускаем DFS
    stack<int> st;
    st.push(startVertex);
    used[startVertex] = true;
    while(!st.empty()){
        int v = st.top(); st.pop();
        for(auto &u : undirected[v]){
            if(!used[u]){
                used[u] = true;
                st.push(u);
            }
        }
    }

    // Теперь проверяем, все ли вершины, которые реально участвуют (inDeg+outDeg>0),
    // помечены used[v] = true.
    for(int v = 0; v < (int)adj.size(); v++){
        if(inDeg[v] + outDeg[v] > 0 && !used[v]){
            // Нашли несвязную вершину
            cout << "NO\n";
            return 0;
        }
    }

    // --- 2) Проверка условия на полустепени (Euler path) ---
    // Считаем, сколько вершин имеют outDeg-inDeg = 1, inDeg-outDeg = 1, и т.п.
    int startCount = 0, endCount = 0;
    for (int v = 0; v < (int)adj.size(); v++){
        long long diff = outDeg[v] - inDeg[v];
        if (diff == 1) startCount++;
        else if (diff == -1) endCount++;
        else if (diff != 0) {
            cout << "NO\n";
            return 0;
        }
    }

    if(!((startCount == 1 && endCount == 1) || (startCount == 0 && endCount == 0))) {
        cout << "NO\n";
        return 0;
    }

    // --- 3) Поиск стартовой вершины для Эйлерова пути ---
    // Если есть вершина с outDeg = inDeg + 1, начинаем от неё,
    // иначе начинаем от любой вершины, у которой outDeg > 0.
    int startNode = -1;
    for (int v = 0; v < (int)adj.size(); v++){
        if ((long long)outDeg[v] - (long long)inDeg[v] == 1) {
            startNode = v;
            break;
        }
    }
    if (startNode == -1) {
        // тогда ищем любую вершину, откуда есть рёбра
        for (int v = 0; v < (int)adj.size(); v++){
            if (outDeg[v] > 0){
                startNode = v;
                break;
            }
        }
    }

    // --- 4) Эйлеров путь (Hierholzer’s algorithm) ---
    // В стеке будем хранить вершины текущего пути,
    // а в пути (vector<int> eulerPath) — построенный результат.
    vector<int> eulerPath;  
    // Используем собственный стек для обхода
    stack<int> stackPath;
    // Чтобы итеративно доставать "последнее" ребро, удобно хранить итераторы...
    // Но можно просто хранить индекс следующего ребра, который мы ещё не посещали:
    vector<int> idxNext(adj.size(), 0);

    stackPath.push(startNode);
    while(!stackPath.empty()){
        int v = stackPath.top();
        // Если у нас есть ещё не использованные рёбра из v
        if (idxNext[v] < (int)adj[v].size()){
            int u = adj[v][idxNext[v]++];
            stackPath.push(u);
        } else {
            // Рёбер больше нет, эта вершина — конец цепочки из v
            stackPath.pop();
            eulerPath.push_back(v);
        }
    }
    // eulerPath хранит путь в обратном порядке, 
    // но нам это не критично, можно потом развернуть.
    reverse(eulerPath.begin(), eulerPath.end());
    // Длина eulerPath должна быть (n + 1), потому что рёбер n, а вершин в пути n+1.

    if ((int)eulerPath.size() != n+1){
        // Значит что-то пошло не так
        cout << "NO\n";
        return 0;
    }

    // --- 5) Восстановим итоговую строку длины (n+2) ---
    // Первая вершина eulerPath[0] — это пара (x0, y0). Выводим символы x0, y0.
    // Далее при переходе на вершину eulerPath[i] = (xi, yi) добавляем yi.
    // Т.к. вершины — пары, нужно сначала их раскодировать в отдельные символы.
    auto decodePair = [&](int p) {
        auto pp = indexToPair(p);
        return make_pair(pp.first, pp.second); // (x, y)
    };

    // Переведём eulerPath в последовательность символов
    // Берём первые 2 символа из eulerPath[0], потом добавляем по 1 символу из каждой следующей вершины.
    string answer;
    {
        auto [x0, y0] = decodePair(eulerPath[0]);
        answer.push_back(indexToChar(x0));
        answer.push_back(indexToChar(y0));
        for (int i = 1; i < (int)eulerPath.size(); i++){
            auto [x_i, y_i] = decodePair(eulerPath[i]);
            // eulerPath[i] = (x_i, y_i), это следующая пара. 
            // Совпадает y0 из предыдущей пары с x_i новой пары, 
            // поэтому добавляем только y_i:
            answer.push_back(indexToChar(y_i));
        }
    }

    // Проверим, что длина действительно n+2
    if ((int)answer.size() != n+2) {
        cout << "NO\n";
        return 0;
    }

    // Если дошли сюда — всё хорошо
    cout << "YES\n";
    cout << answer << "\n";

    return 0;
}

Краткие пояснения к коду

1. Маппинг символов

   • Функции charToIndex и indexToChar переводят символ в число от 0 до 61 и обратно.
   • Пары символов сводим к индексу от 0 до $62 \cdot 62 - 1$.

2. Построение графа

   • Каждая трёхбуквенная строка XYZ даёт ребро из вершины (X,Y) в вершину (Y,Z).
   • Храним это в adj[v], где v — индекс пары (X,Y).

3. Проверка связности

   • Переходим к «неориентированному» виду, чтобы убедиться, что все вершины, которые реально задействованы (у которых $\text{inDeg}[v] + \text{outDeg}[v] > 0$), лежат в одной компоненте связности.

4. Проверка на существование Эйлерова пути

   • Считаем $\text{outDeg}[v] - \text{inDeg}[v]$. Возможны варианты:
     • 0 для большинства вершин (Эйлеров цикл)
     • У ровно одной вершины +1 и у ровно одной -1 (Эйлеров путь)
     • Остальным обязательно 0.

5. Поиск Эйлерова пути (Hierholzer’s algorithm)

   • Ищем стартовую вершину: та, где $\text{outDeg} = \text{inDeg} + 1$, если такая есть. Иначе берём любую с $\text{outDeg} > 0$.
   • Строим путь, пока не используем все рёбра.

6. Сбор итоговой строки

   • Имея последовательность вершин $v_0, v_1, \ldots, v_n$ (всего $n+1$ штук), каждая вершина — это пара символов.
   • Склеиваем первый символ пары $v_0$, второй символ пары $v_0$, а затем только второй символ каждой следующей пары.
   • Получается строка из $n+2$ символов.

Если всё получилось, выводим:

text
YES
<восстановленная_строка>

Иначе — NO.

Проверка на данных из условия:

1. Пример:

   text
   n = 5
   aca
   aba
   aba
   cab
   bac

   Вывод:

   text
   YES
   abacaba

2. Пример:

   text
   n = 4
   abc
   bCb
   cb1
   b13

   Вывод:

   NO
   

3. Пример:

   text
   n = 7
   aaa
   aaa
   aaa
   aaa
   aaa
   aaa
   aaa

   Здесь все тройки: aaa. Очевидно, искомая строка — это 9 букв a: aaaaaaaaa.
   Вывод:

   text
   YES
   aaaaaaaaa

Таким образом, данный алгоритм корректно решает задачу.