Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect.

Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţelege interschimbarea a două elemente din şir aflate pe poziţii vecine.

Cerința

Să se determine numărul maxim care se poate obţine din şirul cu N cifre, după efectuarea a maxim X operaţii swap.

Date de intrare

Fișierul de intrare bignumber.in conține pe prima linie numerele naturale N şi X separate prin exact un spaţiu, iar pe următoarea linie se află N cifre fără spaţiu.

Date de ieșire

Fișierul de ieșire bignumber.out va conține pe prima linie numărul maxim care se poate obţine conform cerinţei din enunţ.

Restricții și precizări

1 ≤ N ≤ 1.000.000
0 ≤ X ≤ 1.000.000.000
Pentru 30% din teste N ≤ 5.000
Pentru alte 20% din teste X ≤ 25.000.000

Exemplu

bignumber.in

5 3
14325

bignumber.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema BigNumber:

#define TuTTy "Cosmin-Mihai Tutunaru"
#include <cstdio>
#include <vector>
#include <algorithm>
#define infile "bignumber.in"
#define outfile "bignumber.out"
#define nmax 1000013
#define ll long long

using namespace std;

int cnt[10];
int untestable[10];

vector<char> v; //the initial string
vector<char> w; //sorted version of w
vector<char> z; //used by getCost and moveLeft
int n, x;

void read() {
    scanf("%d %d\n", &n, &x);
    for (int i = 0; i < n; ++i) {
        char c;
        scanf("%c", &c);
        v.push_back(c);
    }
}

void printVector(vector<char> str) {
    for (size_t i = 0; i < str.size(); ++i) {
        printf("%c", str[i]);
    }

    printf("\n");
}

int getFirstPosAfter(int pos, int va) {
    for (int i = pos+1; i < n; ++i) {
        if (z[i] - '0' == va) {
            return i;
        }
    }

    return -1;
}

ll moveLeft(int pos, char c, int no) {
    ll cost = 0;
    int cnt = 0;

    for (int i = pos; i < (int)z.size(); ++i) {
        if (z[i] == c) {
            ++cnt;
        }

        if (cnt == no) {
            cnt = 0;
            for (int j = i; j >= pos; --j) {
                if (z[j] == c) {
                    ++cnt;
                } else {
                    z[j+cnt] = z[j];
                    cost += cnt;
                }
            }

            for (int j = 0; j < no; ++j) {
                z[pos+j] = c;
            }

            break;
        }
    }

    return cost;
}

ll getCost(int no) {
    ll cost = 0;
    z = v;

    for (int i = 0; i < no+1; ++i) {
        int pos = min(no + 1, i + cnt[w[i] - '0']);
        cost += moveLeft(i, w[i], pos - i);
        i = pos - 1;
    }

    return cost;
}

void solve() {
    for (size_t i = 0; i < v.size(); ++i) {
        cnt[v[i]-'0']++;
    }

    w = v;
    sort(w.begin(), w.end());
    reverse(w.begin(), w.end());

    int le = 0, ri = n-1, best = -1;

    while(le <= ri) {
        int mi = (le+ri) / 2;
        if (getCost(mi) <= x) {
            best = mi, le = mi+1;
        } else {
            ri = mi - 1;
        }
    }

    if (best >= 0) {
        x -= getCost(best);
    } else {
        z = v;
    }

    for (int i = 0; i < best+1; ++i) {
        cnt[z[i] - '0']--;
    }

    for (int i = best+1; i < n && x; ++i) {
        for (int va = 9; va > z[i] - '0' && x; --va) {
            if (!cnt[va] || untestable[va] > i) {
                continue;
            }

            int pos = getFirstPosAfter(i, va);

            if (pos > i && pos - i <= x) {
                x -= pos - i;

                for (int j = pos - 1; j >= i; --j) {
                    z[j+1] = z[j];
                }

                z[i] = va + '0';
            } else {
                untestable[va] = x - (pos-1) - 1;
            }
        }

        cnt[z[i] - '0']--;
    }
}

void write() {
    printVector(z);
}

int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    read();
    solve();
    write();

    fclose(stdin);
    fclose(stdout);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1161 BigNumber

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1161 BigNumber de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1161 BigNumber