Editorial for SHIFT Operator on Matrix


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 flashmt

uses math;
const fi='';
      oo=1000000000;
var n,re,m:longint;
    a:array[0..6,0..6] of longint;
    s:array[0..6] of longint;

procedure rf;
var i,j:longint;
begin
     re:=-oo;
     fillchar(s,sizeof(s),0);
     for i:=0 to n-1 do
          for j:=0 to n-1 do
          begin
               read(a[i,j]);
               s[j]:=s[j]+a[i,j];
          end;
     for j:=0 to n-1 do re:=max(re,s[j]);
end;

procedure att(i,val:longint);
var j,k,m:longint;
begin
     m:=-oo;
     if i>=n then
     begin
          re:=val; exit;
     end;
     for j:=0 to n-1 do
     begin
          s[j]:=s[j]+a[i,j];
          m:=max(m,s[j]);
     end;
     if m<re then att(i+1,m);
     for k:=1 to n-1 do
     begin
          m:=-oo;
          for j:=0 to n-1 do
          begin
               s[j]:=s[j]+a[i,(j+k) mod n]-a[i,(j+k-1) mod n];
               m:=max(m,s[j]);
          end;
          if m<re then att(i+1,m);
     end;
     for j:=0 to n-1 do s[j]:=s[j]-a[i,(j+n-1) mod n];
end;

begin
     assign(input,fi); reset(input);
     while true do
     begin
          read(n);
          if n=-1 then break;
          rf;
          fillchar(s,sizeof(s),0);
          att(0,m);
          writeln(re);
     end;
     close(input);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 123;
const int INF = 0x3f3f3f3f;

int a[N][N];
int sum[N], newSum[N];
int n, ans;

void backtrack(int row) {
    if (row > n) {
        ans = *max_element(sum + 1, sum + 1 + n);
        return;
    }
    for (int shift = 0; shift < n; ++shift) {
        for (int i = 1; i <= n; ++i) newSum[i] = sum[i] + a[row][i + shift];
        if (*max_element(newSum + 1, newSum + 1 + n) >= ans) continue;
        for (int i = 1; i <= n; ++i) sum[i] = newSum[i];
        backtrack(row + 1);
        for (int i = 1; i <= n; ++i) sum[i] -= a[row][i + shift];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while (cin >> n) {
        if (n == -1) break;
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j + n] = a[i][j];
        for (int i = 1; i <= n; ++i) sum[i] = a[1][i];
        ans = INF;
        backtrack(2);
        cout << ans << '\n';
    }
    return 0;
}

Code mẫu của RR

//Written by RR
{$r-,q-}
{$mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
var
  f1,f2         :       text;
  kq            :       array[1..7] of longint;
  sum,a         :       array[1..7,1..14] of longint;
  res,n         :       longint;

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
      i,j:longint;
    begin
      for i:=1 to n do
      for j:=1 to n do
        read(f1,a[i,j]);
      for i:=1 to n do
        for j:=1 to n do
          a[i,n+j]:=a[i,j];
      for i:=1 to n do
        sum[1,i]:=a[1,i];
    end;
function update(i:longint):boolean; inline;
    var
      j:longint;
    begin
      for j:=1 to n do
      begin
        sum[i,j]:=sum[i-1,j]+a[i,j+kq[i]];
        if sum[i,j]>res then exit(false);
      end;
      exit(true);
    end;
procedure update2; inline;
    var
      j,ln:longint;
    begin
      ln:=-1000111000;
      for j:=1 to n do
        ln:=max(ln,sum[n,j]);
      res:=min(res,ln);
    end;
procedure duyet(i:longint); inline;
    var
      k:longint;
    begin
      for k:=0 to n do
        begin
          kq[i]:=k;
          if not update(i) then continue;
          if i<n then duyet(i+1)
          else update2;
          kq[i]:=0;
        end;
    end;

begin
  openF;
  read(f1,n);
  while (n>0) do
    begin
      inp; res:=1000111000;
      duyet(2);
      writeln(f2,res);
      read(f1,n);
    end;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
long max(long a[],long n)
  {
  long T=-1000000;
  for(long i=1;i<=n;i++)
    if(a[i]>T)
      T=a[i];
  return T;
  }
main()
{
long a[8][8],d[8],n;
while(scanf("%ld",&n)>0&&n>0)
  {
  for(long i=1;i<=n;i++)
    for(long j=1;j<=n;j++)
      scanf("%ld",&a[i][j]);
  long t=0,min=1000000;
  while(t<=long(pow(n,n-1)))
    {
    long m=t;
    for(long i=1;i<=n;i++) d[i]=a[n][i];
    for(long i=1;i<=n-1;i++)
      {
      long ti=m%n;
      m=m/n;       
      for(long j=1;j<=ti;j++)
        d[j]=d[j]+a[i][n+j-ti];
      for(long j=ti+1;j<=n;j++)
        d[j]=d[j]+a[i][j-ti];  
      }
    if(max(d,n)<min)
      min=max(d,n);
    t++;
    }
  printf("%ld\n",min);              
  }
//getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MMATRIX;
Const
  input  = '';
  output = '';
  maxn = 7;
  maxv = 100000;
Var
  fi,fo: text;
  m,n: integer;
  a: array[1..maxn,1..maxn] of integer;
  d: array[1..maxn] of integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure init;
Var
  i,j: integer;
Begin
  For i:= 1 to n do
    For j:= 1 to n do read(fi, a[i,j]);
End;

Procedure calc;
Var
  val,tmp: integer;
  i,j,k: integer;
Begin
  val:= 0;
  For i:= 1 to n do
    Begin
      tmp:= 0;
      For j:= 1 to n do
        Begin
          k:= i - d[j];
          If k <= 0 then k:= k + n;
          tmp:= tmp + a[j,k];
        End;
      If val < tmp then val:= tmp;
      If val > m then exit;
    End;
  If m > val then m:= val;
End;

Procedure attempt(i: integer);
Var
  j: integer;
Begin
  For j:= 1 to n do
    Begin
      d[i]:= j;
      If i = n then calc else attempt(i + 1);
    End;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;


Procedure printresult;
Begin
  m:= maxv;
  attempt(1);
  Writeln(fo, m);
End;

Begin
  openfile;

  Repeat
    Readln(fi, n);
    If n <> -1 then
      Begin
        init;
        printresult;
      End;
  Until n = -1;

  closefile;
End.

Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE}
 {$mode delphi}

var
    best, i, j, n : integer;
    a, b : array[1..7,1..7] of integer;
    p : array[1..7] of integer;

procedure duyet(step : integer);
var
    i, j, k, localmax : integer;
begin
    if step > n then
    begin
        for i := 1 to n do
        begin
            k := p[i];
            for j:=1 to n do
            begin
                b[i,j] := a[i,k];
                inc(k);
                if k > n then k := 1;
            end;
        end;
        localmax := 0;
        for j:=1 to n do
        begin
            k := 0;
            for i:=1 to n do k := k + b[i,j];
            if localmax < k then localmax := k;
        end;
        if best > localmax then best := localmax;
        exit;
    end;
    for k := 1 to n do
    begin
        p[step] := k;
        duyet(step+1);
    end;
end;

begin
    while true do
    begin
        read(n);
        if n=-1 then break;
        for i:=1 to n do
        begin
            for j:=1 to n do
                read(a[i,j]);
        end;
        p[1] := 1;
        best := 1000000000;
        duyet(2);
        writeln(best);
    end;
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.