Editorial for Đàn bò hỗn loạn


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

const fi='';
      fo='';
      maxc=65535;
      maxn=15;
var n,k:longint;
    re:int64;
    a:array[0..maxn] of longint;
    f:array[0..maxc,0..maxn] of int64;
    p:array[0..maxn] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     read(n,k);
     dec(n);
     for i:=0 to n do read(a[i]);
     close(input);
end;

procedure init;
var i:longint;
begin
     p[0]:=1;
     for i:=1 to n+1 do p[i]:=p[i-1]*2;
end;

function out(j,i:longint):boolean;
begin
     out:=((i shr j) and 1)=0;
end;

procedure pr;
var i,j,max,q:longint;
begin
     init;
     fillchar(f,sizeof(f),0);
     for i:=0 to 15 do f[p[i],i]:=1;
     max:=p[n+1]-1;
     for i:=1 to max do
         for j:=0 to n do
             if not out(j,i) then
                for q:=0 to n do
                    if out(q,i) and (abs(a[q]-a[j])>k) then
                       f[i or p[q],q]:=f[i or p[q],q]+f[i,j];
     re:=0;
     for i:=0 to n do
         re:=re+f[max,i];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

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

#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)

#define N 16
int a[N], n, k;
long long f[1<<N][N];
vector<int> suit[N];

void enter() {
    scanf("%d%d",&n,&k);
    for(int i = 0; i < n; ++i) scanf("%d", a+i);
}

long long F(int state, int x) {
    long long & res = f[state][x];
    if(res != -1) return res;
    if(state == 0) return res = 1; 
    res = 0;
    TR(suit[x], it) {
        int t = *it;
        if(state & 1 << t) res += F(state & ~(1 << t), t);
    }
    return res;
}

void solve() {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(abs(a[i] - a[j]) > k) suit[i].push_back(j);
    memset(f, -1, sizeof f);
    long long res = 0;
    for(int i = 0; i < n; ++i)
        res += F((1 << n) - 1 & ~(1 << i), i);
    printf("%lld\n", res);
}

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

Code mẫu của ladpro98

program mixup2;
uses    math;
const   maxN=16;
        maxS=1 shl maxN;
        fi='';
var     f:array[0..maxS,0..maxN] of int64;
        a,power:array[0..maxN] of longint;
        n,m,k:longint;
function getbit(a,i:longint):longint;
begin
        exit(a shr (i-1) and 1);
end;

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

procedure init;
var     i:longint;
begin
        power[0]:=1;
        for i:=1 to n do
        power[i]:=power[i-1] shl 1;
        m:=power[n]-1;
end;

procedure dp;
var     i,j,t:longint;
begin
        for i:=1 to n do
        f[0,i]:=1;
        for i:=1 to m do
        for t:=1 to n do
        if getbit(i,t)=0 then
        begin
                for j:=1 to n do
                if (getbit(i,j)=1) and (abs(a[n-t+1]-a[n-j+1])>k) then
                inc(f[i,t],f[i-power[j-1],j]);
        end;
end;

procedure output;
var     i:longint;
        res:int64;
begin
        res:=0;
        for i:=0 to n-1 do
        inc(res,f[m-power[i],i+1]);
        write(res);
end;

begin
        input;
        init;
        dp;
        output;
end.

Code mẫu của RR

{
PROG: mixup2
LANG: PASCAL
ID: invinci3
}
const
  FINP='';
  FOUT='';
  MAXN=16;
var
  n,k:longint;
  kq:int64;
  s:array[0..MAXN] of longint;
  d:array[0..1 shl MAXN,1..MAXN] of int64;
procedure inp;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n,k);
  for i:=1 to n do
    readln(f,s[i]);
  close(f);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
procedure solve;
var
  mask,last,next:longint;
begin
  for last:=1 to n do
    d[1 shl (last-1),last]:=1;
  for mask:=0 to 1 shl n do
    for last:=1 to n do
    if mask and (1 shl (last-1))>0 then
      for next:=1 to n do
        if (mask and (1 shl (next-1))=0) and (abs(s[next]-s[last])>k) then
          inc(d[mask or (1 shl (next-1)),next],d[mask,last]);
  kq:=0;
  for last:=1 to n do
    inc(kq,d[1 shl n-1,last]);
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

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

long long f[70000][17], tong=0;

int TTD(int x) { return x>0 ? x:-x;}

int main()
{
    //freopen("mixup.in","r",stdin);
    int n,M, a[17],b[17],chay=1;
    tong=0;
    scanf("%d %d",&n,&M);
    for(int i = 0;i<n;i++)
            scanf("%d",&a[i]);
    for(int i = 0;i<n;i++)
        f[0][i] = 1;
    b[0] = 1;
    for(int i = 1;i<n;i++)
    {
        b[i] = b[i-1]*2;
        chay = chay + b[i];
    }
    for(int i = 1;i<=chay;i++)
    {
        int t[n],m= i;
        for(int j = 0;j<n;j++)
        {
            t[j] = m%2;
            m = m/2;
        }
        for(int j = 0;j<n;j++)
        {
            f[i][j]=0;
            if(b[j]==i) f[i][j]=1;
            else if(t[j]!=0)
            {
                for(int k = 0;k<n;k++)
                     if(TTD(a[j]-a[k])>M)
                          f[i][j]+=f[i-b[j]][k];
                //if(i==8) printf("%d %d\n",j);
            }
        }
        //for(int j = 0;j<n;j++)
            //printf("%d ",f[i][j]);
        //printf("\n");
    }
    for(int i = 0;i<n;i++)
         tong += f[chay][i];
    printf("%lld",tong);
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MIXUP2;
        Const
                input  = '';
                output = '';
        Var
                a,d: array[0..16] of integer;
                  F: array[0..65535,1..16] of int64;
                n,k: integer;

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

                Readln(fi, n, k);
                For i:= 1 to n do read(fi, a[i]);

                Close(fi);
          End;

Procedure power;
          Var
                i: integer;
          Begin
                d[0]:= 1;
                For i:= 1 to n do d[i]:= d[i - 1] shl 1;
          End;

Procedure optimize;
          Var
                i,j,t,s,tmp: integer;
          Begin
                Fillchar(F, sizeof(F), 0);
                For i:= 1 to n do F[d[i - 1],i]:= 1;

                For i:= 0 to d[n] - 1 do
                  For j:= 1 to n do if i and d[j - 1] = d[j - 1] then
                        Begin
                                t:= i - d[j - 1];
                                For s:= 1 to n do
                                  if t and d[s - 1] = d[s - 1] then
                                        Begin
                                                tmp:= abs(a[j] - a[s]);
                                                If tmp > k then F[i,j]:= F[i,j] + F[t,s];
                                        End;
                        End;
          End;

Procedure printresult;
          Var
                   fo: text;
                  res: int64;
                    i: integer;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                res:= 0;
                For i:= 1 to n do res:= res + F[d[n] - 1,i];
                Writeln(fo, res);

                Close(fo);
          End;

Begin
        init;
        power;
        optimize;
        printresult;
End.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   17
typedef long long ll;
ll f[MAX][1<<MAX];
int n,k;
int a[MAX];
int lg2[1<<MAX];
int iabs(const int &x) {
    if (x<0) return (-x); else return (x);
}
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    int i;
    for (i=0;i<n;i=i+1) scanf("%d",&a[i]);
    for (i=0;i<MAX;i=i+1) lg2[1<<i]=i;
}
void optimize(void) {
    int i,j,s,t;
    for (i=0;i<n;i=i+1)
        f[i][(1<<n)-1-(1<<i)]=1;
    for (j=(1<<n)-1;j>=0;j=j-1)
        for (i=0;i<n;i=i+1) {
            if ((j|(1<<i))==j) continue;
            s=j;
            while (s>0) {
                t=lg2[s&(-s)];
                if (abs(a[t]-a[i])>k) f[t][j-(1<<t)]+=f[i][j];              
                s=s-(1<<t);
            }
        }
    ll res=0;
    for (i=0;i<n;i=i+1) res+=f[i][0];
    printf("%lld",res);
}
int main(void) {
    init();
    optimize();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int a[22];
    for(int i=0;i<n;++i) cin >> a[i];
    long long *f[n];
    for(int i=0;i<n;++i) {
        f[i] = new long long[1<<n];
        memset( f[i], 0, sizeof(long long) * (1<<n));
    }
    for(int i=0;i<n;++i) f[i][1<<i] = 1;
    for(int bit=1;bit<(1<<n);++bit) 
        for(int last=0;last<n;++last) if((bit&(1<<last))!=0) 
            for(int l2=0;l2<n;++l2) if(l2!=last && (bit&(1<<l2))!=0 && abs(a[l2]-a[last])>k)
                f[last][bit] += f[l2][bit ^ (1<<last)];
    long long r = 0;
    for(int i=0;i<n;++i) r += f[i][(1<<n)-1];
    cout << r << endl;
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.