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

#include <bits/stdc++.h>

#define NM 3002
#define QM 300002
#define XM 1000000000000000
#define INF XM

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;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long 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 << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 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;
    }
};

int n;
struct sir
{
    int val;
    int distincte;
    int sum;
    int prod;
    bool operator <(const sir &B) const
    {
        if(this->distincte != B.distincte) return this->distincte > B.distincte;
        if(this->sum != B.sum) return this->sum < B.sum;
        if(this->prod != B.prod) return this->prod < B.prod;
        return this->val < B.val;
    }
}A[1000001];

int main()
{
    InParser fin("sort4.in");
    OutParser fout("sort4.out");
    fin >> n;
    int x,c,s,p;
    for(int i = 1; i <= n; i++)
    {
        fin >> A[i].val;
        x=A[i].val;
        int F[11]={0};
        s = 0,p=1,c = 0;
        while(x)
        {
            F[x%10]++;
            s=s+x%10;
            p=p*(x%10);
            if(F[x%10]==1) c++;
            x/=10;
        }
        A[i].distincte = c;
        A[i].sum = s;
        A[i].prod = p;
    }
    sort(A+1,A+n+1);
    for(int i = 1; i <= n; i++)
        fout<<A[i].val<<' ';
    return 0;
}