Editorial for NERED


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100 + 5;
int a[N][N], n, m, f[N][N];

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 0, x, y; i < m; ++i) scanf("%d%d", &x, &y), a[x][y] = 1;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j)
        f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j];
    int res = m;
    for(int w = 1; w <= n; ++w) if(m % w == 0) {
        int h = m / w;
        for(int x = w; x <= n; ++x) for(int y = h; y <= n; ++y)
            res = min(res, m - (f[x][y] - f[x-w][y] - f[x][y-h] + f[x-w][y-h]));
    }
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

program mnered;
uses    math;
const   maxn=101;
        fi='';
var     s,a:array[0..maxn,0..maxn] of longint;
        n,res,m:longint;

procedure input;
var     inp:text;
        i,x,y:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n,m);
        for i:=1 to m do
        begin
                readln(inp,x,y);
                a[x,y]:=1;
        end;
        close(inp);
end;

procedure init;
var     i,j:longint;
begin
        for i:=1 to n do
        for j:=1 to n do
        s[i,j]:=s[i,j-1]+s[i-1,j]-s[i-1,j-1]+a[i,j];
end;

function get(x,y,u,v:longint):longint;
begin
        exit(s[u,v]-s[x-1,v]-s[u,y-1]+s[x-1,y-1]);
end;

procedure work(p,q:longint);
var     i,j:longint;
begin
        for i:=p to n do
        for j:=q to n do
        res:=min(res,m-get(i-p+1,j-q+1,i,j));
end;

procedure process;
var     i:longint;
begin
        res:=high(longint);
        for i:=1 to trunc(sqrt(m)) do
        begin
                if m mod i = 0 then
                begin
                        work(i,m div i);
                        work(m div i,i);
                end;
        end;
end;

begin
        input;
        init;
        process;
        write(res);
end.

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=111;
var
  n,m:longint;
  sum,a:array[-1..MAXN,-1..MAXN] of longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure inp;
var
  u,v:longint;
begin
  read(f1,n,m);
  for m:=1 to m do
    begin
      read(f1,u,v);
      a[u,v]:=1;
    end;
end;
procedure solve;
var
  i,j,u1,v1,u2,v2,l,kq:longint;
begin
  for i:=1 to n do
  for j:=1 to n do
    sum[i,j]:=sum[i-1,j]+sum[i,j-1]-sum[i-1,j-1]+a[i,j];
  kq:=m;
  for u1:=1 to n do
  for v1:=1 to n do
    for l:=0 to n-u1 do
      begin
        u2:=u1+l;
        if m mod (u2-u1+1)<>0 then continue;
        v2:=v1+m div (u2-u1+1)-1;
        if v2>n then continue;
        kq:=min(kq,m-(sum[u2,v2]-sum[u1-1,v2]-sum[u2,v1-1]+sum[u1-1,v1-1]));
      end;
  writeln(f2,kq);
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long n,m,ax[10001],ay[10001],free[101][101],u,v;
//freopen("MNERED2.inp","r",stdin);
scanf("%ld %ld",&n,&m);
for(long i=1;i<=n;i++)
  for(long j=1;j<=n;j++)
    free[i][j]=0;
long t=0;    
for(long i=1;i<=m;i++)
  {
  scanf("%ld %ld",&u,&v);
  if(free[u][v]==0)
    {
    t++;
    ax[t]=u;
    ay[t]=v;
    free[u][v]=1;
    }
  }
long max=0;  
for(long i=1;i<=m;i++)
  {
  if(m%i!=0)
    continue;
  else if(i>n||m/i>n)
    continue;
  else
    {
    long u=m/i;         
    long f[101][101],tinh;
    for(long j=1;j<=n;j++)
      for(long k=1;k<=n;k++)  
         f[j][k]=0;
    for(long j=1;j<=t;j++)
      {
      if(ax[j]<=i&&ax[j]+i-1>=n)
        for(long k=1;k<=n-i+1;k++)
          f[k][ay[j]]++;
      else if(ax[j]<=i)
        for(long k=1;k<=ax[j];k++)
          f[k][ay[j]]++;
      else if(ax[j]+i-1>=n)
        for(long k=ax[j]-i+1;k<=n-i+1;k++)
          f[k][ay[j]]++;
      else
        for(long k=ax[j]-i+1;k<=ax[j];k++)
          f[k][ay[j]]++;   
      }
    //for(long j=1;j<=n;j++)
      //for(long k=1;k<=n;k++)   
        //printf("%ld\n",f[j][k]);     
    for(long j=1;j<=n-i+1;j++)
      {
      tinh=0;
      for(long k=1;k<=u;k++)
        tinh=tinh+f[j][k];
      if(tinh>max)
        max=tinh;
      for(long k=2;k<=n-u+1;k++)
        {
        tinh=tinh+f[j][k+u-1]-f[j][k-1];
        if(tinh>max)
          max=tinh;
        }
      }    
    }
  }
printf("%ld",m-max);
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MNERED;
Const
  input  = '';
  output = '';
  maxn = 100;
Var
  a,br,b,tt: array[0..maxn,0..maxn] of integer;
  d: array[1..maxn] of integer;
  num,move: integer;
  n,m: integer;

Procedure init;
Var
  f: text;
  i,j,r,c: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n, m);
  Fillchar(a, sizeof(a), 0);

  For i:= 1 to m do
    Begin
      Readln(f, r, c);
      inc(a[r,c]);
    End;

  Close(f);

  Fillchar(b, sizeof(b), 0);
  For i:= 1 to n do
    For j:= 1 to n do
      If a[i,j] > 1 then b[i,j]:= a[i,j] - 1;
End;

Procedure gens;
Var
  i,j,tb,tp: integer;
Begin
  Fillchar(br, sizeof(br), 0);
  Fillchar(tt, sizeof(tt), 0);

  For i:= 1 to n do
    Begin
      tb:= 0;
      tp:= 0;

      For j:= 1 to n do
        Begin
          tb:= tb + b[i,j];
          br[i,j]:= br[i - 1,j] + tb;

          tp:= tp + a[i,j];
          tt[i,j]:= tt[i - 1,j] + tp;
        End;
    End;

  num:= 0;
  For i:= 1 to m do if m mod i = 0 then
    Begin
      inc(num);
      d[num]:= i;
    End;
End;

Procedure solve;
Var
  sx,sy,fx,fy: integer;
  i,tmp,mb,mt: integer;
Begin
  move:= maxn * maxn;
  For sx:= 1 to n do
    For sy:= 1 to n do
      For i:= 1 to num do
        Begin
          fx:= sx + d[i] - 1;
          fy:= sy + m div d[i] - 1;

          If (fx <= n) and (fy <= n) then
            Begin
              mb:= br[fx,fy] - br[sx - 1,fy] - br[fx,sy - 1] + br[sx - 1,sy - 1];
              mt:= m - (tt[fx,fy] - tt[sx - 1,fy] - tt[fx,sy - 1] + tt[sx - 1,sy - 1]);
              tmp:= mb + mt;
              If move > tmp then move:= tmp;
            End;
        End
End;

Procedure printresult;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    Writeln(f, move);
  Close(f);
End;

Begin
  init;
  gens;
  solve;
  printresult;
End.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   111
int n,m;
int c[MAX][MAX];
int s[MAX][MAX];
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,j,x,y;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&x);
        scanf("%d",&y);
        c[x][y]++;
    }
    for (i=1;i<=n;i=i+1)
        for (j=1;j<=n;j=j+1)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(c[i][j]>0);
}
int count(const int &x1,const int &y1,const int &x2,const int &y2) {
    return (s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
}
void process(void) {
    int res=m+1;
    int i,j,dx,dy;
    for (i=1;i<=n;i=i+1)
        for (j=1;(j<=n) && ((n-i+1)*(n-j+1)>=m);j=j+1)
            for (dx=1;dx<=n-i+1;dx=dx+1)
                if (m%dx==0 && m/dx<=n-j+1) {
                    dy=m/dx;
                    minimize(res,m-count(i,j,i+dx-1,j+dy-1));
                }
    printf("%d",res);
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n, m;
int a[111][111], p[111][111];

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u][v] = 1;
    }
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n;++j)
            p[i][j] = p[i-1][j] + a[i][j];
    int res = 0;
    for(int d1=1;d1<=n;++d1) {
        for(int d2=d1;d2<=n;++d2) if( m % (d2-d1+1) == 0) {
            int w = m / (d2-d1+1);
            for(int i=1, cur=0;i<=n;++i) {
                cur += p[d2][i] - p[d1-1][i];
                if(i>w) cur -= p[d2][i-w] - p[d1-1][i-w];
                if(i>=w) res >?= cur;
            }
        }
    }
    cout << m - res << endl;
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.