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