Cod sursa(job #37816)

Utilizator robbyRobertino robert robby Data 25 martie 2007 12:43:32
Problema Elimin 2 Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[2005];
typedef struct interval{int in,sf;};
interval in[2005];
int v[2005],num[2005];
int compare(const void *c,const void *b)
{
  int x,y,x2,y2;
  x=(*(interval*)c).sf-(*(interval*)c).in;
  y=(*(interval*)b).sf-(*(interval*)b).in;
  x2=(*(interval*)c).sf;
  y2=(*(interval*)b).sf;
  if (y!=x)
	return y-x;
   else
	return a[y2]-a[x2];
}
FILE *f,*g;
int main()
{
  int i,j,n,sta,dre,max,nr;
  f=fopen("elimin2.in","rt");
  g=fopen("elimin2.out","wt");
  fscanf(f,"%s",&a);
  n=strlen(a);
  nr=0;
  for (i=0;i<n;i++)
	for (j=n-1;j>=i;j--)
	  if (a[i]==a[j])
		{
		  in[++nr].in=i;
		  in[nr].sf=j;
		  break;
		}
  qsort(in+1,nr,sizeof(interval),compare);
  sta=-1;
  dre=n;
  max=0;
  for (i=1;i<=nr&&sta<dre;i++)
	if ((in[i].in>sta)&&(in[i].sf<dre))
	 if (!((!max)&&(a[in[i].in]=='0')))
	  {
		v[in[i].in]=1;
		v[in[i].sf]=1;
		max++;
		sta=in[i].in;
		dre=in[i].sf;
		num[in[i].in]=a[in[i].in]-'0';
		num[in[i].sf]=a[in[i].sf]-'0';
	  }
  for (i=0;i<=n;i++)
	if (v[i])
	  fprintf(g,"%d",num[i]);
  fclose(f);
  fclose(g);
  return 0;
}