Pagini recente » Cod sursa (job #2279247) | Cod sursa (job #693556) | Cod sursa (job #3134773) | Cod sursa (job #2078313) | Cod sursa (job #7768)
Cod sursa(job #7768)
#include<stdio.h>
#define fin "subsir2.in"
#define fout "subsir2.out"
#define NMAX 5001
#define INF 20000001
long n,min,start,v[NMAX],a[NMAX],b[NMAX],c[NMAX];
//a bun ; b lungime ; c reconst
FILE *in,*out;
void print(long p) {
if (c[p]==p) {
out=fopen(fout,"a");
fprintf(out,"%ld\n%ld",min,p);
fclose(out);
}
else {
print(c[p]);
out=fopen(fout,"a");
fprintf(out," %ld",p);
fclose(out);
}
}
int main() {
long i,j,k,best;
in=fopen(fin,"r");
fscanf(in,"%ld",&n);
for (i=1;i<=n;i++) fscanf(in,"%ld",&v[i]);
min=NMAX;
for (i=n;i>0;i--) {
k=INF; best=INF; a[i]=1; c[i]=i;
for (j=i+1;j<=n;j++)
if (v[j]<k && v[i]<=v[j]) {
a[j]=0;
if (b[j]<best) {
best=b[j];
c[i]=j;
}
if (v[j]<k) k=v[j];
if (b[j]==best && v[j]<v[c[i]]) c[i]=j;
}
if (best==INF) b[i]=1;
else b[i]=best+1;
}
out=fopen(fout,"w");
//for (i=1;i<=n;i++) fprintf(out,"%ld ",a[i]);
for (i=1;i<=n;i++)
if (a[i])
if (min>b[i]) {
min=b[i];
start=i;
}
else
if (min==b[i] && v[i]<v[start]) start=i;
fprintf(out,"%ld\n",min);
do {
fprintf(out,"%ld ",start);
start=c[start];
} while (c[start]!=start);
fprintf(out,"%ld\n",start);
fclose(in); fclose(out);
return 0;
}