Cerința

Laurențiu este un copil pasionat de teoria numerelor, dar și de informatică. Astfel, în timp ce își savura limonada după o zi obositoare de scoală alături de prietenii săi, acestuia i-a venit în minte o problemă interesantă: dându-se un șir de n numere naturale, sortați-l descrescător după numărul de cifre distincte, la număr de cifre distincte egal sortați-l crescător după suma cifrelor, la suma cifrelor egală sortați-l crescător după produsul cifrelor, iar dacă și produsul cifrelor este egal, atunci numerele se vor sorta crescător după valorile lor.

Date de intrare

Fișierul de intrare sort4.in conține pe prima linie numărul n, iar pe a două linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire sort4.out vă conține șirul sortat.

Restricții și precizări

1 ≤ n ≤ 1.000.000
numerele de pe a două linie a fișierului de intrare vor fi mai mici decât 2.000.000.000

Exemplu

sort4.in

5
111 19 223 51 37

sort4.out

51 223 19 37 111

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 Sort4:

/// solutie - Moca Andrei - 100p
#include <bits/stdc++.h>
using namespace std;
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;
    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }
public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }
    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }
    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};
InParser fin("sort4.in");
OutParser fout("sort4.out");
class Number {
public:
    Number() :
        nrcif(0), sum(0), prod(0), nr(0) {}
    Number(int x) {
        int freq;
        nr = x;
        freq = sum = 0;
        prod = 1;
        while (x) {
            freq |= (1 << (x % 10));
            sum += (x % 10);
            prod *= (x % 10);
            x /= 10;
        }
        nrcif = __builtin_popcount(freq);
    }
    friend OutParser& operator << (OutParser& os, const Number& x) {
        os << x.nr;
        return os;
    }
    bool operator < (const Number& x) const {
        if (nrcif != x.nrcif) return nrcif > x.nrcif;
        if (sum != x.sum) return sum < x.sum;
        if (prod != x.prod) return prod < x.prod;
        return nr < x.nr;
    }
private:
    int nrcif, sum, prod, nr;
};
vector<Number> v;
int n, x;
int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> x;
        v.emplace_back(x);
    }
    sort(v.begin(), v.end());
    for (const Number& x : v)
        fout << x << ' ';
    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 #3146 Sort4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3146 Sort4 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 #3146 Sort4