Editorial for Pizza Location


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

type ar=array[1..100] of boolean;
var n,k,m,re,r:longint;
    a:array[1..20,0..1] of longint;
    b:array[1..100,0..2] of longint;
    d:array[1..100,1..20] of boolean;
    f:array[1..20] of longint;
    c,e:ar;

procedure rf;
var i:longint;
begin
     readln(k,r);
     readln(m);
     for i:=1 to m do readln(a[i,0],a[i,1]);
     readln(n);
     for i:=1 to n do readln(b[i,0],b[i,1],b[i,2]);
end;

procedure init;
var i,j,t:longint;
begin
     for j:=1 to m do
         for i:=1 to n do
             if sqr(a[j,0]-b[i,0])+sqr(a[j,1]-b[i,1])<=r*r then
             begin
                  d[i,j]:=true;
                  inc(f[j],b[i,2]);
             end;
end;

procedure att(i,j:longint;var s:longint;e:ar);
var p,q,t:longint;
begin
     if (i>k) or (j>m) then
     begin
          if s>re then re:=s;
          exit;
     end;
     for p:=j to m-k+i do
     begin
          if (i=k) and (f[p]+s<=re) then continue;
          t:=0;
          fillchar(e,sizeof(e),false);
          for q:=1 to n do
              if (not c[q]) and d[q,p] then
              begin
                   t:=t+b[q,2];
                   c[q]:=true;
                   e[q]:=true;
              end;
          s:=s+t;
          att(i+1,p+1,s,e);
          for q:=1 to n do
              if e[q] then c[q]:=false;
          s:=s-t;
     end;
end;

procedure pr;
var i,j,s:longint;
begin
     init;
     re:=0; s:=0;
     att(1,1,s,e); 
     writeln(re);
end;

begin
     rf;
     pr;
end.

Code mẫu của happyboy99x

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

#define M 20+5
#define N 100+5

int a[M][N];
int rx[M], ry[M], hx[N], hy[N], p[N]; //restaurant x, y, house x, y, people
int k, r, m, n, inRange[N], now, res;

inline int sqr(int x) { return x*x; }

void init() {
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j) 
            if(sqr(hx[j]-rx[i]) + sqr(hy[j]-ry[i]) <= r)
                a[i][++a[i][0]] = j;
}

void enter() {
    scanf("%d%d%d",&k,&r,&m); r *= r;
    for(int i = 0; i < m; ++i) scanf("%d%d",rx+i,ry+i);
    scanf("%d",&n);
    for(int i = 0; i < n; ++i) scanf("%d%d%d",hx+i,hy+i,p+i);
}

void backtrack(int q, int x) {
    if(k-q > m-x) return;
    if(q == k) res = max(now, res); 
    else for(int i = x; i < m; ++i) {
            for(int j = 1; j <= a[i][0]; ++j)
                if(inRange[a[i][j]]++ == 0) now += p[a[i][j]];
            backtrack(q+1, i+1);
            for(int j = 1; j <= a[i][0]; ++j)
                if(--inRange[a[i][j]] == 0) now -= p[a[i][j]];
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    enter();
    init();
    backtrack(0, 0);
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

program pizzaloc;
uses    math;
type    pizzares=record
                x,y:longint;
        end;
        house=record
                x,y,s:longint;
        end;
        arr=array[0..11] of longint;
const   lim=10;
        maxn=123;
        maxm=21;
        fi='';
var     pos:array[1..maxn] of pizzares;
        a:array[1..maxn] of house;
        bit:array[0..maxn,0..maxn] of longint;
        p:array[0..maxn,0..1 shl lim] of longint;
        cs:arr;
        k,r,m,n,res,mp:longint;

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

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;

procedure init;
var     k,i,j:longint;
begin
        r:=sqr(r);
        mp:=n div lim;
        for i:=1 to m do
        begin
                for j:=1 to n do
                if (r>=(sqr(pos[i].x-a[j].x)+sqr(pos[i].y-a[j].y))) then
                begin
                        if j mod lim<>0 then
                        inc(bit[i,j div lim],1 shl (j mod lim-1))
                        else
                        inc(bit[i,j div lim-1],1 shl (lim-1));
                end;
        end;
        for k:=0 to n div lim do
        for i:=0 to 1 shl lim-1 do
        begin
                for j:=1 to lim do
                if getbit(i,j)=1 then
                inc(p[k,i],a[j+k*lim].s);
        end;
end;

procedure back(i,c:longint; s:arr);
var     j,t:longint;
begin
        if (c>=k) then
        begin
                t:=0;
                for j:=0 to mp do
                inc(t,p[j,s[j]]);
                res:=max(res,t);
                exit;
        end;
        if i>m then exit;
        if (k-c)<=(m-i) then back(i+1,c,s);
        for j:=0 to mp do
        s[j]:=s[j] or bit[i,j];
        back(i+1,c+1,s);
end;

begin
        input;
        init;
        back(1,0,cs);
        write(res);
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cmath>
#define MAXN 111
#define FOR(i,a,b) for(long i=a; i<=b; i++)
using namespace std;

long k,r,m,x[MAXN],y[MAXN],n,x2[MAXN],y2[MAXN],s[MAXN],res,kq[MAXN];
long mask[MAXN],S;

long sqr(long u) {
    return u*u;
}

void inp() {
    scanf("%ld %ld %ld",&k,&r,&m);
    FOR(i,1,m) scanf("%ld %ld",&x[i],&y[i]);

    scanf("%ld",&n);
    FOR(i,1,n) scanf("%ld %ld %ld ",&x2[i],&y2[i],&s[i]);

    FOR(i,1,n) {
        FOR(j,1,m)
        if (sqr(x2[i]-x[j])+sqr(y2[i]-y[j])<=r*r)
            mask[i]+=1L<<(j-1);
    }
}

void update() {
    long sum=0;
    FOR(i,1,n)
        if (S&mask[i]) sum+=s[i];
    res=max(res,sum);
}

void duyet(long i) {
    if (i>k) {
        update();
        return ;
    }

    FOR(j,kq[i-1]+1,m-k+i) {
        S+=1L<<(j-1);
        kq[i]=j;
        duyet(i+1);
        S-=1L<<(j-1);
    }
}

void solve() {
    duyet(1);
    printf("%ld\n",res);
}

int main() {
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

struct toado
{
    int x,y;
};

struct cuahang
{
       public:
     int sch,a[101];
};

int main()
{
    //freopen("PIZZALOC.in","r",stdin);
    int k,r,m,n,nguoi[101];
    toado A[21],B[101];
    cuahang  ch[21];
    scanf("%d %d",&k,&r);
    scanf("%d",&m);

    for(int i = 1;i<=m;i++)
    {
            //printf("1\n");
        //ch[i].sch = 0;
        scanf("%d %d",&A[i].x,&A[i].y);
    }
   // printf("2\n");
    scanf("%d",&n);
    for(int i = 1;i<=n ; i++)
        scanf("%d %d %d",&B[i].x,&B[i].y,&nguoi[i]);
    for(int i = 1;i<=m;i++)
    {
           // printf("3\n");
        ch[i].sch = 0;
       // printf("4\n");
        for(int j = 1;j<=n;j++)

            if((A[i].x-B[j].x)*(A[i].x-B[j].x)+(A[i].y-B[j].y)*(A[i].y-B[j].y)<= r*r)
            {
                ch[i].sch++;
                ch[i].a[ch[i].sch] = j;
            }
    }

    int u[k+1],flag[101],KQ = 0;
    for(int i = 1;i<=k;i++)
        u[i] = i;

    while(true)
    {
         //for(int i = 1;i<=k;i++) printf("%d ",u[i]);
         //printf("\n");
         int max = 0;
         for(int i = 1 ;i<=n;i++)
             flag[i] = 0;
         for(int i = 1;i<=k;i++)
             for(int j = 1;j<=ch[u[i]].sch;j++)
                 if(flag[ch[u[i]].a[j]]==0)
                 {
                     flag[ch[u[i]].a[j]]=1;
                     max = max + nguoi[ch[u[i]].a[j]];
                 }
        // printf("_____%d____\n",max);
         if(max>KQ)
             KQ = max;
         if(u[k]<m)
             u[k]++;
         else
         {
             int fl = k-1;
             while(fl>0)
             {
                 if(u[fl]+1!=u[fl+1])
                      break;
                 fl--;
             }
             if(fl==0)
                 break;
             else 
             {
                  u[fl]++;
                  for(int i = fl+1;i<=k;i++)
                      u[i] = u[i-1]+1;
             }
         }
    }
    printf("%d",KQ);
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program PIZZALOC;
Const
  input  = '';
  output = '';
  maxn = 100;
  maxm = 20;
Type
  rec = record
    x,y: integer;
  end;
Var
  n,m,k,r,res,resmax: integer;
  s,e: array[1..maxn] of rec;
  num,es,curr: array[1..maxn] of integer;
  last: array[0..maxn] of integer;
  ser: array[1..maxm,1..maxn] of integer;
  free: array[1..maxm] of boolean;

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

  Readln(f, k, r);

  Readln(f, m);
  For i:= 1 to m do readln(f, s[i].x, s[i].y);

  Readln(f, n);
  For i:= 1 to n do
    Begin
      Read(f, e[i].x, e[i].y);
      Readln(f, num[i]);
    End;

  Close(f);
End;

Procedure gens;
Var
  i,j,dis: integer;
Begin
  Fillchar(es, sizeof(es), 0);
  For i:= 1 to m do
    For j:= 1 to n do
      Begin
        dis:= sqr(s[i].x - e[j].x) + sqr(s[i].y - e[j].y);
        If dis <= r * r then
          Begin
            inc(es[i]);
            ser[i,es[i]]:= j;
          End;
      End;

  Fillchar(free, sizeof(free), true);

  Fillchar(curr, sizeof(curr), 0);
  res:= 0;
  resmax:= 0;

  last[0]:= 0;
End;

Procedure attempt(i: integer);
Var
  j,ij: integer;
Begin
  For j:= last[i - 1] + 1 to m do if free[j] then
    Begin
      free[j]:= false;
      last[i]:= j;

      For ij:= 1 to es[j] do
        Begin
          If curr[ser[j,ij]] = 0 then res:= res + num[ser[j,ij]];
          inc(curr[ser[j,ij]]);
        End;

      If i = k then
        Begin
          If resmax < res then resmax:= res;
        End
      else attempt(i + 1);

      free[j]:= true;
      For ij:= 1 to es[j] do
        Begin
          dec(curr[ser[j,ij]]);
          If curr[ser[j,ij]] = 0 then res:= res - num[ser[j,ij]];
        End;
    End;
End;

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

Begin
  init;
  gens;
  attempt(1);
  printresult;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   250
struct pos
    {
        long x;
        long y;
    };
int k,n,m,r,sum,b;
pos p[MAX];
pos h[MAX];
int s[MAX];
int sou[MAX];
bool c[MAX];
bool go[MAX][MAX];
void init(void)
{
    scanf("%d",&k);
    scanf("%d",&r);
    scanf("%d",&m);
    int i,j;
    for (i=1;i<=m;i=i+1)
        {
            scanf("%ld",&p[i].x);
            scanf("%ld",&p[i].y);
        }
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1)
        {
            scanf("%ld",&h[i].x);
            scanf("%ld",&h[i].y);
            scanf("%d",&s[i]);
        }
    for (i=1;i<=m;i=i+1)
        for (j=1;j<=n;j=j+1)
            {
                if ((p[i].x-h[j].x)*(p[i].x-h[j].x)+(p[i].y-h[j].y)*(p[i].y-h[j].y)<=r*r) go[i][j]=true;
                else go[i][j]=false;
            }
    for (i=1;i<=n;i=i+1) c[i]=false;
    sou[0]=0;
    b=0;
}
void update(void)
{
    if (sum<=b) return;
    b=sum;
}
void btrk(int t)
{
    int i,j,l;
    int tmp[MAX];
    for (i=sou[t-1]+1;i+k-t<=m;i=i+1)
        {
            sou[t]=i;
            l=0;
            for (j=1;j<=n;j=j+1)
                {
                    if ((go[i][j]) && (!c[j]))
                        {
                            l=l+1;
                            c[j]=true;
                            tmp[l]=j;
                            sum=sum+s[j];
                        }
                }
            if (t==k) update();
            else btrk(t+1);
            for (j=1;j<=l;j=j+1)
                {
                    c[tmp[j]]=false;
                    sum=sum-s[tmp[j]];
                }
        }
}
int main(void)
{
    init();
    btrk(1);
    printf("%d",b);
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.