Editorial for Các lá bài Blackjack


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 ladpro98

program ndccard;
uses    math;
const   maxV=22222;
        maxN=10004;
        fi='';
var     check:array[1..maxV] of boolean;
        a:array[1..maxN] of longint;
        n,m,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        read(inp,n,m);
        for i:=1 to n do
        read(inp,a[i]);
        close(inp);
        res:=maxV*maxV+1;
end;

procedure swap(i,j:longint);
var     t:longint;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     i,j,p:longint;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while a[i]<p do inc(i);
                while a[j]>p do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;

procedure process;
var     i,j:longint;
begin
        for i:=1 to n-1 do
        for j:=i+1 to n do
        check[a[i]+a[j]]:=true;
        j:=a[n]+a[n-1];
        for i:=1 to n-2 do
        begin
                while (j>=1) and ((not check[j]) or (a[i]+j>m)) do dec(j);
                if (a[i]+j<=m) then
                res:=min(res,m-a[i]-j);
        end;
end;

begin
        input;
        sort(1,n);
        process;
        write(m-res);
end.

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
const int BUFSIZE = (1<<12) + 17;
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp && !REACHEOF) { \
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);

int n, m;
int bit[500111];
int a[10111];

#define _(x) ((x) & (-(x)))
int update(int u, int k) {
    while (u <= m) {
        bit[u] = max(bit[u], k);
        u += _(u);
    }
}

int get(int u) {
    int res = -1;
    while (u > 0) {
        res = max(res, bit[u]);
        u -= _(u);
    }
    return res;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        memset(bit, 0, sizeof bit);
        FOR(i,1,n) scanf("%d", &a[i]);
        sort(a+1, a+n+1);

        int res = 0;
        FOR(i,1,n) {
            if (a[i] >= m) break;
            int sum, t;
            FOR(j,i+1,n) {
                sum = a[i] + a[j];
                if (sum >= m) break;

                t = get(m - sum);
                if (t >= 0) {
                    res = max(res, sum + t);
                }
            }
            update(a[i], a[i]);
        }
        printf("%d\n", res);
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) For(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) For(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-9;

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e17 + 5;
int dr[4] = {-1, 0, +1, 0};
int dc[4] = {0, -1, 0, +1};
#define maxn 10005

int n, a[maxn], m;

int main() {
//  freopen("in.txt", "r", stdin);
//  freopen("fibonacci.in", "r", stdin);
//  freopen("fibonacci.out", "w", stdout);
    cin >> n >> m;
    Rep(i, n) cin >> a[i];
    sort(a, a + n);

    int res = 0;

    Ford(i, n - 1, 2) {
        if(a[i] >= m) continue;
        int run = 0;
        Ford(j, i - 1, 0){
            if(j <= run) break;
            if(a[j] + a[run] + a[i] > m) continue;
            while(run + 1 < j && a[run + 1] + a[j] + a[i] <= m) run++;
            res = max(res, a[run] + a[j] + a[i]);
        }
    }

    cout << res;

    return 0;
}

Code mẫu của skyvn97

#include<set>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define MAX   10101
using namespace std;
const int INF=(int)1e9;
int m,n;
set<int> sa,sb;
int a[MAX];
int best;
int max(const int &x,const int &y) {
    if (x>y) return (x); else return (y);
}
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i;
    for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
    sort(&a[1],&a[n+1]);
    if (n<3) {
        printf("0");
        exit(0);
    }
    if (a[1]+a[2]+a[3]>m) {
        printf("0");
        exit(0);
    }
    if (a[n]+a[n-1]+a[n-2]<=m) {
        printf("%d",a[n]+a[n-1]+a[n-2]);
        exit(0);
    }
    best=0;
}
int maxlower(const set<int> &s,const int &val) {    
    set<int>::iterator it;
    it=s.begin();
    if (s.empty()) return (-INF);
    if (*it>val) return (-INF);
    it=s.end();
    it--;
    if (*it<=val) return (*it);
    else {
        it=s.upper_bound(val);
        it--;
        return (*it);
    }
}
void process(void) {
    int i,j;    
    sa.clear();sb.clear();
    for (i=1;i<=n/2;i=i+1) {
        if (i>2) best=max(best,maxlower(sa,m-a[i])+a[i]);
        if (best==m) {
            printf("%d",m);
            return;
        }
        for (j=1;j<i;j=j+1)
            if (a[i]+a[j]<=m && sa.find(a[i]+a[j])==sa.end()) sa.insert(a[i]+a[j]);
    }   
    for (i=n/2+1;i<=n;i=i+1) {
        if (i-n/2>2) best=max(best,maxlower(sb,m-a[i])+a[i]);
        if (best==m) {
            printf("%d",m);
            return;
        }
        for (j=n/2+1;j<i;j=j+1)
            if (a[i]+a[j]<=m && sb.find(a[i]+a[j])==sb.end()) sb.insert(a[i]+a[j]);
    }   
    for (i=1;i<=n;i=i+1) {
        if (i<=n/2) best=max(best,maxlower(sb,m-a[i])+a[i]);        
        else best=max(best,maxlower(sa,m-a[i])+a[i]);
        if (best==m) {
            printf("%d",m);
            return;
        }
    }
    printf("%d",best);
}
int main(void) {
    init();
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.