# **README**
🤑0773453956 Momo/MB
# **PRIME (YB2022)**

**Ý tưởng:** Dùng sàng nguyên tố và đảo số để kiểm tra và phân tích

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e7;
int t,n;
bool F[maxn],C[10],kt;

int Dao(int n) {
    int tmp = n%10;;
    n/= 10;
    while (n != 0) {
        tmp = tmp*10 + (n % 10);
        n/=10;
    }
    return tmp;
}

void Solve(int n) {
    kt = false;
    n = Dao(n);
    C[2] = C[3] = C[5] = C[7] = false;
    while (n != 0) {
        if (F[n%10] && ! C[n%10]) {
            kt = true;
            cout << n%10 << " ";
            C[n%10] = true;
        }
        n/=10;
    }
    if (kt) cout << "\n";
        else cout << "0\n";
}

int main() {
    freopen("PRIME.INP","r",stdin);
    freopen("PRIME.OUT","w",stdout);
    memset(F,true,sizeof(F));
    F[0] = F[1] = false;
    for (int i = 2; i <= sqrt(maxn); ++i)
        if (F[i]) for (int j = i*i; j <= maxn; j+=i) F[j] = false;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cin >> n;
        if (F[n]) cout << "YES ";
            else cout << "NO ";
        Solve(n);
    }
    return 0;
}

# **ROAD (YB2022)**

**Ý tưởng:** Dùng tổng tiền tố và tìm kiếm nhị phân

#include <bits/stdc++.h>

using namespace std;

struct Road{
    int val,tree;
};

Road A[300005];
int Sa[300005],Sb[300005],a,b,n,minn = INT_MAX,x;

bool cmp(Road a, Road b) {
    return a.val < b.val;
}

int TKNP(int vt) {
    int l = vt,r = n,tmp = -1,mid;
    while (l <= r) {
        mid = (l+r)/2;
        if (Sa[mid] - Sa[vt-1] >= a && Sb[mid] - Sb[vt-1] >= b) {
            tmp = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    return tmp;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("ROAD.INP","r",stdin);
    freopen("ROAD.OUT","w",stdout);
    cin >> n >> a >> b;
    Sa[0] = Sb[0]  = 0;
    for (int i = 1; i <= n; ++i)
        cin >> A[i].val >> A[i].tree;
    sort(A+1,A+n+1,cmp);
    for (int i = 1; i <= n; ++i) {
        Sa[i] = Sa[i-1];
        Sb[i] = Sb[i-1];
        if (A[i].tree == 1) Sa[i]++;
            else Sb[i]++;
    }
    for (int i = 1; i <= n-1; ++i) {
        x = TKNP(i);
        if (x != -1)
            minn = min(minn,A[x].val-A[i].val);
    }
    if (minn == INT_MAX) cout << "-1";
        else cout << minn;
    return 0;
}

# **CONSCELL 0 Truy Vết (YB2022)**

#include <bits/stdc++.h>

using namespace std;

int n,m,d,maxx = INT_MIN,A[10005][10005],F[10005][10005];
int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};


void DFS(int u, int v) {
    F[u][v] = 1;
    int k = A[u][v] + 1;
    for (int i = 0; i < 4; ++i) {
        int xx = u+X[i], yy = v+Y[i];
        if (A[xx][yy] == k && F[xx][yy] == 0) DFS(xx,yy);
        if (A[xx][yy] == k) F[u][v] = max(F[u][v],F[xx][yy]+1);
    }
    maxx = max(maxx,F[u][v]);
}

void Solve() {
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) cin >> A[i][j];
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (F[i][j] == 0)
                DFS(i,j);
    cout << maxx;
    exit(0);
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("CONSCELL.INP","r",stdin);
    freopen("CONSCELL.OUT","w",stdout);
    cin >> m >> n;
    Solve();
    return 0;
}

# **CONSCELL Truy Vết (YB2022)**

Lưu ý: Truy vết này in toạ độ các phần tử của dãy con tăng theo thứ tự tăng dần. **Không chắc chắn** đề thi sẽ ra truy vết theo như này.

**Đầu vào:**
3 3
3 2 1
4 5 8
19 6 7

**Đầu ra:**
8
1 3
1 2
1 1
2 1
2 2
3 2
3 3
2 3

#include <bits/stdc++.h>

using namespace std;

int n,m,d = 0,maxx = INT_MIN,A[10005][10005],F[10005][10005],C[100005],s,t,tmp;
bool kt = true;
int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};


void DFS(int u, int v) {
    F[u][v] = 1;
    int k = A[u][v] + 1;
    for (int i = 0; i < 4; ++i) {
        int xx = u+X[i], yy = v+Y[i];
        if (A[xx][yy] == k && F[xx][yy] == 0 && xx != 0  && xx != n+1 && yy != 0 && yy != m+1) DFS(xx,yy);
        if (A[xx][yy] == k) F[u][v] = max(F[u][v],F[xx][yy]+1);
    }
    if (F[u][v] > maxx) {
        maxx = F[u][v];
        s = u;
        t = v;
    }
}

void Solve() {
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) cin >> A[i][j];
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (F[i][j] == 0)
                DFS(i,j);
    cout << maxx << "\n";
    while (kt) {
        cout << s << " " << t << "\n";
        kt = false;
        tmp = A[s][t]+1;
        for (int i = 0; i <= 3; ++i) {
            int xx = s + X[i], yy = t + Y[i];
            if (A[xx][yy] == tmp ) {
                s = xx;
                t = yy;
                kt = true;
                break;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("CONSCELL.INP","r",stdin);
    freopen("CONSCELL.OUT","w",stdout);
    cin >> m >> n;
    Solve();
    return 0;
}

# **REWARD 0 Truy Vết (YB2022)**

#include <bits/stdc++.h>

using namespace std;

int n,A[100005],F[100005];

int main() {
    freopen("REWARD.INP","r",stdin);
    freopen("REWARD.OUT","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> A[i];
    F[1] = A[1];
    F[2] = A[1]+A[2];
    for (int i = 3; i <= n; ++i)
        F[i] = max(F[i-1],max(F[i-2] + A[i], F[i-3]+A[i]+A[i-1]));
    cout << F[n];
    return 0;
}

# **REWARD Truy Vết (YB2022)**

Không chắc truy vết đúng hoàn toàn, có thể tự sinh test để kiểm chứng.

#include <bits/stdc++.h>

using namespace std;

string tostr(int n) {
    string kq = "";
    while (n != 0) {
        kq += char(n%10 + '0');
        n/=10;
    }
    reverse(kq.begin(),kq.end());
    return kq;
}

int n,A[100005],F[100005];
string Trace[100005];

int main() {
    freopen("REWARD.INP","r",stdin);
    freopen("REWARD.OUT","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> A[i];
    F[1] = A[1];
    Trace[1] = tostr(A[1]);
    F[2] = A[1]+A[2];
    Trace[2] = tostr(A[1]) + " " + tostr(A[2]);
    for (int i = 3; i <= n; ++i) {
        F[i] = max(F[i-1],max(F[i-2] + A[i], F[i-3]+A[i]+A[i-1]));
        if (F[i] == F[i-1]) Trace[i] = Trace[i-1];
            else if (F[i] == F[i-2]+A[i]) Trace[i] = Trace[i-2] + " " + tostr(A[i]);
                else Trace[i] = Trace[i-3] + " " + tostr(A[i-1]) + " " + tostr(A[i]);
    }
    cout << F[n] << "\n" << Trace[n];
    return 0;
}

# **Rải Nhựa Đường (Đồ Thị)**

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u,v,w;
};

edge A[10005];
int n,a,Lab[100005],u,v,w,r1,r2,kq = 0,d = 0;

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int getRoot(int v) {
    while (Lab[v] > 0) v = Lab[v];
    return v;
}

void Union(int r1, int r2) {
    int x = Lab[r1] + Lab[r2];
    if (Lab[r1] < Lab[r2]) {
        Lab[r1] = x;
        Lab[r2] = r1;
    }
    else {
        Lab[r1] = r2;
        Lab[r2] = x;
    }
}

int main() {
    freopen("<TENFILE>.INP","r",stdin);
    freopen("<TENFILE>.OUT","w",stdout);
    memset(Lab,-1,sizeof(Lab));
    cin >> n >> a;
    int m = 0;
    while (cin >> u >> v >> w) {
        m++;
        A[m].u = u;
        A[m].v = v;
        A[m].w = w;
      }
      sort(A+1,A+n+1,cmp);
      for (int i = 1; i <= n; ++i)
          if (getRoot(A[i].u) != getRoot(A[i].v)) {
              r1 = getRoot(A[i].u);
              r2 = getRoot(A[i].v);
              kq += A[i].w;
              d++;
              Union(r1,r2);
              if (d == n-1) break;
          }
      cout << kq;
    return 0;
}

# **Đặt Mìn (Đồ Thị)**

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e4;
int n,m,A[1005][1005],u,v,w,Trace[1005][1005],maxx,x,y,minn = INT_MAX,s,t;

void Florentino() {
    for (int u = 1; u <= n; ++u)
        for (int v = 1; v <= n; ++v)
            Trace[u][v] = v;
    for (int k = 1; k <= n; ++k)
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; v++)
                if (A[u][v] > A[u][k] + A[k][v]) {
                    A[u][v] = A[u][k] + A[k][v];
                    Trace[u][v] = Trace[u][k];
                }
}
int main() {
    s = -1;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (j == i) A[i][j] = 0;
                else A[i][j] = MAX;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        A[u][v] = w;
        A[v][u] = w;
    }
    Florentino();
    for (int i = 1; i <= n; ++i) {
        maxx = INT_MIN;
        for (int j = 1; j <= n; ++j) {
            if (maxx < A[i][j]) {
                maxx = A[i][j];
                x = i;
                y = j;
            }
        }
        if (maxx < minn) {
            minn = maxx;
            s = x;
            t = y;
        }
    }
    if (s == -1) {
        cout << "NOT FOUND";
        exit(0);
    }
    cout << s << "\n";
    cout << t << " " << A[s][t] << "\n";
    while (s != t) {
        cout << s << " -> ";
        s = Trace[s][t];
    }
    cout << t;
    return 0;
}