Đề thi học sinh giỏi tỉnh Yên Bái môn Tin học năm học 2023-2024 (có đáp án)

#include <iostream>
#include <vector>

using namespace std;

// Hàm để tìm các vị trí tốt trong một dãy số
vector<int> find_good_positions(vector<int> &a) {
    // Khởi tạo một biến để lưu tổng các số trước vị trí hiện tại
    int prefix_sum = 0;
    // Khởi tạo một vector để lưu các vị trí tốt
    vector<int> good_positions;
    // Lặp qua các phần tử của dãy số
    for (int i = 0; i < a.size(); ++i) {
        // Nếu phần tử hiện tại bằng tổng các số trước đó
        if (a[i] == prefix_sum) {
            // Thêm vị trí hiện tại vào vector
            good_positions.push_back(i + 1); // Cộng 1 vì vị trí bắt đầu từ 1
        }
        // Cập nhật tổng các số trước vị trí hiện tại
        prefix_sum += a[i];
    }
    // Trả về vector các vị trí tốt
    return good_positions;
}

int main() {
    freopen("GPOS.INP", "r", stdin);
    freopen("GPOS.OUT", "w", stdout);

    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Tìm các vị trí tốt
    vector<int> good_positions = find_good_positions(A);

    if (good_positions.size() > 0) {
        cout << good_positions.size() << endl;
        for (int i = 0; i < good_positions.size(); ++i) {
            cout << good_positions[i] << " ";
        }
        cout << endl;
    } else {
        cout << "-1" << endl;
    }

    return 0;
}

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

// Hàm để tìm ước nguyên tố lớn nhất của một số
long long largest_prime_factor(long long n) {
    long long max_factor = 1;
    for (long long i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            max_factor = i;
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1 && n > max_factor) {
        max_factor = n;
    }
    return max_factor;
}

// Hàm để tìm khóa để giải mật mã Lazi trong một xâu ký tự
long long find_key(string s) {
    long long key = 0;
    long long num = 0;
    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else {
            if (num != 0) {
                long long factor = largest_prime_factor(num);
                if (factor > key) {
                    key = factor;
                }
                num = 0;
            }
        }
    }
    if (num != 0) {
        long long factor = largest_prime_factor(num);
        if (factor > key) {
            key = factor;
        }
    }
    return key;
}

int main() {
    freopen("BLAZI.INP", "r", stdin);
    freopen("BLAZI.OUT", "w", stdout);
    string S;
    getline(cin, S);

    // Tìm khóa
    long long key = find_key(S);

    // Ghi kết quả vào file output
    cout << key << endl;

    return 0;
}

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm để tìm số lượng nhiều nhất các căn nhà mà công ty có thể bán
int max_houses(int N, int M, int k, vector<int>& a, vector<int>& b) {
    // Sắp xếp các giá của căn nhà và khách hàng theo thứ tự tăng dần
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    // Khởi tạo biến để lưu số lượng căn nhà đã bán
    int count = 0;
    // Khởi tạo biến để lưu chỉ số của khách hàng hiện tại
    int j = 0;
    // Lặp qua các giá của căn nhà
    for (int i = 0; i < N; ++i) {
        // Nếu chỉ số của khách hàng vượt quá số lượng khách hàng
        if (j >= M) {
            // Dừng vòng lặp
            break;
        }
        // Nếu giá của căn nhà nằm trong khoảng chấp nhận của khách hàng
        if (b[j] - k <= a[i] && a[i] <= b[j] + k) {
            // Tăng số lượng căn nhà đã bán lên 1
            count++;
            // Tăng chỉ số của khách hàng lên 1
            j++;
        }
        // Nếu giá của căn nhà lớn hơn khoảng chấp nhận của khách hàng
        else if (a[i] > b[j] + k) {
            // Tăng chỉ số của khách hàng lên 1, tăng số lượng căn nhà đã bán lên 1
            j++;
            count++;
        }
    }
    // Trả về số lượng căn nhà đã bán
    return count;
}

int main() {
    freopen("HOUSE.INP", "r", stdin);
    freopen("HOUSE.OUT", "w", stdout);
    int N, M, k;
    cin >> N >> M >> k;

    vector<int> a(N), b(M);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> b[i];
    }

    // Tìm số lượng nhiều nhất các căn nhà mà công ty có thể bán
    int result = max_houses(N, M, k, a, b);

    // Ghi kết quả vào file output
    cout << result << endl;

    return 0;
}

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

// Hàm để giải bài toán chọn quà
int solve(int N, int K, vector<int>& M, vector<int>& P) {
    // Khởi tạo mảng F[j] là tổng giá trị lớn nhất khi chọn các sản phẩm khác nhau sao cho tổng khối lượng bằng j
    vector<int> F(K + 1, 0);
    // Gán F[0] bằng 1
    F[0] = 1;
    // Duyệt qua các sản phẩm
    for (int i = 0; i < N; ++i) {
        // Duyệt ngược qua các khối lượng từ K đến M[i]
        for (int j = K; j >= M[i]; --j) {
            // Nếu F[j - M[i]] khác 0
            if (F[j - M[i]] != 0) {
                // Cập nhật F[j] bằng max của F[j] và F[j - M[i]] + P[i]
                F[j] = max(F[j], F[j - M[i]] + P[i]);
            }
        }
    }
    // Trả về kết quả là F[K]
    return F[K];
}

int main() {
    // Mở file input để đọc dữ liệu
    freopen("DQCN.INP", "r", stdin);
    // Mở file output để ghi kết quả
    freopen("DQCN.OUT", "w", stdout);

    int N, K;
    // Đọc số lượng sản phẩm và tổng khối lượng cần đạt được
    cin >> N >> K;

    vector<int> M(N), P(N);
    // Đọc khối lượng và giá trị của từng sản phẩm
    for (int i = 0; i < N; ++i) {
        cin >> M[i] >> P[i];
    }

    // Tìm giá trị lớn nhất có thể đạt được
    int result = solve(N, K, M, P);

    // Ghi kết quả vào file output
    if (result == 0) {
        cout << "NONE" << endl;
    } else {
        cout << result - 1 << endl;
    }

    return 0;
}

# Hàm để tìm các vị trí tốt trong một dãy số
def find_good_positions(a):
    # Khởi tạo một biến để lưu tổng các số trước vị trí hiện tại
    prefix_sum = 0
    # Khởi tạo một danh sách để lưu các vị trí tốt
    good_positions = []
    # Lặp qua các phần tử của dãy số
    for i in range(len(a)):
        # Nếu phần tử hiện tại bằng tổng các số trước đó
        if a[i] == prefix_sum:
            # Thêm vị trí hiện tại vào danh sách
            good_positions.append(i + 1) # Cộng 1 vì vị trí bắt đầu từ 1
        # Cập nhật tổng các số trước vị trí hiện tại
        prefix_sum += a[i]
    # Trả về danh sách các vị trí tốt
    return good_positions

# Đọc dữ liệu từ file input
with open('GPOS.INP', 'r') as file:
    N = int(file.readline())
    A = list(map(int, file.readline().split()))

# Tìm các vị trí tốt
good_positions = find_good_positions(A)

# Ghi kết quả vào file output
with open('GPOS.OUT', 'w') as file:
    if len(good_positions) > 0:
        file.write(str(len(good_positions)) + '\n')
        file.write(' '.join(map(str, good_positions)) + '\n')
    else:
        file.write('-1\n')

# Hàm để tìm ước nguyên tố lớn nhất của một số
def largest_prime_factor(n):
    # Khởi tạo một biến để lưu ước nguyên tố lớn nhất
    max_factor = 1
    # Lặp qua các số từ 2 đến căn bậc hai của n
    for i in range(2, int(n**0.5) + 1):
        # Nếu n chia hết cho i
        if n % i == 0:
            # Cập nhật ước nguyên tố lớn nhất
            max_factor = i
            # Chia n cho i cho đến khi không chia hết
            while n % i == 0:
                n //= i
    # Nếu n lớn hơn 1 và lớn hơn ước nguyên tố lớn nhất
    if n > 1 and n > max_factor:
        # Cập nhật ước nguyên tố lớn nhất
        max_factor = n
    # Trả về ước nguyên tố lớn nhất
    return max_factor

# Hàm để tìm khóa để giải mật mã Lazi trong một xâu ký tự
def find_key(s):
    # Khởi tạo một biến để lưu khóa
    key = 0
    # Khởi tạo một biến để lưu số hiện tại
    num = 0
    # Lặp qua các ký tự của xâu
    for c in s:
        # Nếu ký tự là số
        if c.isdigit():
            # Cập nhật số hiện tại bằng cách nhân 10 và cộng ký tự
            num = num * 10 + int(c)
        # Nếu ký tự không phải là số
        else:
            # Nếu số hiện tại khác 0
            if num != 0:
                # Tìm ước nguyên tố lớn nhất của số hiện tại
                factor = largest_prime_factor(num)
                # Nếu ước nguyên tố lớn hơn khóa
                if factor > key:
                    # Cập nhật khóa
                    key = factor
                # Đặt lại số hiện tại bằng 0
                num = 0
    # Nếu số hiện tại khác 0
    if num != 0:
        # Tìm ước nguyên tố lớn nhất của số hiện tại
        factor = largest_prime_factor(num)
        # Nếu ước nguyên tố lớn hơn khóa
        if factor > key:
            # Cập nhật khóa
            key = factor
    # Trả về khóa
    return key

# Đọc dữ liệu từ file input
with open('BLAZI.INP', 'r') as file:
    S = file.readline().strip()

# Tìm khóa
key = find_key(S)

# Ghi kết quả vào file output
with open('BLAZI.OUT', 'w') as file:
    file.write(str(key))

# Hàm để tìm số lượng nhiều nhất các căn nhà mà công ty có thể bán
def max_houses(N, M, k, a, b):
    # Sắp xếp các giá của căn nhà và khách hàng theo thứ tự tăng dần
    a.sort()
    b.sort()
    # Khởi tạo biến để lưu số lượng căn nhà đã bán
    count = 0
    # Khởi tạo biến để lưu chỉ số của khách hàng hiện tại
    j = 0
    # Lặp qua các giá của căn nhà
    for i in range(N):
        # Nếu chỉ số của khách hàng vượt quá số lượng khách hàng
        if j >= M:
            # Dừng vòng lặp
            break
        # Nếu giá của căn nhà nằm trong khoảng chấp nhận của khách hàng
        if b[j] - k <= a[i] <= b[j] + k:
            # Tăng số lượng căn nhà đã bán lên 1
            count += 1
            # Tăng chỉ số của khách hàng lên 1
            j += 1
        # Nếu giá của căn nhà nhỏ hơn khoảng chấp nhận của khách hàng
        elif a[i] < b[j] - k:
            # Bỏ qua căn nhà này
            continue
        # Nếu giá của căn nhà lớn hơn khoảng chấp nhận của khách hàng
        else:
            # Tăng chỉ số của khách hàng lên 1, tăng số lượng căn nhà đã bán lên 1
            j += 1
            count += 1
    # Trả về số lượng căn nhà đã bán
    return count

# Đọc dữ liệu từ file input
with open('HOUSE.INP', 'r') as file:
    N, M, k = map(int, file.readline().split())
    a = list(map(int, file.readline().split()))
    b = list(map(int, file.readline().split()))

# Tìm số lượng nhiều nhất các căn nhà mà công ty có thể bán
result = max_houses(N, M, k, a, b)

# Ghi kết quả vào file output
with open('HOUSE.OUT', 'w') as file:
    file.write(str(result))

# Hàm để giải bài toán chọn quà
def solve(N, K, M, P):
    # Khởi tạo mảng F[j] là tổng giá trị lớn nhất khi chọn các sản phẩm khác nhau sao cho tổng khối lượng bằng j
    F = [0 for j in range(K + 1)]
    # Gán F[0] bằng 1
    F[0] = 1
    # Duyệt qua các sản phẩm
    for i in range(N):
        # Duyệt ngược qua các khối lượng từ K đến M[i]
        for j in range(K, M[i] - 1, -1):
            # Kiểm tra xem F[j - M[i]] có bằng 0 hay không
            if F[j - M[i]] != 0:
                # Nếu không bằng 0, thì cập nhật F[j] bằng max của F[j] và F[j - M[i]] + P[i]
                F[j] = max(F[j], F[j - M[i]] + P[i])
    # Trả về kết quả là F[K]
    return F[K]

# Đọc dữ liệu từ file input
with open('DQCN.INP', 'r') as file:
    N, K = map(int, file.readline().split())
    M, P = zip(*[map(int, line.split()) for line in file])

# Tìm tổng giá trị lớn nhất của các sản phẩm được chọn sao cho tổng khối lượng bằng K
result = solve(N, K, M, P)

# Ghi kết quả vào file output
with open('DQCN.OUT', 'w') as file:
    if result == 0:
        file.write("NONE\n")
    else:
        file.write(str(result-1) + "\n")