Cod sursa(job #176388)

Utilizator albuaAlbu Alexandru albua Data 11 aprilie 2008 10:17:31
Problema Economie Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>

FILE *f,*g;
int a[505],n,i,b[105],max;
char c[1005];

int divide(int ls, int ld)
{
  int s=ls,d=ld,aux;
  aux=a[ls];
  while(s<d)
    {
	  while((s<d)&&(a[d]>aux))d--;
	  a[s]=a[d];
	  while((s<d)&&(a[s]<=aux))s++;
	  a[d]=a[s];
	}
  a[s]=aux;
  return s;
}

void quick(int ls, int ld)
{
  int k;
  if(ls<ld)
    {
	  k=divide(ls,ld);
	  quick(1,k-1);
	  quick(k+1,n);
	}
}

int verifica(void)
{
  int i;
  for(i=1;i<=n;i++)
    if(c[a[i]]==0)
	  return 0;
  return 1;
}

void genereaza(void)
{
  int i;
  for(i=a[1];i<=max;i+=a[1])
    c[i]=1;
}

void actualizeaza(int pas)
{
  int i,j;
  for(i=pas;i<=max;i+=pas)
    c[i]=1;
  for(i=1;i<=n;i++)
    if(c[i]==1)
	  c[i+pas]=1;
}

void afiseaza(void)
{
  int i;
  fprintf(g,"%d\n",b[0]);
  for(i=1;i<=b[0];i++)
    fprintf(g,"%d\n",b[i]);
}

int main()
{
  f=fopen("economie.in","r");
  g=fopen("econimie.out","w");
  fscanf(f,"%d\n",&n);
  for(i=1;i<=n;i++)  fscanf(f,"%d\n",&a[i]);
  quick(1,n);
  b[0]++;
  b[b[0]]=a[1];
  i=1;
  max=a[n];
  genereaza();
  while(!verifica())
    {
	   b[0]++;
	   b[b[0]]=a[++i];
	   actualizeaza(a[i]);
	}
  afiseaza();
  fclose(f);  fclose(g);
  return 0;
}