Pagini recente » Cod sursa (job #1378870) | Cod sursa (job #2512707) | Cod sursa (job #2388737) | Cod sursa (job #1906529) | Cod sursa (job #422797)
Cod sursa(job #422797)
# include <stdio.h>
# include <math.h>
# define MAXN 150
unsigned long int a[2*MAXN+1][2*MAXN+1],sum[2*MAXN+1][2*MAXN+1];
long int n,m,r,c,elemmaxim;
void citire()
{
FILE *f=fopen("balans.in","r");
fscanf(f,"%ld%ld%ld%ld",&n,&m,&r,&c);
long int i,j;
long int aux;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
fscanf(f,"%ld",&aux);
if (aux>elemmaxim)
elemmaxim=aux;
a[i][j]=aux;
a[i+n][j]=a[i][j];
a[i][j+m]=a[i][j];
a[i+n][j+m]=a[i][j];
}
fclose(f);
for (i=1;i<=2*n;i++)
for (j=1;j<=2*m;j++)
sum[i][j]=sum[i-1][j]+a[i][j];
}
void scrie(float sol)
{
FILE *g=fopen("balans.out","w");
fprintf(g,"%.3f\n",sol);
fclose(g);
}
float sc[2*MAXN+1];
float sumsc[2*MAXN+1];
long int deq[2*MAXN+1];
long int existsPositiveSubsequence()
{
long int begin=1,end=0,j;
for (j=c;j<=m+c;j++)
{
//adauga la deq j-c
deq[++end]=j-c;
//scufunda-l in deq
while (end-1>=begin && sumsc[deq[end]]<sumsc[deq[end-1]])
{
deq[end-1]=deq[end];
end--;
}
//adu capatul deq-ului la curent
while (j-deq[begin]>m)
begin++;
//verifica daca noua suma este pozitiva
if (sumsc[j] >= sumsc[deq[begin]])
return 1;
}
return 0;
}
long int canBeObtained(float avg)
{
// printf("Now testing average: %.3f\n",avg);
//ne alegem doua linii si calculam sumele pe coloane
long int lineup, linedown, j;
for (linedown = r; linedown <= n+r; linedown ++)
for (lineup = n < linedown-r? n : linedown-r; lineup >= 0; --lineup)
{
for (j=1;j<=m+c;j++)
{
sc[j]=sum[linedown][j]-sum[lineup][j]-avg*(linedown-lineup);
sumsc[j]=sc[j]+sumsc[j-1];
}
// for (j=1;j<=2*m;j++)
// printf("%.3f ",sc[j]);
// printf("\n");
if (existsPositiveSubsequence())
return 1;
}
return 0;
}
float calculeaza(float li, float lf)
{
float m;
while ( (li-lf>=0? li-lf: lf-li) >= 1e-4 )
{
//printf("%.8f\n",m);
m =(li+lf)/2;
//daca m este o medie care se poate obtine, atunci cauta una mai mare
if (canBeObtained(m)) li=m;
else lf=m;
}
return m;
}
int main()
{
citire();
float sol = calculeaza(0,elemmaxim);
scrie(sol);
return 0;
}