Khởi nghiệp | Đề thi HSG tin 12 Nghệ An | năm học 2022 - 2023

Thứ bảy - 06/05/2023 04:25
In ra
Đóng cửa sổ này

Câu 4. Khởi nghiệp - Đề thi HSG tin 12 tỉnh Nghệ An năm 2022-2023

Đức là vừa tốt nghiệp đại học loại xuất sắc chuyên ngành Công Nghệ Thông tin tại một trường đại học danh tiếng. Đức đã tìm hiểu, lên kế hoạch khởi nghiệp từ thời đang là sinh viên và nay là thời điểm mà Đức sẽ thực hiện kế hoạch đó. Qua tìm hiểu, Đức biết được n công ty tiềm năng và có liên quan đến công việc làm của mình nên sẽ hợp tác làm việc với n công ty này. Các công ty được đánh số thứ tự lần lượt là 1, 2, 3, ....n. Điều kiện để hợp tác với công ty thứ i (i= 1, 2, ...,n) là: Đức đã hợp tác được với ít nhất a_i công ty khác (trong n − 1 công ty còn lại) hoặc là mua một món quà tinh thân có giá trị b_i (đồng) để tặng cho công ty thứ i.

Ban đầu, Đức chưa hợp tác được với công ty nào. Hãy tính chi phí ít nhất để Đức có thể hợp tác với tất cả n công ty.
Dữ liệu cho trong file văn bản KhoiNghiep.Inp gồm:

Dòng 1 ghi số nguyên dương n là số công ty.
n dòng tiếp theo, dòng thứ i ghi hai số nguyên a_i,b_i(1≤i≤n;0≤a_i ≤n; 0 ≤b_i ≤10^4)

Kết quả ghi ra file văn bản KhoiNghiep.Out gồm một số nguyên duy nhất là chi phí ít nhất để Đức có thể hợp tác với tất cả n công ty.

Giải:

# Đọc dữ liệu từ file input
with open("KhoiNghiep.Inp", "r") as f:
    n = int(f.readline().strip())
    companies = []
    for i in range(n):
        a, b = map(int, f.readline().strip().split())
        companies.append((a, b))

# Sắp xếp các công ty theo giá trị bi tăng dần
companies.sort(key=lambda x: x[1])

# Khởi tạo danh sách công ty đã hợp tác
partnered = [False] * n

e = 0
total_cost = 0
i = 0
for i in range(n):
    if not partnered[i]:
        if e >= companies[i][0]:  # Kiểm tra công ty đang xét có free không nếu đuợc thì vào.
            partnered[i] = True
            e += 1
        else:  # Kiểm tra các công ty còn lại có được free không.
            j = i + 1
            while j < n:
                if e >= companies[j][0] and not partnered[j]:
                    partnered[j] = True
                    e += 1
                    j = i  # Nếu được vào free thì kiểm tra lại từ i đến hết vì e đã thay đổi.
                    continue
                else:
                    j += 1
            if not partnered[i]: # Thoát khỏi vòng while nên không còn có công ty hợp tác free nữa.
                total_cost += companies[i][1]
                partnered[i] = True
                e += 1
with open('KhoiNghiep.Out', 'w') as f:
    f.write(str(total_cost))

Giải thích:

Trong đoạn code trên, ta sử dụng một vòng lặp while để kiểm tra từng công ty. Nếu công ty đó đã được hợp tác, ta tăng giá trị của i lên 1 và tiếp tục kiểm tra công ty tiếp theo. Nếu công ty đó chưa được hợp tác, ta kiểm tra xem có thể hợp tác free hay không. Nếu có, ta đánh dấu công ty đó đã hợp tác và kiểm tra trong các công ty chưa được hợp tác xem còn công ty nào có thể hợp tác free không. Nếu không có, ta tìm công ty có giá trị bi nhỏ nhất để hợp tác. Nếu không có công ty nào có thể hợp tác, ta tăng tổng chi phí lên giá trị bi của công ty hiện tại và đánh dấu công ty đó đã hợp tác.

Thuật toán mà tôi đã sử dụng để giải quyết bài toán này là một phương pháp tham lam. Cụ thể, ta sẽ kiểm tra từng công ty để xem có thể hợp tác free không. Nếu không thể hợp tác free, ta giải quyết bài toán bằng cách tìm công ty có giá trị bi nhỏ nhất để hợp tác.

Thuật toán này được gọi là phương pháp tham lam vì ta luôn chọn công ty có giá trị bi nhỏ nhất để hợp tác, mà không đánh giá tác động của quyết định đó đến việc hợp tác với các công ty khác ở những bước sau. Tuy nhiên, trong bài toán này, phương pháp tham lam này lại cho kết quả chính xác, mà không cần tìm cách tối ưu toàn bộ quy trình hợp tác.

Tác giả: admin

BÀI TẬP Ở NHÀ

Khởi nghiệp | Đề thi HSG tin 12 Nghệ An | năm học 2022 - 2023

Giải:

Giải thích: