# Đề HSG9 - BRVT - 2015: Editorial

## Bài 1: Thừa kế (7 điểm)

Tính tổng các số chẵn và tổng các số lẻ trong đoạn $\left[ a, b \right]$ $\left( a, b \le 10^9 \right)$

:::info
:information_source: Ký hiệu toán học cần biết:

$\lceil \frac{a}{b} \rceil$: Phép tính $\frac{a}{b}$ làm tròn lên.
$\lfloor \frac{a}{b} \rfloor$: Phép tính $\frac{a}{b}$ làm tròn xuống

${\sum_{i=a}^b i}$ : Tổng các số từ a đến b
:::

### Brute - force:

Duyệt tuần tự từ a đến b và cộng các số chẵn hoặc lẻ vào tổng tương ứng.

Độ phức tạp thời gian: $O \left( b - a + 1 \right)$.

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int sumOdd = 0, sumEven = 0;
    for (int i = a; i <= b; i++) {
        if (i % 2 == 0) {
            sumEven += i;
        }
        else {
            sumOdd += i;
        }
    }

    if (sumEven > sumOdd) {
        cout << 1 << "\n";
    }
    else {
        cout << 2 << "\n";
    }

    cout << abs(sumEven - sumOdd);
    
    return 0;
}

:::

### Accepted:

Xét đoạn $\left[ a, b \right]$, đặt:

- $sE$: Tổng các số chẵn.
- $sO$: Tổng các số lẻ.
- $sTotal$: Tổng các số.

Ta có ==$sO = sTotal - sE$==. Vậy chỉ cần tính **$sE$** và **$sTotal$**!

$$
\begin{flalign}
sTotal
&= \sum_{i=a}^b i \\
&= \sum_{i=1}^b i - \sum_{i=1}^{a-1} i \\
&= \frac{b(b+1)}{2} - \frac{(a-1)a}{2}
\end{flalign}
$$

>Tổng các số từ $a$ đến $b$ bằng tổng các số từ $1$ đến $b$ trừ đi tổng các số từ $1$ đến $a-1$

Những số chẵn trong đoạn $\left[ a, b \right]$ có thể viết lại thành $2i$ với $\lceil \frac{a}{2} \rceil \le i \le \lfloor \frac{b}{2} \rfloor$

$$
\begin{flalign}
sE
&= \sum_{i=\lceil \frac{a}{2} \rceil}^{\lfloor \frac{b}{2} \rfloor} 2i \\
&= 2 * \sum_{i=\lceil \frac{a}{2} \rceil}^{\lfloor \frac{b}{2} \rfloor} i \\
&= 2 * \left( \sum_{i=1}^{\lfloor \frac{b}{2} \rfloor} i - \sum_{i=1}^{\lceil \frac{a}{2} \rceil - 1} i \right) \\
&= 2 * \left( \frac{{\lfloor \frac{b}{2} \rfloor}({\lfloor \frac{b}{2} \rfloor}+1)}{2} - \frac{({\lceil \frac{a}{2} \rceil}-1){\lceil \frac{a}{2} \rceil}}{2} \right)
\end{flalign}
$$

>sE được tính bằng cách lấy tổng các số từ $\lceil \frac{a}{2} \rceil$ đến $\lfloor \frac{b}{2} \rfloor$ nhân đôi lên

Sau khi đã tính được $sE$ và $sTotal$, ta tính $sO$. Như vậy, bài toán đã được giải quyết!

>VD: Trong đoạn $\left[ 3, 10 \right]$ có những số chẵn sau: $4, 6, 8, 10$.
>Tương ứng với: $2*2, 2*3, 2*4, 2*5$.
>
>$sTotal = \frac{10*(10+1)}{2} - \frac{(3-1)*3}{2} = 52$
>
>${\lfloor \frac{a}{2} \rfloor} = {\lfloor \frac{10}{2} \rfloor} = 5$
>${\lceil \frac{b}{2} \rceil} = {\lceil \frac{3}{2} \rceil} = 2$
>
>$sE = 2 * \left( \frac{5*(5+1)}{2} - \frac{(2-1)*2}{2} \right) = 28$
>
>$sO = sTotal - sE = 52 - 28 = 24$

Độ phức tạp thời gian: $O \left( 1 \right)$.

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    
    long long l = (a + 1) / 2, r = b / 2;

    //Lấy max với 0 phòng trường hợp l = r
    long long sE = max(0LL, (r * (r + 1) / 2 - l * (l - 1) / 2) * 2);

    long long sTotal = b * (b + 1) / 2 - a * (a - 1) / 2;

    long long sO = sTotal - sE;

    if (sE > sO) {
        cout << 1 << "\n";
    }
    else {
        cout << 2 << "\n";
    }

    cout << abs(sE - sO);
    
    return 0;
}

:::

## Bài 2: Chọn quà (7 điểm)

Cho dãy số nguyên dương $A_1, A_2, A_3, \dots, A_n$ $\left( n \le 10^6 \right)$.
Đếm số cách chọn cặp $A_i, A_j$ $\left( i < j \right)$ sao cho **tổng các số còn lại là chẵn**.

### Brute - force:

Tính trước tổng của dãy số và lưu vào biến $sum$.

Duyệt tuần tự để cố định $A_i$, tương ứng với mỗi giá trị lại duyệt tuần tự một lần nữa để tìm $A_j$. Kiểm tra nhanh cặp số hiện tại có thỏa mãn hay không bằng cách kiểm tra $sum - \left( A_i + A_j \right)$ có chẵn hay không.

Độ phức tạp thời gian: $O \left( b - a + 1 \right)$.

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += A[i];
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if ( (sum - (A[i] + A[j]) ) % 2 == 0) {
                res++;
            }
        }
    }

    cout << res;
    
    return 0;
}

:::

### AC:

Nhận thấy tính chẵn lẻ của $sum - (A_i + A_j)$ phụ thuộc vào tính chẵn lẻ của $(A_i + A_j)$ do $sum$ đã cố định, ta có thể chia ra các trường hợp như sau:

#### Trường hợp 1: $sum$ chẵn $\to$ $\left( A_i + A_j \right)$ phải chẵn.

Bài toán quy về **"Đếm số cặp số có tổng chẵn"**, chỉ có hai trường hợp như sau:

- Chẵn - Chẵn.
- Lẻ - Lẻ.

#### Trường hợp 2: $sum$ lẻ $\to$ $\left( A_i + A_j \right)$ phải lẻ.

Bài toán quy về **"Đếm số cặp số có tổng lẻ"**, chỉ có duy nhất trường hợp sau:

- Chẵn - Lẻ.

---

Như vậy để xử lý bài toán chỉ cần đếm số lượng số chẵn và số lẻ trong dãy.

Khi đó, đặt:

- $cnt_0$: số lượng số chẵn.
- $cnt_1$: số lượng số lẻ.

Ta có các công thức tính như sau:

- Số cặp chẵn - chẵn: $\frac {cnt_0 \cdot (cnt_0 - 1)}{2}$.
- Số cặp lẻ - lẻ: $\frac {cnt_1 \cdot (cnt_1 - 1)}{2}$
- Số cặp chẵn - lẻ: $cnt_0 \cdot cnt_1$

Độ phức tạp thời gian: $O \left( n \right)$.

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    long long res = 0, sum = 0, cnt[2] = {0, 0};

    cin >> n;
    for (int i = 0; i < n; i++) {
        int x; 
        cin >> x;
        
        sum += x;
        cnt[x % 2]++;
    }

    if (sum % 2 == 0) {
        cout << cnt[0] * (cnt[0] - 1) / 2 + cnt[1] * (cnt[1] - 1) / 2;
    }
    else {
        cout << cnt[0] * cnt[1];
    }
    
    return 0;
}

:::

## Bài 3: Đổ nước vào chai (6 điểm)

Cho dãy số nguyên dương $A_1, A_2, A_3, ..., A_n$ $(n \le 10^5)$. Chọn một số phần tử sao cho không có hai phần tử nào liền kề nhau trong dãy, sao cho tổng các phần tử được chọn là **lớn nhất**.

### Brute - force:

Quay lui thử tất cả các cách chọn.

Độ phức tạp thời gian: $O\left( 2^n \right)$.

### AC:

Quy hoạch động cơ bản.

Định nghĩa $dp_i$ là tổng lớn nhất có thể đạt nếu xét lấy trong $i$ phần tử đầu tiên (có thể lấy hoặc không lấy).

Công thức quy hoạch động:

- $dp_1$ = $A_1$: Trường hợp cơ sở.
- $dp_i = \max(dp_{i-1}, \: dp_{i-2} + A_i)$ $\left( i \ge 2 \right)$:
- $dp_i = dp_{i-1}$: Không lấy $A_i$ vào tổng tối ưu.
- $dp_i = dp_{i-2} + A_i$: Lấy $A_i$ vào tổng tối ưu.

Kết quả: $dp_n$.

Độ phức tạp thời gian: $O \left( n \right)$.

:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int n, A[N+1];
long long dp[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
    }

	dp[1] = A[1];
	for (int i = 2; i <= n; i++)  {
		dp[i] = max(dp[i-1], dp[i-2] + A[i]);
    }

	cout << dp[n];

	return 0;
}

:::