Cod sursa(job #53406)

Utilizator floringh06Florin Ghesu floringh06 Data 21 aprilie 2007 23:20:25
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
using namespace std;
#include<stdio.h>
#define nmax 5050
#define infinit 10000

FILE *fin=fopen("secv.in","r"),
     *fout=fopen("secv.out","w");
 
long long c[nmax],a[nmax],s[nmax]; 
int i,j,k,n,min,sol;
long long aux;
        
void sort()
{
  for(i=1;i<=n;i=i+1) 
  {
  j=i;
  while(j/2 && a[j/2]<a[j]) 
     {
     aux=a[j/2];
     a[j/2]=a[j];
     a[j]=aux;

     j=j/2;
     }
  }
i=n;
while(i>1)
  {
  aux=a[1];
  a[1]=a[i];
  a[i]=aux;
  i=i-1; 

  j=1;
  while(1) 
    {
    k=2*j;
    if(k>i) break; 
    if(k+1<=i && a[k+1]>a[k]) k=k+1;
    if(a[j] >= a[k]) break;
    aux=a[j];
    a[j]=a[k];
    a[k]=aux;
    j=k;
    }
  }   
}     

void solve()
{
 int i,j,p,len;
 s[1]=a[1];
 p=2;
 for (i=2; i<=n; i++)
  { if (s[p-1]<a[i]) { s[p]=a[i]; p++; } }
 len=p-1;
 for (i=1; i<=n-len+1; i++)
  {
   if (c[i]==min)
    {
     p=1; j=i;
     while (p<len)
      {
       j++;
       if (s[p+1]==c[j]) p++;
       if (p==len) break;
      }
     if (j-i+1<sol) sol=j-i+1;
    } 
  }    
}           

int main()
{
  fscanf(fin,"%d\n",&n);
  for (i=1; i<=n; i++){
   fscanf(fin,"%lld",&c[i]); a[i]=c[i]; }
  sort();
  sol=infinit;
  min=a[1];
  solve();
  if (sol>n) sol=-1; 
  fprintf(fout,"%d\n",sol);
  fclose(fin);
  fclose(fout);
  return 0;
}