Cod sursa(job #2608899)

Utilizator matthriscuMatt . matthriscu Data 1 mai 2020 20:47:55
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <cstdio>

int nthDigit(int n, int x) {
    while(n-- > 1)
        x /= 10;
    return x % 10;
}

int numDigits(int n) {
    int rez = 0;
    while(n) {
        ++rez;
        n /= 10;
    }
    return rez;
}

int v[10000005],
    bucket0[100005], bucket1[100005], bucket2[100005], bucket3[100005],
    bucket4[100005], bucket5[100005], bucket6[100005],
    bucket7[100005], bucket8[100005], bucket9[100005],
    cnt, cnt0, cnt1, cnt2, cnt3, cnt4, cnt5, cnt6, cnt7, cnt8, cnt9;

int main() {
    int n, a, b, c, max, temp, i, j, k;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d%d%d%d", &n, &a, &b, &c);
    v[1] = b;
    max = numDigits(b);
    for(i = 2; i <= n; ++i) {
        v[i] = (a * v[i-1] + b) % c;
        temp = numDigits(v[i]);
        if(temp > max)
            max = temp;
    }

    for(k = 1; k <= max; ++k) {
        cnt = cnt0 = cnt1 = cnt2 = cnt3 = cnt4 = cnt5 = cnt6 = cnt7 = cnt8 = cnt9 = 0;
        for(j = 1; j <= n; ++j)
            if(nthDigit(k, v[j]) == 1)
                bucket1[++cnt1] = v[j];
            else if(nthDigit(k, v[j]) == 2)
                bucket2[++cnt2] = v[j];
            else if(nthDigit(k, v[j]) == 3)
                bucket3[++cnt3] = v[j];
            else if(nthDigit(k, v[j]) == 4)
                bucket4[++cnt4] = v[j];
            else if(nthDigit(k, v[j]) == 5)
                bucket5[++cnt5] = v[j];
            else if(nthDigit(k, v[j]) == 6)
                bucket6[++cnt6] = v[j];
            else if(nthDigit(k, v[j]) == 7)
                bucket7[++cnt7] = v[j];
            else if(nthDigit(k, v[j]) == 8)
                bucket8[++cnt8] = v[j];
            else if(nthDigit(k, v[j]) == 9)
                bucket9[++cnt9] = v[j];
            else
                bucket0[++cnt0] = v[j];

        for(i = 1; i <= cnt0; ++i)
            v[++cnt] = bucket0[i];
        for(i = 1; i <= cnt1; ++i)
            v[++cnt] = bucket1[i];
        for(i = 1; i <= cnt2; ++i)
            v[++cnt] = bucket2[i];
        for(i = 1; i <= cnt3; ++i)
            v[++cnt] = bucket3[i];
        for(i = 1; i <= cnt4; ++i)
            v[++cnt] = bucket4[i];
        for(i = 1; i <= cnt5; ++i)
            v[++cnt] = bucket5[i];
        for(i = 1; i <= cnt6; ++i)
            v[++cnt] = bucket6[i];
        for(i = 1; i <= cnt7; ++i)
            v[++cnt] = bucket7[i];
        for(i = 1; i <= cnt8; ++i)
            v[++cnt] = bucket8[i];
        for(i = 1; i <= cnt9; ++i)
            v[++cnt] = bucket9[i];
    }

    for(i = 1; i <= n; i += 10)
        printf("%d ", v[i]);
}