Cod sursa(job #1312934)

Utilizator cipriancxFMI - gr143 Timofte Ciprian cipriancx Data 10 ianuarie 2015 10:33:17
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include<cstdio>
#include <cstdlib>
using namespace std;

int v[1000001],dimv,a,b,c,maxnr,cifre,dim,n;
struct nod *start[10],*stop[10];
struct nod
{    int val;
    struct nod *u;
};

int put(int nr){
int var=1; for(int i=1; i<=nr; i++)var*=10;

return var;
}

void adauga(int nr, int poz)
{

    struct nod *p=(struct nod*)malloc(dim);
   stop[poz]->val=nr;
   stop[poz]->u=p;
   stop[poz]=p;
}

void descarca()
{dimv=0;
struct nod* p;
for(int i=0; i<=9; i++)
while(start[i]!=stop[i])
{
    struct nod* p;
    ++dimv;
    v[dimv]=start[i]->val;
    p=start[i]->u;
    free(start[i]);
    start[i]=p;
}
}



int main()
{
    dim=sizeof(struct nod);
freopen("radixsort.in","r",stdin);
freopen("radixsort.out","w",stdout);
//initializam listele
for(int i=0; i<=9; i++)
{
    start[i]=(struct nod*)malloc(dim);
    stop[i]=start[i];
}
cin>>n>>a>>b>>c;
int anterior,curent;
anterior=b;
adauga(anterior,anterior%10);
for(int i=2; i<=n; i++)
{
    curent=(a*anterior+b)%c;
  adauga(curent,curent%10);
    anterior=curent;
}
descarca();

maxnr=c;
cifre=0;
while(maxnr){cifre++; maxnr/=10;}
int cifra=2;
while(cifra<=cifre)
{
    for(int i=1; i<=dimv; i++)
        adauga(v[i],(v[i]/put(cifra-1))%10);
    descarca();
    cifra++;
}


for(int i=1; i<=dimv; i++)if(i%10 == 1)cout<<v[i]<<" ";


    return 0;
}