Editorial for Aladdin


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='';
      maxn=210;
type ar=array[1..maxn,1..maxn] of longint;
var n:longint;
    a,b:ar;
    qx,qy:array[0..maxn*maxn] of longint;

procedure rf;
var i,j,dem:longint;
begin
     read(n);
     for i:=1 to n-1 do
          for j:=1 to n-1 do
              read(b[i,j]);
     qx[1]:=1; qy[1]:=1; dem:=1;
     for i:=3 to n+n do
         for j:=max(1,i-n) to min(n,i-1) do
         begin
              inc(dem);
              qx[dem]:=j; qy[dem]:=i-j;
         end;
end;

procedure wf;
var i,j:longint;
begin
     for i:=1 to n do
     begin
          for j:=1 to n do write(a[i,j],' ');
          writeln;
     end;
     halt;
end;

procedure edit(x,y,val:longint);
begin
     if x>1 then b[x-1,y]:=b[x-1,y]+val;
     if y>1 then b[x,y-1]:=b[x,y-1]+val;
     b[x,y]:=b[x,y]+val;
end;

procedure att(p:longint);
var i,j,x,y,xx,yy:longint; c0,c1:boolean;
begin
     if p>n*n then wf;
     x:=qx[p]; y:=qy[p];
     c0:=true; c1:=true;
     if (x>1) and (y>1) then
     begin
          if b[x-1,y-1]<>0 then c0:=false;
          if b[x-1,y-1]<>1 then c1:=false;
     end;
     if c0 then
     begin
          a[x,y]:=0;
          att(p+1);
     end;
     if c1 then
     begin
          a[x,y]:=1;
          edit(x,y,-1);
          att(p+1);
          edit(x,y,1);
     end;
end;

procedure pr;
begin
     att(1);
     writeln('No solution');
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>

const int MAXN = 222;
const int dx[4] = {0,0,1,1};
const int dy[4] = {0,1,0,1};
using namespace std;

int a[MAXN][MAXN], black[MAXN][MAXN];
int n;
bool found;

bool inBound(int x, int y) {
    return (0<x)&&(x<=n)&&(0<y)&&(y<=n);
}

bool ok(int x, int y, int l, int r) {
    if (!inBound(x,y)) return true;
    if ((x==n)||(y==n)) return true;
    int i,p,q;
    int t = a[x][y];
    for(i=0; i<4; i++) {
        p = x+dx[i];
        q = y+dy[i];
        if ((inBound(p,q))&&(black[p][q])) t--;
    }
    return (l<=t)&&(t<=r);
}

void BackTrack(int p, int q, int ii, int jj) {
    if (found) return;
    int i,j,v;
    if (p>n) {
        found = true;
        for(i=1; i<=n; i++) {
            for(j=1; j<=n; j++)
                printf("%d ", black[i][j]);
            printf("\n");
        }
        return;
    }
    for(v=0; v<=1; v++) {
        black[ii][jj] = v;
        if (!ok(ii-1,jj-1,0,0)) continue;
        if (!ok(ii-1,jj,0,1)) continue;
        if (!ok(ii,jj-1,0,2)) continue;
        i = ii+1; j=jj-1;
        if (inBound(i,j))
            BackTrack(p,q,i,j);
        else {
            if (q<n) BackTrack(p,q+1,p,q+1);
            else    BackTrack(p+1,q,p+1,q);
        }
    }
    black[ii][jj] = 0;
}

int main()
{
    //freopen("ALADDIN.in", "r", stdin);
    scanf("%d", &n);
    int i,j;
    for(i=1; i<n; i++) for(j=1; j<n; j++) scanf("%d", &a[i][j]);
    BackTrack(1,1,1,1);
    if (!found) printf("No solution");
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=401;
var
  f1,f2:text;
  test,t,n:longint;
  a,sl:array[1..MAXN,1..MAXN] of longint;
  ok:boolean;
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
  read(f1,n);
  for i:=1 to n-1 do
  for j:=1 to n-1 do
    read(f1,sl[i,j]);
end;
procedure ans;
var
  i,j:longint;
begin
  for i:=1 to n do
    begin
      for j:=1 to n do write(f2,a[i,j],' ');
      writeln(f2);
    end;
  closeF;
  halt;
end;
procedure dienSo(u:longint);
var
  i,j,count:longint;
begin
  ok:=true;
  for i:=2 to n do
    begin
      j:=u+1-i;
      if (j<2) or (j>n) then continue;
      count:=a[i-1,j-1]+a[i-1,j]+a[i,j-1];
      if count=sl[i-1,j-1] then a[i,j]:=0
      else if count+1=sl[i-1,j-1] then a[i,j]:=1
      else ok:=false;
    end;
end;
procedure xoaSo(u:longint);
var
  i,j:longint;
begin
  for i:=2 to n do
    begin
      j:=u+1-i;
      if (j<2) then continue;
      a[i,j]:=0;
    end;
end;
procedure try(u:longint);
var
  i,j:longint;
begin
  for i:=0 to 1 do
  if (u<=n) or (i=0) then
  for j:=0 to 1 do
  if (u<=n) or (j=0) then
    begin
      a[1,u]:=i; a[u,1]:=j;
      dienSo(u);
      if ok then
        begin
          if u=n+n then ans
          else try(u+1)
        end;
      xoaSo(u); a[1,u]:=0; a[u,1]:=0;
    end;
end;
procedure solve;
begin
  a[1,1]:=0;
  try(2);
  a[1,1]:=1;
  try(2);
end;
begin
  openF;
  inp;
  solve;
  writeln(f2,'No solution');
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 222
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,a[maxn][maxn],c[maxn][maxn],tong;

inline int sum(int u, int v){
   return a[u][v]+a[u][v+1]+
          a[u+1][v]+a[u+1][v+1];
}

bool TRY(int u,int v){
     int t=0,uu=0,vv=0; 
     //printf("%d %d\n",u,v);
     if(u==n || v==1){
         if(u+v>=n) { vv = n; uu = u+v+1-vv;}
         else { uu = 1; vv= u+v+1-uu;}
     }
     else{ uu = u+1; vv = v-1;}

     if(u==n && v== n){
          // printf("DDDDD\n");
           a[u][v] = 0;
           t = c[u-1][v-1]-sum(u-1,v-1);
           if(t<0 || t>1) return false;
           a[u][v] = t; return true;
     }

     if(u==1){
           a[u][v] = 0; if(TRY(uu,vv)) return true;
           a[u][v] = 1; if(TRY(uu,vv)) return true;
           return false;
     }

     if(v==1){
           a[u][v] = 0; if(TRY(uu,vv)) return true;
           a[u][v] = 1; if(TRY(uu,vv)) return true;
           return false;
     }

     a[u][v] = 0; t = c[u-1][v-1]-sum(u-1,v-1);
     if(t<0 || t>1) return false;
     a[u][v] = t;
    // if(u==n && sum(u,v-1)!=c[u][v-1]) return false;
   //  if(v==n && sum(u-1,v)!=c[u-1][v]) return false;
     if(TRY(uu,vv)) return true;
     return false;
}

int main(){
   // freopen("ALADIN.in","r",stdin);
     scanf("%d",&n);
     for(int i = 1;i<n;i++) for(int j = 1;j<n;j++) scanf("%d",&c[i][j]);
     memset(a,0,sizeof(a));
    // tong = 3;
    bool flag = false;
     for(int i = 0;i<=1;i++) { a[1][1] = i; if(TRY(1,2)){flag = true; break;}}
     if(!flag) printf("No solution");
     else{
     for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++)
           printf("%d%c",a[i][j],j<n?' ':'\n');
     }
    // getch();
}

Code mẫu của khuc_tuan

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] res;

    public static void main(String[] args) throws Exception {
        BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(kb.readLine());
        int[][] sum = new int[n - 1][n - 1];
        for (int i = 0; i + 1 < n; ++i) {
            StringTokenizer st = new StringTokenizer(kb.readLine());
            for (int j = 0; j + 1 < n; ++j)
                sum[i][j] = Integer.parseInt(st.nextToken());
        }
        int[][] a = new int[n][n];
        res = null;
        go(0, sum, a);
        if (res == null)
            System.out.println("No solution");
        else
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j)
                    System.out.print(res[i][j] + " ");
                System.out.println();
            }
    }

    static void go(int pos, int[][] sum, int[][] a) {
        if (res != null)
            return;
        int n = a.length;
        if (pos >= n) {
            res = new int[n][];
            for (int i = 0; i < n; ++i)
                res[i] = a[i].clone();
            return;
        }
        if (pos == 0) {
            a[0][0] = 0;
            go(pos + 1, sum, a);
            a[0][0] = 1;
            go(pos + 1, sum, a);
            return;
        }
        for (a[0][pos] = 0; a[0][pos] <= 1; ++a[0][pos]) {
            for (a[pos][0] = 0; a[pos][0] <= 1; ++a[pos][0]) {
                boolean ok = true;
                for (int i = 1; i <= pos; ++i) {
                    a[i][pos] = sum[i - 1][pos - 1] - a[i - 1][pos] - a[i][pos - 1] - a[i - 1][pos - 1];
                    if (a[i][pos] < 0 || a[i][pos] > 1) {
                        ok = false;
                        break;
                    }
                    a[pos][i] = sum[pos - 1][i - 1] - a[pos][i - 1] - a[pos - 1][i] - a[pos - 1][i - 1];
                    if (a[pos][i] < 0 || a[pos][i] > 1) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    go(pos + 1, sum, a);
                }
            }
        }
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.