Submission #1671007

---

Source Code Expand

// Copyright (C) 2017 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.

#include <bits/stdc++.h>

using namespace std;

// solve problem when a != 0.
string solve(int a, int b, int c) {
    if (b == 0 and c == 0) {
        // it is clear, that answer is 'aaa...'.
        string res = "";
        for (int t = 0; t != a; ++t)
            res += 'a';
        return res;
    }

    // lets build our cyclical string.
    // we have (a) parts equal to 'a', and b + c other parts.
    // clearly, resulting cyclical string has substring of num=ceil(a/(b+c)) symbols 'a'.
    // 
    // if we want to minimize answer, than we shouldn't make it any larger (since it will be start of the minimal cyclical shift)
    // so we will have parts of length num and num-1.
    int num = (a + (b + c - 1)) / (b + c);
    int cnt_short = num * (b + c) - a; // how much parts of "num - 1"

    string tmp = "";
    for (int i = 0; i != num - 1; ++i)
        tmp += 'a';
        
    vector<string> parts;
    for (int i = 0; i != (b + c - cnt_short); ++i)
        parts.push_back(tmp + 'a'); // put long parts of num "a"

    for (int i = 0; i != cnt_short; ++i)
        parts.push_back(tmp); // put short parts of (num - 1) "a".

    // let's distribute B's and C's.
    //
    // We can notice, that minimal cyclical shift will start with num "a"s.
    // So it is always better to put C's to "long" parts, they are conveniently at the beginning of parts
    // array.
    
    for (int i = 0; i != c; ++i)
        parts[i] += 'c';
    for (int i = 0; i != b; ++i)
        parts[c + i] += 'b';

    // Now we want to put all parts together to minimize answer, and we are sure,
    // that the answer will be smaller than possible, if we try to split parts.

    // funny thing: there are no more, than 3 different types of parts, because
    // part uniquely defined by whether it has (num) or (num - 1) A's, and whether it has B or C at the end.
    // but it is not possible for types (num, B) and (num - 1, C) to exist together.

    // so count number of each and call recursion.
    sort(parts.begin(), parts.end());
    vector<string> cparts = parts;
    cparts.resize(std::unique(cparts.begin(), cparts.end()) - cparts.begin());

    while (cparts.size() < 3)
        cparts.push_back("");

    assert(cparts.size() == 3);
    string zzans = solve(std::count(parts.begin(), parts.end(), cparts[0]),
                         std::count(parts.begin(), parts.end(), cparts[1]),
                         std::count(parts.begin(), parts.end(), cparts[2]));

    string ans = "";
    for (char ch: zzans)
        ans += cparts[ch - 'a'];

    return ans;
}

// Time: T(x, y, z) = (x + y + z) + T(a, b, c), where a + b + c = x.
// since X in T(x, y, z) is decreasing in recursion, there are O(N) levels and each is O(N) => O(N^2)

// (actually implementation above is O(N^2 log) due to sort, but one can write without it).

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    // remap 'a', 'b', 'c' in such way, that
    // num of 'a' is not zeros.
    map<char, char> back;
    if (a == 0 and b == 0) {
        back['a'] = 'c';
        a = c;
        b = 0;
        c = 0;
    } else if (a == 0) {
        back['a'] = 'b';
        back['b'] = 'c';
        a = b;
        b = c;
        c = 0;
    } else {
        back['a'] = 'a';
        back['b'] = 'b';
        back['c'] = 'c';
    }

    // solve problem when a != 0.
    string ans = solve(a, b, c);
    for (int i = 0; i != int(ans.size()); ++i)
        cout << back[ans[i]];
    cout << "\n";
    
    return 0;
}

Submission Info

Judge Result