Solution Giao lưu Tin học trẻ Mở rộng 2023 Lần 1 - Bảng B

Em trang trí

Fact: toàn bộ học sinh lớp 9A, 9B đều không thể AC bài này.

Đong dầu

Đề bài

Cho bể dầu lớn vô hạn. Cần đong \(n\) lít dầu bằng một trong hai loại thao tác:

• Thêm \(2\ell\) hoặc \(3 \ell\) dầu
• Bớt \(2\ell\) hoặc \(3 \ell\) dầu

Trâu

Gọi số can \(2\ell\) dầu cần dùng là \(x\), số can \(3\ell\) cần dùng sẽ là \(\dfrac{n-2x}{3}\). Nếu số can là nguyên dương, ta tìm tổng số can nhỏ nhất.

int answer = 1e9;
for (int x = 0; x * 2 <= n; x++){
    int remain = n - 2 * x;
    if (remain % 3 == 0){
        int y = remain / 3;
        answer = min(answer, x + y);
    }
}

Thuật chuẩn

Dùng càng nhiều can \(3\ell\) nhất có thể.
\(\Rightarrow\) không dư, hoặc dư \(1\ell\), hoặc dư \(2\ell\)

• Nếu còn dư \(2\ell\): dùng thêm 1 can \(2\ell\)
• Nếu còn dư \(1\ell\): bớt một can \(3\ell\) và thay bằng 2 can \(2\ell\).

Trường hợp đặc biệt: \(n = 1\) \(\Rightarrow\) không thể bớt can nào được
\(\Rightarrow\) \(3-2 = 1\), tức múc vào 3\(\ell\) và bỏ ra \(2\ell\), tức đáp án là 2 thao tác.

Nếu không xử lý trường hợp này thì chỉ ăn được \(24.75/25\) điểm

Biến đổi

Đề bài

Cho hai số \(a\) và \(b\). Mỗi lần biến đổi, ta lấy số lớn trừ bớt cho số bé. Đếm số lần biến đổi tối thiểu để đưa một trong hai số về \(0\).

Trâu

Đề bảo gì làm nấy

int answer = 0;
while (a > 0 and b > 0){
    answer++;
    if (a > b)
        a -= b;
    else
        b -= a;
}
cout << answer;

Thuật chuẩn

Nhận thấy, thuật toán được nhắc trong đề chính là thuật toán Euclid.

Trong lúc thực hiện thuật toán, sẽ có trường hợp số \(a\) cực lớn, và \(b\) cực nhỏ, khi trừ nhiều lần sẽ rất tốn thời gian. Vì vậy, ta gom các phép trừ lại thành một phép chia duy nhất.

\(a \div b = q\) dư \(r\) \(\Rightarrow\) \(a = bq + r\) \(\Rightarrow\) diễn ra \(q\) phép trừ, và sau khi trừ thì \(a = r\).

int answer = 0;
while (a > 0 and b > 0){
    if (a < b) swap(a, b); // số nào là a, số nào là b không quan trọng
    answer += a / b;
    a = a % b;
}
cout << answer;

Avatar

Subtask 1: \(a[i] = b[j] = 1\)

Mỗi dũng sĩ giết được một con.
Đáp án là min(m, n).

Subtask 2: \(b[1] = b[2] = \dots = b[m]\)

Đặt \(x = b[1]\).
Các dũng sĩ chỉ giết được robot có sức mạnh \(\le x\).

Vì thế, ta đếm số lượng robot có sức mạnh nhỏ hơn hoặc bằng \(x\), và nếu có quá \(m\) robot thỏa mãn thì ta chỉ giết \(m\) con.

int x = b[1];
int answer = 0;
for (int i = 1; i <= n; i++)
    answer += a[i] <= x;
answer = min(answer, m);
cout << answer;

Subtask 3

Sắp xếp \(a, b\) theo thứ tự tăng dần.

Nhận xét: Khi đánh, để diệt nhiều con nhất, ta ưu tiên bốc những con robot yếu nhất, và dùng những chiến binh mạnh nhất.

Cách 1

Nếu người Na-vi thứ \(j\) đánh được robot thứ \(i\), tức \(b[j] \ge a[i]\)
Thì người Na-vi thứ \(j + 1\) cũng đánh được robot thứ \(i\), vì \(b[j+1] \ge b[j] \ge a[i]\)
Đồng thời người Na-vi thứ \(j\) cũng đánh bại được robot thứ \(i-1\), vì \(b[j] \ge a[i] \ge a[i - 1]\).

Vì vậy, với mỗi người Na-vi thứ \(j\), ta tìm robot \(i\) lớn nhất sao cho \(b[j] \ge a[i]\).
\(\Rightarrow\) chỉ những người từ \(j \rightarrow n\) đánh được robot \(1 \rightarrow i\) \(\Rightarrow\) giết được \(\min(n-j+1, i)\) con robot.

Điều này có thể tính được bằng chặt nhị phân, hoặc hai con trỏ (vì \(j\) tăng thì \(i\) cũng tăng).

// sort mảng a và b
int i = 0;
int answer = 0;
for (int j = 1; j <= m; j++){
    while (i != n and a[i + 1] <= b[j])
        i++; // nếu đánh được thêm 1 robot thì tăng i.
    
    // ta sẽ thử cho người j->n đánh i robot đầu
    int outcome = min(n - j + 1,   i  );
        //             số người  robot
    answer = max(answer, outcome);
}

Cách 2

Hệ quả của nhận xét: nếu đáp án là \(x\), thì ta cứ lấy \(x\) người Na-vi mạnh nhất chọi với \(x\) con robot yếu nhất.
\(\Rightarrow\) ta sẽ xử lý \(a[1\rightarrow x]\) và \(b[m-x+1\rightarrow m]\), so sánh lần lượt từng phần tử tương ứng.
Hiển nhiên, nếu diệt được \(x\) con thì diệt được \(x-1\) con.

Vì vậy, ta chặt nhị phân đáp án.

bool check(int x){
    for (int i = 1; i <= x; i++)
        if (a[i] > b[m - i + 1])
            return false;
    return true;
}

int lo = 1, hi = min(m, n), ans = 0;
while (lo <= hi){
    int mid = (lo + hi) / 2;
    if (check(mid))
        ans = mid, lo = mid + 1;
    else
        hi = mid - 1;
}
cout << ans;

Chọn dãy

Subtask 2: \(n = k\)

Ta suy ra chỉ được chọn một phần tử \(\Rightarrow\) chọn phần tử lớn nhất mảng \(A\).

Subtask 3: \(A[1] = A[2] = \dots = A[n]\)

Ta sẽ tìm cách bốc nhiều phần tử nhất có thể.
Số phần tử bốc được sẽ là \(\dfrac{n}{k}\), cộng thêm \(1\) nếu \(n\) chia \(k\) có dư.

Subtask 1: \(n, k \le 20\)

Ta đệ quy quay lui để thử toàn bộ các chọn \(n\) phần tử.
Để thuận tiện cho việc xử lý các subtask sau, ta gọi hàm dqql(i, sum) là việc thử xử lý các phần tử từ \(1\rightarrow i\), và các phần từ được bốc trước đó (nằm trong khoảng từ \(i+1\rightarrow n\) đã qua) thì có tổng là \(sum\).

int answer = 0;
void dqql(int i, int sum){
    if (i < 1){ // không bốc được nữa
        answer = max(answer, sum);
        return;
    }
    // có bốc i 
    // => tổng tăng lên a[i], thằng tiếp theo được bốc <= i-k
    dqql(i - k, sum + a[i]);
        
    // không bốc i
    // thằng tiếp theo bốc có thể là từ ngay i-1 rồi, tổng không đổi.
    dqql(i - 1, sum);
}

Subtask 5

Nhìn vào code của sub2, ta dễ dàng suy ra được công thức quy hoạch động:

• Nếu chỉ gồm phần tử \(a[i]\), đáp án là \(a[i]\)
• Nếu không chọn phần tử \(a[i]\), ta xem đáp án của \(i-1\) thằng còn lại tốt nhất là bao nhiêu, tức \(f[i - 1]\)
• Nếu \(i\le k\), và ta chọn phần tử \(i\), thì bỏ qua rất nhiều phần tử khoảng cách không đủ xa, chỉ quan tâm \(1 \rightarrow i-k\) \(\Rightarrow\) \(f[i - k] + a[i]\)

\(f[i] = \max(a[i], f[i - 1], f[i - k] + a[i])\) (nếu \(i \ge k\))

Subtask 4

Có thể một số bạn đi theo hướng này:
\(f[i]\) là cách chọn tốt nhất trong \(i\) phần tử đầu và có chọn \(i\).
\(\Rightarrow f[i] = a[i] + \max\limits_{1 \le j \le i - k}f[j]\)

Ta cũng có thể đưa về sub5 một cách dễ dàng bằng cách đặt \(g[j] = \max\limits_{1 \le j \le i - k}f[j] = \max(g[j - 1], f[j])\)