Bài tập A: Nghệ Thuật và Bóng Rổ

Mã nguồn giải:

#include <bits/stdc++.h>
using namespace std;

int diem[10] = {13, 1, 2, 3, 5, 4, 4, 2, 2, 2};

bool laNamNhuan(int nam) {
    return (nam % 400 == 0) || (nam % 4 == 0 && nam % 100 != 0);
}

int ngayLonNhat(int nam, int thang) {
    if (thang == 1 || thang == 3 || thang == 5 || thang == 7 || thang == 8 || thang == 10 || thang == 12) return 31;
    else if (thang == 4 || thang == 6 || thang == 9 || thang == 11) return 30;
    else return laNamNhuan(nam) ? 29 : 28;
}

int main() {
    int soLanChoi = 0;
    int nam = 2000, thang = 1, ngay = 1;
    int tongDiem = 0;
    while (true) {
        tongDiem += diem[nam % 10] + diem[(nam / 10) % 10] + diem[(nam / 100) % 10] + diem[(nam / 1000) % 10];
        tongDiem += diem[thang % 10] + diem[(thang / 10) % 10];
        tongDiem += diem[ngay % 10] + diem[(ngay / 10) % 10];
        if (tongDiem > 50) soLanChoi++;
        if (nam == 2024 && thang == 4 && ngay == 13) break;
        if (ngay < ngayLonNhat(nam, thang)) ngay++;
        else if (thang != 12) {
            thang++;
            ngay = 1;
        } else {
            nam++;
            thang = 1;
            ngay = 1;
        }
        tongDiem = 0;
    }
    cout << soLanChoi;
    return 0;
}

Bài tập B: Cờ Vua Vận Hành

Mã nguồn giải:

#include <bits/stdc++.h>
using namespace std;

int banCo[6][6];
int ketQua = 0;

void quyHoachDeQuy(int soTrang, int soDen, int viTri, int mau) {
    if (soTrang > 13 || soDen > 12 || viTri >= 25) return;
    int hang = viTri / 5, cot = viTri % 5;
    banCo[hang][cot] = mau;
    
    if (cot == 4) {
        bool kiemTraHang = true;
        for (int i = 1; i <= 4; i++) {
            if (banCo[hang][i] != banCo[hang][0]) {
                kiemTraHang = false;
                break;
            }
        }
        if (kiemTraHang) return;
    }
    if (hang == 4) {
        bool kiemTraCot = true;
        for (int i = 1; i <= 4; i++) {
            if (banCo[i][cot] != banCo[0][cot]) {
                kiemTraCot = false;
                break;
            }
        }
        if (kiemTraCot) return;
    }
    if (viTri == 20) {
        bool kiemTraCheo1 = true;
        for (int i = 1; i <= 4; i++) {
            if (banCo[i][4 - i] != banCo[0][4]) {
                kiemTraCheo1 = false;
                break;
            }
        }
        if (kiemTraCheo1) return;
    }
    if (viTri == 24) {
        bool kiemTraCheo2 = true;
        for (int i = 1; i <= 4; i++) {
            if (banCo[i][i] != banCo[0][0]) {
                kiemTraCheo2 = false;
                break;
            }
        }
        if (kiemTraCheo2) return;
    }
    if (viTri == 24) {
        ketQua++;
        return;
    }
    quyHoachDeQuy(soTrang + 1, soDen, viTri + 1, 1);
    quyHoachDeQuy(soTrang, soDen + 1, viTri + 1, 2);
}

int main() {
    quyHoachDeQuy(1, 0, 0, 1);
    quyHoachDeQuy(0, 1, 0, 2);
    cout << ketQua;
    return 0;
}

Bài tập C: Đào Tạo Bộ Sĩ Quan

Mã nguồn giải:

#include <bits/stdc++.h>
using namespace std;

struct BinhMinh {
    long long giaTri;
    int capDo;
} binhMinh[100002];

bool sanSangSoSanh(BinhMinh a, BinhMinh b) {
    if (a.capDo == b.capDo) return a.giaTri < b.giaTri;
    return a.capDo < b.capDo;
}

long long tongTien[100002];

int main() {
    long long soLuong, tien;
    cin >> soLuong >> tien;
    for (long long i = 1; i <= soLuong; i++) {
        cin >> binhMinh[i].giaTri >> binhMinh[i].capDo;
    }
    sort(binhMinh + 1, binhMinh + soLuong + 1, sanSangSoSanh);
    tongTien[0] = 0;
    for (long long i = 1; i <= soLuong; i++) {
        tongTien[i] = tongTien[i - 1] + binhMinh[i].giaTri;
    }
    long long viTri = 1;
    while (true) {
        if (tien > (tongTien[soLuong] - tongTien[viTri - 1])) break;
        viTri++;
    }
    long long ketQua = 0;
    ketQua += tien * binhMinh[viTri - 1].capDo;
    for (long long j = viTri; j <= soLuong; j++) {
        ketQua += binhMinh[j].giaTri * (binhMinh[j].capDo - binhMinh[viTri - 1].capDo);
    }
    cout << ketQua;
    return 0;
}

Bài tập D: Tổ Chức Hoạt Động Nhóm

Mã nguồn giải:

#include <bits/stdc++.h>
using namespace std;

const int MAX_SIZE = 2e5 + 10;
int soLuong, soCanh;
int maMau[MAX_SIZE], maMau2[MAX_SIZE];
vector<int> ke1[MAX_SIZE], ke2[MAX_SIZE];

int timKiem(int dinh1, int dinh2, int cha1, int cha2) {
    int ketQua = 0;
    map<int, int> con1;
    for (auto x : ke1[dinh1]) {
        if (x != cha1) {
            con1[maMau[x]] = x;
        }
    }
    for (auto x : ke2[dinh2]) {
        if (x != cha2) {
            if (con1.count(maMau2[x])) {
                ketQua = max(ketQua, timKiem(con1[maMau2[x]], x, dinh1, dinh2));
            }
        }
    }
    return ketQua + 1;
}

int main() {
    cin >> soLuong >> soCanh;
    for (int i = 1; i <= soLuong; i++) cin >> maMau[i];
    for (int i = 1; i <= soCanh; i++) cin >> maMau2[i];
    int u, v;
    for (int i = 1; i < soLuong; i++) {
        cin >> u >> v;
        ke1[u].push_back(v);
        ke1[v].push_back(u);
    }
    for (int i = 1; i < soCanh; i++) {
        cin >> u >> v;
        ke2[u].push_back(v);
        ke2[v].push_back(u);
    }
    int ketQua = 0;
    if (maMau[1] == maMau2[1]) {
        ketQua = timKiem(1, 1, 0, 0);
    }
    cout << ketQua << endl;
    return 0;
}

Bài tập E: Thống Kê Điểm Số

Mã nguồn giải:

#include <bits/stdc++.h>
#define MAX_N 100005
using namespace std;

int n, k, diem[MAX_N];
double thuong, num[MAX_N], tongBinhPhuong[MAX_N], tong[MAX_N];

bool sanSangSoSanh(double x, double y) {
    return x < y;
}

bool kiemTraHopLe(int x) {
    for (int i = 1; i <= x; i++)
        num[i] = diem[i];
    sort(num + 1, num + x + 1, sanSangSoSanh);
    for (int i = 1; i <= x; i++) {
        tong[i] = tong[i - 1] + num[i];
        tongBinhPhuong[i] = tongBinhPhuong[i - 1] + num[i] * num[i];
    }
    for (int batDau = 1; batDau + k - 1 <= x; batDau++)
        if (tongBinhPhuong[batDau + k - 1] - tongBinhPhuong[batDau - 1] - (tong[batDau + k - 1] - tong[batDau - 1]) * (tong[batDau + k - 1] - tong[batDau - 1]) / k < k * thuong)
            return true;
    return false;
}

int main() {
    cin >> n >> k >> thuong;
    if (k > n) {
        cout << "-1";
        return 0;
    }
    for (int i = 1; i <= n; i++)
        cin >> diem[i];
    int trai = k, phai = n, giua;
    while (true) {
        if (trai == phai) {
            cout << (kiemTraHopLe(trai) ? trai : -1);
            return 0;
        }
        giua = (trai + phai) / 2;
        if (kiemTraHopLe(giua))
            phai = giua;
        else
            trai = giua + 1;
    }
}

Bài tập F: Đếm Thừa Số

Mã nguồn giải:

Đang cập nhật...

Bài tập G: Mua Sắm Thực Phẩm

Mã nguồn giải:

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> ke;  // Sử dụng danh sách kề để biểu diễn cây
vector<int> loaiThucPham;  // Số loại thực phẩm trên mỗi hành tinh
vector<int> duongDi;  // Lưu đường đi từ điểm bắt đầu đến điểm kết thúc
bool timThay = false;  // Kiểm tra xem đã tìm thấy đường đi chưa

// Thuật toán DFS để tìm đường đi từ u đến v
void dfs(int u, int v, vector<int>& duongDiHienTai, vector<bool>& daTham) {
    daTham[u] = true;
    duongDiHienTai.push_back(u);

    if (u == v) {
        duongDi = duongDiHienTai;  // Đường đi đã được tìm thấy
        timThay = true;
        return;
    }

    for (int keNhanh : ke[u]) {
        if (!daTham[keNhanh]) {
            dfs(keNhanh, v, duongDiHienTai, daTham);
            if (timThay) return;  // Nếu đã tìm thấy đường đi, thoát ngay lập tức
        }
    }
    duongDiHienTai.pop_back();  // Quay lui, không cần quay lại trạng thái của 'daTham' vì đây là cây
}

int main() {
    int n, q;
    cin >> n >> q;
    ke.resize(n + 1);
    loaiThucPham.resize(n + 1);

    // Nhập số loại thực phẩm trên mỗi hành tinh
    for (int i = 1; i <= n; i++) {
        cin >> loaiThucPham[i];
    }

    // Nhập n-1 cạnh để xây dựng cây
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }

    // Xử lý từng truy vấn
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;

        // Khởi tạo lại các biến
        duongDi.clear();
        timThay = false;
        vector<bool> daTham(n + 1, false);
        vector<int> duongDiHienTai;

        // Tìm đường đi từ s đến t
        dfs(s, t, duongDiHienTai, daTham);

        // Đếm số loại thực phẩm khác nhau trên đường đi
        set<int> loaiKhacNhau;
        for (int dinh : duongDi) {
            loaiKhacNhau.insert(loaiThucPham[dinh]);
        }

        // In kết quả
        cout << loaiKhacNhau.size() << endl;
    }

    return 0;
}