Cod sursa(job #344952)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 1 septembrie 2009 13:46:06
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <values.h>
#define Nmax 5005
#define BIG MAXINT

int v[Nmax],a[Nmax],t[Nmax];
int n,i,min,j,min2,max,poz,rez,pozr,ok,minx;

void write(int x){
	printf("%d ",x);
   if(x != t[x] ) write(t[x]);
}

int main(){
	freopen("subsir2.in","r",stdin);
   freopen("subsir2.out","w",stdout);
   scanf("%d",&n);
   for(i=1;i<=n;++i) scanf("%d",&v[i]);

   a[n]=1; t[n]=n;  rez=BIG;
   for(i=n-1;i>=1;i--){
   	min=BIG; min2=BIG;
     for(j=i+1;j<=n;j++){
     		if(v[j] >= v[i] && v[j] < min){
         	min=v[j];
            if(a[j] <=min2) min2=a[j],poz=j;
         }
       //    if(a[j]<=rez) rez=BIG,pozr=j;
         }
     if(min==BIG) a[i]=1, t[i]=i;
     else a[i]=a[poz]+1, t[i]=poz;
   }

 /*  min=a[1];  poz=1;
	for(i=1;i<=n;++i)
     if(a[i] ==min && v[i]<v[poz]) min=a[i], poz=i;
       */
  /* if(rez==BIG){
    rez=1;
    for(i=1;i<=n;++i)if(v[i]<min)min=v[i],pozr=i;
   }  */
   min=BIG; v[0]=BIG; minx=BIG;
   for(i=1;i<=n ;++i)
     if(a[i] < min && v[i] < minx) min=a[i],pozr=i,minx=v[i];
	  else
     if(a[i] == min && v[i]<minx) pozr=i,minx=v[i];
       else if(v[i] < minx ) minx=v[i];

   printf("%d\n",min);
   write(pozr);
   fclose(stdin); fclose(stdout);
   return 0;
}