$\Huge \text{🌱 Giải đề tuyển sinh môn Tin học}$
$\small \text{THPT Chuyên Thoại Ngọc Hầu - An Giang}$

:::info
Author: Lê Anh Duy - Chuyên Tin 2020-2023 - THPT Chuyên Thoại Ngọc Hầu, An Giang
Codeforces: [Duy_e](https://codeforces.com/profile/Duy_e)
:::

:::warning
Note:
Đây là lời giải không chính thức. Được cài đặt bài ngôn ngữ C++. Cách đặt được cài đặt theo cách chấm của kỳ thi HSG môn tin học Quốc Gia Việt Nam.

Cách cài đặt của sở có thể bao gồm phần đặt thêm các ràng buộc về dữ liệu nhập, phần đó nhờ bạn đọc tự thêm.
:::

### Bài 1:

>**Tóm đề**: Cho số tự nhiên X, là số chữ số diện tích của mảnh đất. Tìm và in ra diện tích và chu vi của mảnh đất có diện tích lớn nhất và có X chữ số mà diện tích chia hết cho 9 và 5.

#### Lời giải

Ta cần tìm một diện tích có số chữ số bằng X, cũng có nghĩa là ta cần tìm số chính phương $a \text{ mà } 10^{x - 1} \le a \le 10^x - 1.$

Ta cần $a$ chia hết cho $9$ và $5$ $\Leftrightarrow$ tìm $a = b \cdot b$ chia hết cho $9$ và $5$. với $b$ là cạnh mảnh đất

Vì $9 = 3 \cdot 3$ và $5$ là số nguyên tố, nên $b$ cần chia hết cho $3 \cdot 5 = 15$ $\Rightarrow a$ chia hết cho $225 = 15 \cdot 15$

Thay vì tìm thẳng $b$ ở đây ta có thể tìm $c = b \div 15$ sau đó nhân cho $15$ sẽ dễ quản lý hơn. Sau đây là phần cài đặt.
::: success
>Độ phức tạp: $O(X)$

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

long long x;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    freopen("Cau01.inp", "r", stdin);
    freopen("Cau01.out", "r", stdin);
    
    cin >> x;

    long long power = 1;    
    for (int i = 1; i <= x; i ++) power *= 10;
    power --;

    long long side = sqrtl(power / (15 * 15));
    side *= 15;

    cout << "Dien tich: " << side * side << " Chu vi: " << side * 4;

    return 0;
}

:::

### Bài 2:

>**Tóm đề**: cho dãy vô hạn được ghép từ các số tự nhiên liên tiếp, 123456789101112.... Tìm chữ số ở vị trí thứ k

#### Lời giải:

vì $k \le 35000$ nên ta hoàn toàn có thể tạo ra được $k$ chữ số đầu của chuỗi bằng cách ghép cho tới khi độ dài chuỗi có được lớn hơn $k$, sau đó in ra chữ số ở vị trí thứ $k$.

##### Note: ở đây ta nên tự viết hàm ToString(), vì trong themis hoặc một số trình biên dịch không dịch được hàm to_string() trong c++.

:::success
>Độ phực tạp: $O(k)$

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

int k;
string s;

string ToString(int x) {
    string ans = "";
    if (x == 0) return "0";

    while (x > 0) ans += x % 10 + '0', x /= 10;
    reverse(ans.begin(), ans.end());
    return ans;
}

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

    freopen("Cau02.inp", "r", stdin);
    freopen("Cau02.out", "r", stdin);    
    
    cin >> k;

    int num = 1;
    while (s.size() < k) {
        s += ToString(num);
        num ++;
    }

    cout << s[k - 1];

    return 0;
}

:::

### Bài 3:

>**Tóm đề**: Cho 6 số nguyên dương, yêu cầu sắp xếp tăng dần.

#### Lời giải:

Ta chỉ cần dùng hàm sort có sẵn trong ngôn ngữ lập trình (trừ pascal thì cần phải tự code :D).

Ở c++ thì ta có thể dùng `std::sort`.

:::success
>Độ phực tạp: $O(NlogN)$ với $N = 6$

#include <bits/stdc++.h>
using namespace std;
const long long N = 6;
int n, age[N];

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

    freopen("Cau03.inp", "r", stdin);
    freopen("Cau03.out", "r", stdin);
    
    for (int i = 0; i < 6; i ++)
        cin >> age[i];
    
    sort(age, age + N);

    for (int i = 0; i < 6; i ++)
        cout << age[i] << ' ';
    
    return 0;
}

:::

### Bài 4:

>**Tóm đề**: Cho chuỗi ký tự bất kì, in ra các kí tự số theo đúng thứ tự nhập.

#### Lời giải:

Chỉ cần làm y như đề bài, nhưng lưu ý là đối với c++ ta sẽ dùng `getline(cin, s)` thay vì `cin >> s` do chuỗi ký tự có thể chứa ký tự khoảng trắng và `cin >> s` sẽ không nhập được ký tự khoảng trắng.

:::success
>Độ phực tạp: $O(|S|)$ với $|S|$ là độ dài của xâu $S$.

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

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

    freopen("Cau04.inp", "r", stdin);
    freopen("Cau04.out", "r", stdin);
    
    getline(cin, s); // using getline for input space " " character

    for (int i = 0; i < s.size(); i ++)
        if ('0' <= s[i] && s[i] <= '9')
            cout << s[i];
    
    return 0;
}

:::

### Bài 5:

>**Tóm đề**: Cho số $N$, in ra chữ số cuối cùng khác $0$ của $N! = 1 \times 2 \times 3 \times ... \times N$.

#### Lời giải:

Theo đề bài, ta cần loại bỏ được tất cả chữ số $0$ ở cuối của $N$, đương nhiên hoàn toàn có thể giải bằng Bignum, nhưng ở đây mình sẽ dùng thuật toán tốt hơn.

Nhận xét đầu tiên là: Trong $N!$, số lượng thừa số nguyên tố $5$ luôn bé hơn hoặc bằng số lượng thừa số nguyên tố $2$.

Mà số lượng số $0$ cuối cùng của $N!$ bằng số lần ta có thể chia hết $N!$ cho $10$. Từ đó ta có thể thấy được, số lượng chữ số $0$ cuối cùng sẽ bằng số lượng thừa số nguyên tố $5$.

Đặt `Num5 = số lượng thừa số nguyên tố 5 trong N!`

Lúc này, ta chỉ cần loại đi hết `Num5` thừa số nguyên tố $5$ và $2$ ở từng số hạng của $N!$ là được. Sau đó nhân kết quả lại và lấy modulo cho $10$.

>Ở đây mình sử dụng toán tử '%' cho phép chia lấy dư.

Ta biết là, $a \times b \% c = [(a \% c) \times (b\%c)] \% c$.

Nên ta sẽ vừa nhân vừa chia lấy dư.

#### Giải thích code:

Cách tính `Num5`: Thuật toán ngây thơ cho việc này sẽ là với từng số hạng $1, 2, 3...N$ của $N!$ ta sẽ tìm lũy thừa lớn nhất của $5$, và tính tổng số mũ.

Mã giả:

int Num5 = 0;
for (int i = 1; i <= N; i ++) {
    int x = i;
    while (x % 5 == 0) {
        Num5 ++;
        x /= 5;
    }
}

Các bạn có thể dùng cách code trên cũng được. Nhưng ở đây mình sẽ dùng một thuật toán hay hơn :>

Còn về lý do vì sao nó đúng xin bạn đọc tự chứng minh.

:::success
>Độ phực tạp: $O(log_5N + NlogN)$

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

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

    freopen("Cau05.inp", "r", stdin);
    freopen("Cau05.out", "r", stdin);
    
    cin >> n;

    int Num5 = 0, tmp = n, ans = 1;

    while (tmp > 0) {
        Num5 += tmp / 5;
        tmp /= 5;
    }

    for (int i = 1; i <= n; i ++) {
        int x = i;

        while (x % 5 == 0) x /= 5;

        if (Num5 > 0) {
            while (x % 2 == 0 && Num5 > 0) {
                x /= 2;
                Num5 --;
            }
        }

        ans = ans * x % 10;
    }

    cout << ans;
 
    return 0;
}

:::