# Đề HSG9 - BRVT - 2017: Editorial

## Bài 1: Tìm số dư (8 điểm)

Tính tổng $S = 1^3 + 2^3 + \dots + n^3 \; \% \; 2017$ $\left( n \le 10^9 \right)$.

### Brute - force:

==Duyệt tuần tự từ $1 \rightarrow n$== để tính đáp án.

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

:::success
:::spoiler Code

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

int main() {
    int n;
    cin >> n;
    
    long long res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + (1LL * i * i * i) % 2017) % 2017;

    cout << res;

    return 0;
}

:::

### Accepted:

Ta thừa nhận công thức toán học sau: ==$1^3 + 2^3 + \dots + \; n^3 = \left[ \frac{n \cdot (n+1)}{2} \right] ^ 2$==

:::info
:information_source: Lưu ý về các bài toán yêu cầu lấy đáp án chia dư

Nếu tính trước sau đó mới lấy đáp án chia dư cho số $M$ nào đó, đáp án có thể tràn ra khỏi kiểu dữ liệu **long long** trong quá trình tính trước khi tính xong. Do đó, cần biết tính chất sau:

$$
\left( a \cdot b \right) \; \% \; M = \left[ \, (a \; \% \; M) \cdot (b \; \% \; M) \, \right] \; \% \; M
$$

Tính chất tương tự áp dụng cho phép cộng và phép trừ.
:::

Như vậy, ta cần áp dụng lưu ý trên để ==vừa tính đáp án vừa chia dư== để tránh tràn số.

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

:::success
:::spoiler Code

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

int main() {
    long long n; 
    cin >> n;

    n = (n*(n+1)/2) % 2017;
    cout << (n * n) % 2017;

    return 0;
}

:::

## Bài 2: Trò chơi bắn súng (7 điểm)

Đếm số trường hợp của loạt bắn gồm $n$ viên đạn sao cho không có $2$ lần bắn trượt liên tiếp và có ít nhất $2$ lần liên tiếp bắn trúng đích.

### Brute - force:

==Quay lui đơn thuần==, thử tất cả cả trường hợp, sau đó mới kiểm tra có thỏa điều kiện hay không.

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

### Accepted:

Cần đặt thêm **nhánh cận** vào thuật toán quay lui brute - force (chỉ thử các trường hợp có thể thỏa điều kiện).

:::info
**Nhánh cận** trong thuật toán quay lui được hiểu là những điều kiện để dừng hàm quay lui sớm hơn bình thường hoặc chỉ duyệt qua những trường hợp đúng, nhằm tránh việc duyệt qua những trường hợp thừa (chắc chắn sai). Từ đó giảm thời gian chạy chương trình đáng kể.

$\rightarrow$ Nhánh cận được đặt trong bài trên là **không thử hai lần bắn trượt liên tiếp**.
:::

Độ phức tạp thời gian: $O \left( F_{n+2} \right)$ với $F_{n+2}$ là số Fibonacci thứ $n+2$.
>Trường hợp tệ nhất: $O \left( F_{34} \right) = 5702887$.

#### Giải thích độ phức tạp thuật toán:

Đặt:

- $a_n$: Số trường hợp loạt bắn không có 2 lần bắn trượt liên tiếp.
- $b_n$: Số trường hợp loạt bắn không có 2 lần bắn trượt liên tiếp và **phát thứ $n$ trượt**.
- $c_n$: Số trường hợp loạt bắn không có 2 lần bắn trượt liên tiếp và **phát thứ $n$ trúng đích**.

Ta nhận xét chúng có mối quan hệ như sau:

- $a_n = b_n + c_n$.
- $b_n = c(n-1)$ (Phát thứ $n$ bắn trượt thì phắt thứ $n-1$ bắt buộc phải trúng).
- $c_n = a(n-1)$ (Phát thứ $n$ bắn trượt thì phắt thứ $n-1$ trượt hay trúng đều được)

$\Rightarrow$ ==$a_n = a_{n-1} + a_{n-2}$ (Công thức số Fibonacci)== với $a_1 = 2 = F_3$ và $a_2 = 3 = F_4$.

Như vậy tổng số trường hợp mà thuật toán quay lui nhánh cận chạy ở trên sẽ là $F_{n+2}$.

:::success
Bài toán này cũng có thể được giải bằng thuật toán ==quy hoạch động== nói trên.
:::

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
const int N = 32;
int n, res;

void backTrack(int id, bool prevWin, bool consecWin) {
	if (id > n) {
		if (consecWin == true) res++;
		return;
	}
    
        //Chỉ thử TH phát bắn thứ id không trúng nếu trước đó đã bắn trúng
        //Đây chính là NHÁNH CẬN
	if (id == 1 || prevWin == true) backTrack(id+1, 0, consecWin);
    
	backTrack(id+1, 1, consecWin || prevWin == true);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	backTrack(1, 0, 0);

	cout << res;

	return 0;
}

:::

## Bài 3: Phát thưởng (5 điểm)

Cho dãy số nguyên dương $A_1, A_2, A_3, \dots, A_n$. 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)$.

### Accepted:

==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).

Khởi gán:

- $dp_1 = A_1$.
- $dp_2 = \max(A_1, A_2)$.

Công thức quy hoạch động: $dp_i = \max(dp_{i-1}, \; dp_{i-2} + A_i)$

- $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)$.

:::success
:::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];
    dp[2] = max(A[1], A[2]);
	for (int i = 3; i <= n; i++) 
		dp[i] = max(dp[i-1], dp[i-2] + A[i]);

	cout << dp[n];

	return 0;
}

:::