# 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])$