# HSG 9 Đà Nẵng

## 2020 - 2021

### Bài 1: Số nguyên tố cân bằng

- **Tóm tắt đề bài**: Cho $N = xx...xyx...xx$ $(1 \le x \le 9, 0 \le y \le 9)$, đếm số lượng số $N$ thỏa $N$ là số nguyên tố.
- **Ý tưởng**: Sinh tất cả các số $N$ độ dài $k$ thỏa $N$ cân bằng và $N$ là số nguyên tố.

### Bài 2: Từ đại diện

- **Tóm tắt**: Cho một dãy xâu $S$ và một xâu $P$, đếm số lần $P$ xuất hiện trong $S$, trong $P$ có các dấu '?' là kí tự bất kì.
- **Ý tưởng**: Duyệt qua các xâu $X$ của $S$, nếu với mỗi kí tự của $X$ bằng mỗi kí tự của $P$ thì cộng 1 vào kết quả, nếu kí tự đang xét là '?' thì luôn cộng 1 vào kết quả.
- **Code tham khảo**:

# Nhập S
# Nhập P

ans = 0
for X in S:
    if length(X) != length(P):
        continue
    
    for i = 1 --> length(X):
        if X[i] == '?' or X[i] == S[i]:
            ans += 1
print(ans)

Code full:

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

#define int long long
#define all(x) x.begin(), x.end()

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

    vector<string> S;
    string s; getline(cin, s);
    string cur = "";
    for(int i = 0; i < s.size(); ++ i) {
        if(s[i] == ' ') {
            S.push_back(cur);
            cur = "";
        }
        else cur += s[i];
    }
    S.push_back(cur);
    string P; cin >> P;

    int ans = 0;
    for(int i = 0; i < S.size(); ++ i) {
        if(S[i].size() != P.size()) continue;
        string p = P;
        for(int j = 0; j < P.size(); ++ j) 
            if(p[j] == '?')
                p[j] = S[i][j];
        if(S[i] == p) ++ ans;
    }
    cout << ans;
}

### Bài 3: Diện tích lớn nhất

- **Tóm tắt**: đọc đề <(")
- **Ý tưởng**: Cố định đoạn $MA$, có $AB$ tính $MB$ = $\sqrt{AB^2 - MA^2}$, đáp án $m = max(MA * MB)$
- **Code**:

ans = 0
for a = 1 --> k:
    b2 = k * k - a * a
    if b2 là số chính phương:
        ans = max(a * sqrt(b2), ans)
print(ans)

## 2021 - 2022

### Bài 1 & 2

### Bài 3: Tam giác
- Tóm tắt: Cho $a$, $b$ là 2 số nguyên dương. Đếm số số $c$ sao cho $a$, $b$, $c$ là 3 cạnh của một tam giác.
- $a + b > c > a - b$
- $(a + b) - (a - b) - 1 = 2b - 1$ $(b < a)$

### Bài 4: Bội đặc biệt
- Tóm tắt: Cho số $P$ và $N$, và số $X$ có dạng $99...99$, đếm số số $X$ sao cho $X$ chia hết cho $P$ và $X$ có $N$ chữ số.
- Ví dụ: $P = 7$, $N = 7$ -> chỉ có $999999$ là thỏa mãn tính chất trên.

- **Subtask 1**: $P < 100, N \le 10$
Subtask này ta chỉ cần duyệt trâu qua toàn bộ các giá trị $X$ có thể.

X = X * 10 + 9

$X_{max} = 10^{10}$ $\Rightarrow$ ko sợ bị tràn số

- **Subtask 2**: $100 \le P \le 10000, N \le 160$
Subtask này ta cần biết 1 tính chất sau:

(a + b) % m = (a % m + b % m) % m

$X_{max} = 10^{160}$ $\Rightarrow$ ko ổn.
Sau khi tính toán, đáp án của mình là $X$ % $P$
Mình vừa tính, vừa mod luôn.
Áp dụng công thức trên:

X = (X * 10 + 9) % P (a = x * 10, b = 9)
  = (X * 10 % P + 9) % P

Sau khi tính xong, nếu $X = 0$ thì $ans + 1$.

- **Subtask 3**: $10^4 \le P \le 10^6$, $N \le 10^{18}$
- Giả sử ta thử $P = 7$, $N = 20$:
$9$: ko thỏa vì ko chia hết cho 7
$99$: như trên
$999$: như trên
$9999$: như trên
$99999$: như trên
$999999$: chia hết cho 7
.
.
.

- Ta nhận thấy, với test trên, chỉ có các số:
$999999$
$999999999999$
$999999999999999999$
thỏa mãn
- Thử $P = 7,8,9,...$, $N = 18$ để củng cố, khẳng định quy luật là đúng.

$\Rightarrow$ Ta có thể rút ra được quy luật: Gọi $L$ là độ dài của số nhỏ nhất thỏa mãn tính chất của đề
$\Rightarrow$ Đáp án sẽ là $\frac{N}{L}$ vì độ dài của những số sau sẽ tăng thêm $L$

## 2019 - 2020

### Bài 1: Đếm cặp đôi

- Tóm tắt: Có số $x$ ($x \le 10^6$), đếm trong dãy $A$ số cặp $(i, j)$ sao cho $A_i + A_j = x$
- **Cách 1: 2 con trỏ (two - pointers)**
***B1***: Sort lại mảng $A$
***B2***: Cố định 2 biến l, r ở 2 đầu của mảng $A$ ($l = 1, r = n$)
$A_l \le A_{l + 1}$ và $A_{r - 1} \le A_r$
***B3***: Check tổng $A_l + A_r$ so với $x$ $\Rightarrow$ 3 trường hợp có thể xảy ra:
*TH1*: $A_l + A_r < x$ $\Rightarrow$ tăng $l$ lên để tổng đến gần $x$ hơn.
*TH2*: $A_l + A_r > x$ $\Rightarrow$ giảm $r$ xuống.
*TH3*: $A_l + A_r == x$ $\Rightarrow$ $ans += (số lượng số $A_l$) * (số lượng số $A_r$).
- **Cách 2: dùng CTDL map (chỉ áp dụng cho C++)**
Khai báo:

map<int, int> mp; // gán cho mỗi giá trị int một giá trị int tương ứng
mp[3] = 2
mp[1000000000] = -1358374985729
mp[-1000] = 100

**Ưu điểm**: lưu bất kì giá trị nào mình muốn ($\le 10^{18}$)
**Nhược điểm**: truy cập giá trị trong mảng $O(1)$, truy cập map $O(log$ $n)$ ($n$ là kích thước hiện tại của map)

***B1***: tạo `map<int, int> cnt` để đếm phân phối
***B2***: với mỗi $A_i$, đếm số lượng $x - A_i$ trong mảng rồi cộng vào `ans`
***B3***: `cnt[A[i]] ++`

### Bài 3: Thừa số nguyên tố

- Tóm tắt: tự đọc đề
- **Solution**: đề bảo gì làm nấy <(")
Cụ thể hơn, ta đếm tổng số mũ của mỗi số $A_i$, rồi bỏ số có tổng số mũ lớn nhất

## 2018 - 2019

### Bài 3: Tìm phần thưởng

Code tham khảo (chưa tối ưu: $O(sqrt(m)) = O(10^8)$):

// nhap m
int ans = 0, max_diff = 0;
for(int a = 1 -> sqrt(m)) {
    if(m % a == 0) { // a la uoc cua m
        // a = q - x
        int b = m / i; // b = q + x
        int q = (a + b) / 2; // a + b = q - x + q + x = 2q --> q = (a + b) / 2
        int p = b - q + 1;
        if(q - p + 1 > max_diff) {
            max_diff = q - p + 1;
            ans = (p + q) / 2;
        }
    }
}
cout << ans;

Tối ưu: thay vì for từ $1$ đến $\sqrt{m}$ thì ta sẽ làm ngược lại, nếu tìm được ước thỏa mãn thì in ra luôn (vì cách này for từ ước lớn nhất $\Rightarrow$ nhỏ nhất $\Rightarrow$ nếu tìm được đáp án thỏa mãn thì chắc chắn đáp án đó là lớn nhất).

test test test test test test test