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.
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