Cod sursa(job #1560466)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 ianuarie 2016 19:01:38
Problema Balans Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#define MAXN 300
#define EPS 0.0000001
#define INF 2000000000.0
int ma[MAXN][MAXN], sum[MAXN];
double s[MAXN];

inline double min2(double a, double b){
  return a < b ? a : b;
}

inline int eq(double x, double y){
  if(x - y > EPS)
    return 1;
  if(y - x > EPS)
    return -1;
  return 0;
}

inline char bun(int n, int m, int l, int c, double x){
  int i, j, k;
  double min;
  for(i = 0; i < n - l; i++){
    for(j = 0; j < m; j++)
      sum[j] = 0;
    for(j = i; j < n; j++){
      for(k = 0; k < m; k++)
        sum[k] += ma[j][k];
      if(j >= i + l - 1){
        min = INF;
        s[0] = sum[0] - (j - i + 1) * x;
        for(k = 1; k < m; k++){
          s[k] = s[k - 1] + sum[k] - (j - i + 1) * x;
          if(k >= c && eq(min, s[k - c + 1]) == 1)
            min = s[k - c];
          if(k >= c - 1 && eq(s[k] - min, 0) != -1)
            return 1;
        }
        for(k = c - 1; k < m; k++)
          if(eq(s[k], 0) != -1)
            return 1;
      }
    }
  }
  return 0;
}

int main(){
  FILE *in = fopen("balans.in", "r");
  int n, m, l, c, i, j;
  fscanf(in, "%d%d%d%d", &n, &m, &l, &c);
  if(l == 0)
    l++;
  if(c == 0)
    c++;
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      fscanf(in, "%d", &ma[i][j]);
      ma[i + n][j] = ma[i][j + m] = ma[i + n][j + m] = ma[i][j];
    }
  }
  n *= 2;  m *= 2;
  double rez = 0, pas;
  for(pas = (double)(1 << 16); pas > 0.0001; pas /= 2){
    if(bun(n, m, l, c, rez + pas))
      rez += pas;
  }
  FILE *out = fopen("balans.out", "w");
  fprintf(out, "%.3lf", rez);
  fclose(out);
  return 0;
}