# Đề THT B - BRVT - 2018: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2017 - 2018.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_thtb_15_24).
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Đếm số tam giác (8 điểm)

### Tóm tắt đề bài

Cho $n-1$ điểm trên cạnh $AB$ và chia $AB$ thành $n$ phần bằng nhau. Tương tự với $AC$.

Nối các điểm trên cạnh $AB$ với điểm $C$ và các điểm trên cạnh $AC$ với điểm $B$.

**Yêu cầu:** Đếm số lượng tam giác được tạo ra chia dư cho $2018$.

:::danger
**Lưu ý:** Các tam giác không nhất thiết phải được tạo bởi điểm nằm trên cạnh $AB$, $AC$.
:::

**Dữ liệu đảm bảo:** $1 \le n \le 10^9$.

### Lời giải

>[!Tip] Nhận xét
>Vì các điểm được nối từ $B$ và $C$ nên các tam giác tạo được ==có đỉnh là $B$ hoặc $C$==.
>
>:::success
>Tách nhỏ bài toán thành đếm số tam giác có đỉnh $B$ hoặc $C$.
>:::


Xét hình minh họa ở trên, với mỗi cặp đỉnh trên cạnh $AC$, ta tạo được một vùng (đánh dấu màu vàng). Trong vùng này, có $n$ đường cắt (đánh dấu bằng màu xanh), và mỗi đường cắt trên tạo được thành một tam giác mới.

Do đó, số tam giác có đỉnh $B$ là ==$C^2_{n+1} \times n$==.
> $C^k_n$ là tổ hợp chập $k$ của $n$ có công thức là $\frac{n!}{(n-k)!k!}$.
>
> Ta lấy $C^2_{n+1}$ vì trên $AC$ có $n+1$ đỉnh.

Tương tự, số tam giác có đỉnh $C$ là ==$C^2_{n+1} \times n$==.

>[!Caution]
>Nếu cộng hai đáp án ở trên lại, thì ta đang tính trùng số lượng các tam giác có có đỉnh là cả $B$ và $C$.
>::: danger
>Số lượng tam giác bị trùng như vậy là ==$n^2$==.
>> **Giải thích:**
>> Số tam giác trùng là số cách chọn một đỉnh và ghép với $B, C$, tức là $n \times n$.
>> Khi $1$ cạnh từ $B$ và $1$ cạnh từ $C$ (không tính $BC$) giao nhau sẽ tạo ra $1$ đinh.
>:::

**Đáp án:** $C^2_{n+1} \times 2n - n^2 = n^3$.

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

:::success
:::spoiler Code

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

long long n;

int main() {
    cin >> n;
    n %= 2018;
    cout << (n * n * n) % 2018;
    
    return 0;
}

:::

## Bài 2: Hình vuông số (7 điểm)

### Tóm tắt đề bài

Cho ma trận có kích thước $n \times n$, các số được điển theo thứ tự xoắn ốc.

**Yêu cầu:** Hãy tìm giá trị của ô $(i,j)$.

**Dữ liệu đảm bảo:**
- $2 \le N \le 10^4$.
- $1 \le i, j \le N$.

### Lời giải

Vì giới hạn nhỏ, ta thực hiện di chuyển trên bảng như đề miêu tả để tìm đến ô $(i, j)$.

Đặt hai biến $t_1$ và $t_2$ đại diện cho hai con trỏ đang duyệt theo vòng xoắn ốc của ma trận.

Dùng vòng lặp `while` để liên tục dịch các con trỏ đến các biên rồi thay đổi hướng của chúng. Kết thúc vòng lặp khi $t_1 = i$ và $t_2 = j$.

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

:::success
:::spoiler Code

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

int n;
int main() {
    cin >> n;
    int x, y;
    cin >> x >> y;
    int cnt = 1,t1 = 1,t2 = 1;
    
    int l = 0, r = 1, d = 0, u = 0;
    //Hướng di chuyển hiện tại của con trỏ
    
    int bl = 1, br = n, bu = 2, bd = n;
    //Biên trái, biên phải, biên trên, biên dưới
    
    while (t1 != x || t2 != y) {
        cnt++;
        if (r==1) {
            t2++;
            if (t2 == br) {
                d = 1;
                r = 0;
                br--;
            }
        }
        else if (d == 1) {
            t1++;
            if (t1 == bd) {
                l = 1;
                d = 0;
                bd--;
            }
        }
        else if (l == 1) {
            t2--;
            if (t2 == bl) {
                u = 1;
                l = 0;
                bl++;
            }
        }
        else if (u == 1) {
            t1--;
            if (t1 == bu) {
                r = 1;
                u = 0;
                bu++;
            }
        }

    }
    
    cout << cnt;
    
    return 0;
}

:::