Olympic 10 Thành phố 2020 - 2021¶

Câu 1: Quảng cáo¶

Đề bài¶

Siêu thị thường có quảng cáo giới thiệu những mặt hàng mới. Để phân bố thời gian quảng cáo sao cho có hiệu quả, họ ghi nhận thời điểm đi vào và thời điểm đi ra khỏi siêu thị của từng khách hàng và cho rằng phân bố này sẽ không thay đổi trong các ngày tiếp theo.

Thời điểm bắt đầu của mỗi đoạn quảng cáo là một số nguyên. Mỗi đoạn quảng cáo sẽ kết thúc ngay trước khi đoạn quảng cáo tiếp theo bắt đầu. Nếu đoạn quảng cáo xuất hiện vào đúng thời điểm khách hàng bước ra khỏi siêu thị thì xem như khách hàng vẫn nghe được quảng cáo này. Thời điểm đi vào siêu thị của khách hàng luôn nhỏ hơn thời điểm đi ra và là các số nguyên.

Họ muốn phân bố thời gian các đoạn âm thanh quảng cáo sao cho hai quảng cáo khác nhau không diễn ra đồng thời (tức là vào một thời điểm chỉ có một quảng cáo) và mỗi khách hàng đều được nghe ít nhất hai quảng cáo khác nhau. Mặt khác, họ cũng muốn các nhân viên bị ít ảnh hưởng bởi những âm thanh này nên đề xuất số lượng các đoạn quảng cáo là ít nhất có thể.

Yêu cầu: Bạn hãy viết chương trình phân bố thời gian các đoạn quảng cáo sao cho đạt được các yêu cầu nói trên.

Đầu vào: DOANQC.INP

Dòng đầu tiên ghi một số nguyên \(N\) cho biết số lượng khách hàng đến siêu thị trong một ngày \((1 \le N \le 3000)\).
\(N\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(A_i\) và \(B_i\) cho biết thời điểm đi vào và thời điểm đi ra của mỗi khách hàng \((0 \lt A_i \lt B_i \lt 10^6)\).

Đầu ra: DOANQC.OUT

Dòng đầu tiên ghi một số nguyên \(K\) cho biết số lượng các đoạn quảng cáo trong một ngày.
Dòng tiếp theo ghi \(K\) số nguyên cho biết thời điểm xuất hiện của các đoạn quảng cáo theo thứ tự tăng dần.

Lưu ý:

Các số trên cùng một dòng ghi cách nhau bởi ít nhất một khoảng trắng.
Nếu có nhiều kết quả thì đưa ra một kết quả bất kỳ trong số chúng.

Ví dụ:

DOANQC.INP	DOANQC.OUT
5 1 8 8 12 1 8 1 8 20 21	4 4 8 12 20 21

Cách giải đề xuất¶

Ý tưởng chính

Khi một khách hàng đi vào siêu thị, họ sẽ nghe được quảng cáo đang phát sẵn trước đó. Đây là lần nghe quảng cáo thứ nhất của khách hàng này.

Mà yêu cầu đề bài là mỗi khách hàng phải nghe ít nhất hai quảng cáo.

Cho nên, ta cần xét thời điểm đi ra của mỗi khách hàng: có nên phát quảng cáo vào thời điểm đi ra này hay không.

Có hai trường hợp:

Trường hợp 1: thời điểm vào và ra đều xảy ra sau thời điểm phát quảng cáo mới nhất (latest_ad).

Để bảo đảm khách hàng nghe được ít nhất hai quảng cáo, ta phải phát quảng cáo vào thời điểm họ đi ra.

Trường hợp 2: thời điểm phát quảng cáo mới nhất nằm ở giữa thời điểm vào và thời điểm ra.

Ở trường hợp này, khách hàng đã nghe được ít nhất hai quảng cáo, nên ta không cần phát thêm quảng cáo ở thời điểm họ đi ra.

Viết chương trình

0. Khai báo các biến liên quan.

C++Python

int n;

struct interval
{
    int checkin;
    int checkout;
};

// mỗi phần tử là một cặp số cho biết thời điểm vào và ra {checkin, checkout}
vector<interval> customers;

// mảng lưu các thời điểm phát quảng cáo
vector<int> schedule;

n = 0

# mỗi phần tử là một cặp số cho biết thời điểm vào và ra {checkin, checkout}
customers = []

# mảng lưu các thời điểm phát quảng cáo
schedule = []

1. Ta phải phát quảng cáo vào thời điểm vào của khách hàng đầu tiên, tức thời điểm vào nhỏ nhất trong số toàn bộ khách hàng.

C++Python

    // Tìm khách hàng đầu tiên, tức thời điểm đi vào siêu thị nhỏ nhất
    vector<interval>::iterator first_customer = min_element(customers.begin(), customers.end(), compare_checkin); // (1)!

    // Lưu thời điểm vào nhỏ nhất vào lịch
    schedule.push_back((*first_customer).checkin);

Hàm compare_check_out() dùng để tìm thời điểm nhỏ nhất đi vào siêu thị, tức thời điểm vào của khách hàng đầu tiên.
43 44 45 46
bool compare_checkin(const interval &a, const interval &b) { return a.checkin < b.checkin; }

    # Lấy thời điểm vào của khách hàng đầu tiên
    min_checkin = min(customers, key=lambda t: t[0])[0]

    # Lưu thời điểm vào nhỏ nhất vào lịch
    schedule.append(min_checkin)

2. Sắp xếp mảng customers theo thứ tự tăng dần của thời điểm ra.

C++Python

    sort(customers.begin(), customers.end(), compare_checkout);

Trong đó, hàm compare_check_out() dùng để sắp xếp mảng customers theo thời điểm ra.

bool compare_checkout(const interval &a, const interval &b)
{
    return a.checkout < b.checkout;
}

    customers.sort(key=lambda t: t[1])

3. Phân bố lịch phát quảng cáo.

Duyệt từng khách hàng c trong mảng customers đã sắp xếp:

Nếu thời điểm vào xảy ra sau thời điểm phát quảng cáo mới nhất (lưu trong biến latest_ad) thì ta nạp thời điểm ra vào lịch phát (lưu trong biến schedule).

C++Python

    // biến latest_ad lưu thời điểm mới nhất phát quảng cáo
    int latest_ad = -1;

    int checkin, checkout;

    // Duyệt từng khách hàng trong mảng customers đã sắp xếp
    for (interval c : customers)
    {
        // Nếu thời điểm vào xảy ra sau thời điểm phát quảng cáo mới nhất
        if (latest_ad <= c.checkin)
        {
            // thì phát quảng cáo tại thời điểm ra
            schedule.push_back(c.checkout);

            // Ghi nhận thời điểm phát quảng cáo mới nhất
            latest_ad = c.checkout;
        }
    }

    # biến latest_ad lưu thời điểm mới nhất phát quảng cáo
    latest_ad = -1

    # Duyệt từng khách hàng trong mảng customers đã sắp xếp
    for c in customers:
        # Nếu thời điểm vào xảy ra sau thời điểm phát quảng cáo mới nhất
        if latest_ad <= c[0]:
            # thì phát quảng cáo tại thời điểm ra
            schedule.append(c[1])

            # Ghi nhận thời điểm phát quảng cáo mới nhất
            latest_ad = c[1]

Về output của bài toán

Output của chương trình này khác với output của đề bài. Cụ thể, output là:

4
1 8 12 21

Giải thích:

Có ba khách hàng cùng là (1, 8):

Đi vào tại thời điểm 1: ta phát quảng cáo tại thời điểm 1 để họ nghe lần thứ nhất.
Đi ra tại thời điểm 8: ta phát quảng cáo tại thời điểm 8 để họ nghe lần thứ hai.

Khách hàng (8, 12):

Đi vào tại thời điểm 8: họ nghe quảng cáo lần thứ nhất tại thời điểm 8.
Đi ra tại thời điểm 12: ta phát quảng cáo tại thời điểm 12 để họ nghe lần thứ hai.

Khách hàng (20, 21):

Đi vào tại thời điểm 20: họ nghe được đoạn quảng cáo phát từ thời điểm 12, đây là lần nghe thứ nhất.
Đi ra tại thời điểm 21: ta phát quảng cáo tại thời điểm 21 để họ nghe lần thứ hai.

Output này có số lần phát quảng cáo ít hơn so với output của đề bài, đáp ứng được yêu cầu của bài toán.

Mã nguồn¶

Code đầy đủ được đặt tại:

GitHub

Câu 2: Chia phô mai¶

Đề bài¶

Hai chú gấu con đã tìm được trong rừng hai miếng phô mai có khối lượng tương ứng là \(a\) và \(b\) gram, với \(a\) và \(b\) là số nguyên. Hai chú gấu tham lam đến nỗi muốn đánh nhau để tranh phần miếng phô mai nhiều hơn.

Một con cáo đi đến và nói: "Các chú hãy đợi đấy, tôi sẽ giúp các chú chia các miếng phô mai bằng nhau!". "Đồng ý, nhưng làm sao chia được?" - một chú gấu hào hứng nói.

"Rất đơn giản, nếu khối lượng miếng phô mai nào đó được chia đều thành hai phần thì tôi sẽ ăn một phần. Nếu khối lượng miếng phô mai được chia đều làm ba thì tôi sẽ ăn hai phần ba. Còn nếu chia đều làm năm thì tôi sẽ ăn bốn phần năm. Như vậy tôi sẽ ăn một ít và hai miếng phô mai sẽ bằng nhau" - con cáo nói.

Hai chú gấu nghi ngờ con cáo chơi khăm mình nhưng lúc này chúng không thể tự chia hai miếng phô mai bằng nhau được nên đành phải đồng ý với lời đề nghị của cáo nhưng với một điều kiện: Cáo phải chia sao cho hai miếng phô mai bằng nhau nhanh nhất và khối lượng của chúng phải luôn là số nguyên.

Yêu cầu: Bạn hãy tìm số thao tác ít nhất đã mô tả ở trên sao cho cáo có thể chia thành hai miếng phô mai bằng nhau.

Đầu vào: PHOMAI.INP

Gồm một dòng duy nhất ghi hai số nguyên \(a\) và \(b\) cách nhau một khoảng trắng \((1 \le a, b \le 10^9)\).

Đầu ra: PHOMAI.OUT

Gồm một dòng duy nhất ghi một số cho biết:

Trường hợp con cáo nói dối và không thể chia đều được, ghi số -1.
Ngược lại, ghi số thao tác ít nhất. Trong trường hợp hai miếng phô mai ban đầu bằng nhau thì ghi số 0.

Ví dụ:

PHOMAI.INP	PHOMAI.OUT
15 20	3

Giải thích:

Lần 1: Cáo chia miếng 15g thành 3 phần, mỗi phần bằng 5g. Cáo ăn 2 phần, miếng còn lại bằng 5g.
Lần 2: Cáo chia miếng 20g thành 2 phần, mỗi phần bằng 10g. Cáo ăn 1 phần, miếng còn lại bằng 10g.
Lần 3: Cáo chia tiếp miếng 10g thành 2 phần, mỗi phần bằng 5g. Cáo ăn 1 phần, miếng còn lại bằng 5g.

Sau 3 lần chia, Cáo có 2 miếng bằng nhau là 5g. Vậy kết quả là 3. Không có cách chia nào khác nhanh hơn 3 lần.

PHOMAI.INP	PHOMAI.OUT
14 8	-1
4 4	0

Cách giải đề xuất¶

Ý tưởng chính

Vì mỗi miếng phô mai có thể được chia 2, 3 và 5 nhiều lần, ta có:

\[ \begin{aligned} a = 2^{x1} . 3^{y1} . 5^{z1} . remaining\_a \\ b = 2^{x2} . 3^{y2} . 5^{z2} . remaining\_b \end{aligned} \]

Trường hợp 1: phần dư của a và phần dư của b không bằng nhau, nghĩa là không có cách chia nào.

Trường hợp 2: phần dư bằng nhau.

Lúc này, để đạt được số thao tác chia ít nhất, ta tính chênh lệch giữa các số mũ.

Bởi vì:

Gọi \(c\) là chênh lệch của các số mũ của cơ số 2: \(c = | x1 - x2 |\).

Cáo chỉ cần chia một trong hai miếng phô mai \(c\) lần thì số mũ (của cơ số 2) của hai miếng phô mai \(a\) và \(b\) sẽ bằng nhau.

Thực hiện tương tự như vậy cho số mũ của 3 và số mũ của 5.

Viết chương trình

0. Tạo cấu trúc factors để lưu trữ các số mũ và phần dư khi phân tích a và b.

C++Python

struct factors
{
    int x = 0;         // số mũ của 2
    int y = 0;         // số mũ của 3
    int z = 0;         // số mũ của 5
    int remaining = 0; // phần dư sau khi phân tích lũy thừa
};

class factors:
    def __init__(self, x=0, y=0, z=0, remaining=0):
        self.x = x                  # số mũ của 2
        self.y = y                  # số mũ của 3
        self.z = z                  # số mũ của 5
        self.remaining = remaining  # phần dư sau khi phân tích lũy thừa 

1. Viết hàm factorize() dùng để phân tích một số n thành tích của các thừa số nguyên tố 2, 3 và 5.

C++Python

factors factorize(int n)
{
    factors f;

    // Chia 2 nhiều lần để lấy số mũ của 2
    while (n % 2 == 0)
    {
        n /= 2;
        f.x += 1;
    }

    // Chia 3 nhiều lần để lấy số mũ của 3
    while (n % 3 == 0)
    {
        n /= 3;
        f.y += 1;
    }

    // Chia 5 nhiều lần để lấy số mũ của 5
    while (n % 5 == 0)
    {
        n /= 5;
        f.z += 1;
    }

    // Phần dư còn lại của n
    f.remaining = n;

    return f;
}

def factorize(n):
    f = factors()

    # Chia 2 nhiều lần để lấy số mũ của 2
    while n % 2 == 0:
        n /= 2
        f.x += 1

    # Chia 3 nhiều lần để lấy số mũ của 3
    while n % 3 == 0:
        n /= 3
        f.y += 1

    # Chia 5 nhiều lần để lấy số mũ của 5
    while n % 5 == 0:
        n /= 5
        f.z += 1

    # Phần dư còn lại của n
    f.remaining = n

    return f

2. Gọi hàm factorize() để thực hiện phân tích a và b.

Sau khi phân tích, nếu phần dư không bằng nhau thì trả về -1, không có cách chia để hai miếng phô mai bằng nhau.

Ngược lại, nếu phần dư bằng nhau thì tính tổng các chênh lệch giữa các số mũ. Đây chính là số cách chia ít nhất cần tìm.

C++Python

void process()
{
    // Phân tích a và b
    factors fa = factorize(a);
    factors fb = factorize(b);

    // Nếu phần dư không bằng nhau thì có nghĩa là không có cách chia
    if (fa.remaining != fb.remaining)
    {
        result = -1;
        return;
    }

    // Ngược lại, nếu phần dư bằng nhau thì tính tổng các chênh lệch giữa các số mũ
    result = abs(fa.x - fb.x) + abs(fa.y - fb.y) + abs(fa.z - fb.z);
}       

def process():
    global a, b, result

    # Phân tích a và b
    fa = factorize(a)
    fb = factorize(b)

    # Nếu phần dư không bằng nhau thì có nghĩa là không có cách chia
    if fa.remaining != fb.remaining:
        result = -1
        return

    # Ngược lại, nếu phần dư bằng nhau thì tính tổng các chênh lệch giữa các số mũ
    result = abs(fa.x - fb.x) + abs(fa.y - fb.y) + abs(fa.z - fb.z)

Mã nguồn¶

Code đầy đủ được đặt tại:

GitHub

Olympic 10 Thành phố 2020 - 2021¶

Câu 1: Quảng cáo¶

Đề bài¶

Cách giải đề xuất¶

Mã nguồn¶

Câu 2: Chia phô mai¶

Đề bài¶

Cách giải đề xuất¶

Mã nguồn¶

Tags