# Đề HSG9 - BRVT - 2024: Editorial

## Bài 1: Tổng dãy số (8 điểm)

Tính $\text F \left( n \right) = - 1 + 2 - 3 \dots + (-1)^n \cdot n$ $\left( n \le 10^{15} \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() {
    long long n; 
    cin >> n;

    long long sum = 0;
    for (long long i = 1; i <= n; i++) {
        if (i % 2 == 1) sum -= i;
        else sum += i;
    }

    cout << sum;

    return 0;
}

:::

### Accepted:
==**Nhận xét:**==
- Nếu $n$ chẵn: $\text F \left( n \right) = - 1 + 2 - 3 + 4 + \dots - (n-1) + n =1+1+ \dots +1 =$ ==$\frac n2$==.
- Nếu $n$ lẻ: $\text F \left( n \right) = - 1 + 2 - 3 + 4 + \dots -n=1+1+\dots -n=$ ==$\frac{n-1}2-n$==.

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

:::success
:::spoiler Code

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

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

    if (n % 2 == 0) {
        cout << n / 2;
    }
    else {
        cout << (n-1) / 2 - n;
    }

    return 0;
}

:::

## Bài 2: Mua hàng (7 điểm)

Có $n$ mặt hàng với giá tiền $A_1, A_2, ..., A_n$ $\left( n \le 10^6 \right)$.
Tìm cách mua một số mặt hàng sao cho tổng giá tiền **lớn nhất** và **chẵn**.

### AC:

Để giá trị mua hàng là lớn nhất, đầu tiên ta sẽ lấy hết tất cả mặt hàng.
- Nếu tổng giá trị đạt được là chẵn thì in ra luôn kết quả.
- Nếu tổng giá trị là lẻ thì trừ đi $A_i$ lẻ nhỏ nhất.

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

:::success
:::spoiler Code

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

long long n, sum;
long long minVal = 1e18;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        
        sum += x;
        
        if (x % 2 == 1) {
            minVal = min(minVal, x);
        }
    }

    if (sum % 2 == 0) {
        cout << sum;
    }
    else {
        cout << sum - minVal;
    }
    
    return 0;
}

:::

## Bài 3: Tham quan (5 điểm)

Một trung tâm thương mại có $n$ tầng $(n \le 10^6)$.

Đi đến tầng $i$ mất chi phí là $A_i$ để mua hàng.

Từ tầng $i$ có thể di chuyển đến tầng $i+1$ bằng thang bộ và không mất phí di chuyển, hoặc đi thang máy đến tầng $i+2$ và mất $C_i$ phí thang máy $\left( A_i, C_i \le 10^3 \right)$.

### AC:
==Quy hoạch động cơ bản.==

Định nghĩa $dp_i$ là chi phí nhỏ nhất phải trả để đi đến tầng thứ $i$.

Khởi gán:
- $dp_1 = A_1$.
- $dp_2 = A_1+A_2$ (Đi thang bộ).

Công thức quy hoạch động: $dp_i=min(dp_{i-1},dp_{i-2}+C_{i-2})+A_i$.
- ==TH1:== $dp_i = dp_{i-1} + A_i \rightarrow$ Đi thang bộ từ tầng $i-1$ đến tầng $i$.
- ==TH2:== $dp_i = dp_{i-2} + C_{i-2} + A_i \rightarrow$ Đi thang máy từ tầng $i-2$ đến tầng $i$.

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 = 1e6;
long long n;
int dp[N+5], C[N+5], A[N+5];

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

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

    cout << dp[n];
    
    return 0;
}

:::