Cod sursa(job #1020882)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 2 noiembrie 2013 19:42:44
Problema Elementul majoritar Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
using namespace std;
int a[100],n,m,b[100];
int bucket[10];

void radixsort(int n)
{
  int exp = 1;
 
  while (m / exp > 0)
  {
    for(register int i=0;i<10;i++) bucket[i]=0;
    for(register int i = 0; i < n; i++) bucket[(a[i] / exp) & 10]++;
    for (int i = 1; i < 10; i++) bucket[i] += bucket[i - 1];
    for (int i = n - 1; i >= 0; i--) b[--bucket[(a[i] / exp) & 10]] = a[i];
    for (int i = 0; i < n; i++) a[i] = b[i];
    exp *= 10;
  }
}
int main()
{ freopen("elmaj.in","rt",stdin);
  freopen("elmaj.out","wt",stdout);
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    {scanf("%d", &a[i]);
	 m=(a[i]>m) ? a[i] : m;
	}
  radixsort(n);
  int k=1,t; m=0;
  for(int i=0;i<n;i++) 
      if(a[i]==a[i+1]) k++;
		else {if(m<k) {m=k; t=a[i];} k=1;} 
  if(m > n/2) printf("%d %d\n",t,m);
	 else printf("NU\n");
  return 0;
}