# Lời giải tham khảo môn Tin kì thi tuyển sinh 10 PTNK 2024

## [Đề chính thức](https://ptnk.edu.vn/cong-bo-de-thi-chinh-thuc-tuyen-sinh-lop-10-nam-hoc-2024-2025/)

[TOC]

<hr>

### **Bài 1**
* **Đề:** Có một dãy số từ $1$ đến $n$ ($n \le 10^9$). Ở mỗi lượt, lấy từ dãy hiện tại các giá trị có vị trí **chia** $3$ **dư** $2$ vào dãy mới, sau đó thay dãy hiện tại bằng dãy mới nhận được. Tiếp tục thực hiện thao tác trên đến khi còn một số duy nhất, hãy cho biết số này.<br> VD: $n = 10 \rightarrow 1,2,3,4,5,6,7,8,9,10 \rightarrow 2,5,8 \rightarrow 5$

* **Lời giải:**
* Viết các dãy ra, ta có thể thấy một quy luật: từ giá trị đầu ở dãy thứ $i$ sang giá trị đầu ở dãy $i+1$ sẽ tăng $3^i$ (lưu ý rằng giá trị đầu ở dãy thứ $i+1$ chính là giá trị thứ hai ở dãy thứ $i$) (các dãy tính từ $0$, với dãy đầu là $1,2,3,...,n$)
0. $1, 2, 3, 4, ...$
1. $2, 5, 8, 11, ...$
2. $5, 14, 23, ...$
3. $14, 41, ...$

* Như vậy ta chỉ cần bắt đầu từ $1$, sau đó cộng dồn vào $3^0, 3^1, ...$ tới khi giá trị hiện tại lớn nhất có thể nhưng không vượt quá $n$.
:::spoiler **Code mẫu**

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

void solve() {
    long long n;
    cin >> n;
    long long res = 1, p = 1;
    while(res + p <= n) {
        res += p;
        p *= 3;
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	
    freopen("LUCK.inp", "r", stdin);
    freopen("LUCK.out", "w", stdout);

    solve();

    return 0;
}

:::
* Độ phức tạp: $O(\log_3 n)$.

<hr>

### **Bài 2**
* **Đề:** Cho bản đồ kích thước $m \times n$ ($m,n\le 1000$), mà mỗi ô $(i,j)$ có thể là nước (giá trị $0$) hay đất (giá trị $1$).
Một tập các ô đất tạo thành *đảo* định nghĩa như sau: hai ô đất thuộc cùng một đảo nếu như có thể đi từ ô này đến ô kia bằng cách di chuyển qua các ô **kề cạnh** là đất. Ngược lại, chúng ở hai đảo khác nhau.
Ta được phép chọn **một** ô nước, và lấp đầy nó để trở thành ô đất. Sau khi chọn một ô để lấp đầy, diện tích lớn nhất của một đảo nào đó bằng bao nhiêu? Biết rằng diện tích của đảo bằng số ô đất thuộc đảo đó. Đồng thời luôn có ít nhất một ô nước trong bản đồ ban đầu.

* **Lời giải:**
* Xét thuật toán trâu sau: với mỗi ô nước, ta sẽ thử biến đổi nó thành ô đất, rồi tính diện tích của hòn đảo có chứa ô này.
Để thực hiện điều này, ta có thể dùng thuật toán loang (theo chiều rộng, BFS, hoặc theo chiều sâu, DFS) bắt đầu từ ô đang xét, mà chỉ loang tới các ô đất và không đi vào ô nước.
Khi đã thử tất cả các ô nước, ta sẽ chọn diện tích lớn nhất có được và đó chính là đáp án. Tuy nhiên, với mỗi ô nước, ta lại loang mất thêm $O(m\times n)$, nên tổng độ phức tạp tệ nhất là $O(m^2\times n^2)$.

* Để tối ưu, ta vẫn giữ ý tưởng duyệt thử tất cả các ô nước, nhưng ta sẽ xác định và tính diện tích trước các hòn đảo ban đầu. Vậy ta sẽ cần tiền xử lý vài thứ.
Ta sẽ loang qua toàn bộ bản đồ để tìm tất cả các hòn đảo ban đầu, đồng thời tính hai mảng: $id$, với $id[i][j]$ là số hiệu của hòn đảo mà chứa ô $(i,j)$, và $sz$, với $sz[idx]$ là diện tích của hòn đảo có số hiệu $idx$.
Khi thử biến đổi một ô nước, nó sẽ "liên kết" với một vài hòn đảo có từ đầu, mà những hòn đảo này chắc chắn sẽ có ô kề với ô nước đang xét. Vì thế, ta sẽ duyệt qua các ô đất kề (4 ô kề cạnh) với ô đang xét và đánh dấu số hiệu các hòn đảo tương ứng. Diện tích của hòn đảo có được bằng $1 +$ (tổng các $sz[idx]$), với $idx$ là số hiệu các hòn đảo kề với ô hiện tại.

* Chú ý rằng hai ô đất cùng kề với ô đang xét có thể có cùng số hiệu (thuộc cùng một hòn đảo). Ta có thể sử dụng mảng đánh dấu hoặc `set` để xử lý điều này. Nhờ thế, độ phức tạp tính toán với mỗi ô nước chỉ còn $O(1)$.
:::spoiler **Code mẫu**

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

const int N = 1e3 + 5;

int m, n;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int a[N][N];
bool added[N * N];
int id[N][N], sz[N * N];

bool safe(int i, int j) {
    return i >= 1 && i <= m && j >= 1 && j <= n;
}

void dfs(int i, int j, int idx) {
    ++sz[idx];
    id[i][j] = idx;
    for(int k = 0; k < 4; ++k) {
        int x = i + dx[k], y = j + dy[k];
        if(safe(x, y) && !id[x][y] && a[x][y] == 1) dfs(x, y, idx);
    }
}

void solve() {
    int res = 0;
    cin >> m >> n;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j) cin >> a[i][j];
    int idx = 0;
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(!id[i][j] && a[i][j] == 1) {
                ++idx;
                dfs(i, j, idx);
            }
        }
    }
	
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(a[i][j] == 1) continue;
            int s = 1;
            for(int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k];
                if(safe(x, y) && !added[id[x][y]]) {
                    s += sz[id[x][y]];
                    added[id[x][y]] = true;
                }
            }
			
            for(int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k];
                if(safe(x, y)) added[id[x][y]] = false;
            }
            res = max(res, s);
        }
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	
    freopen("ISLANDS.inp", "r", stdin);
    freopen("ISLANDS.out", "w", stdout);
	
    solve();

    return 0;
}

:::

* Độ phức tạp: $O(m \times n)$.

<hr>

### **Bài 3**
* **Đề:** Cho một chuỗi vô hạn được ghép bởi dãy số vô hạn $1, 2, 3, 4, ...$ viết dính liền nhau (chuỗi sẽ là $123456789101112131415 ...$) và một số $n$ ($n \le 10^{14}$), in ra các chữ số ở vị trí $n$, $n+1$, $n+2$ và $n+3$ trong chuỗi trên.

* **Lời giải:**
* Tạo một hàm con để tìm chữ số thứ $n$. Trong đó ta sẽ cần tính toán một số thứ:
* Chữ số thứ $n$ nằm trong **một số có bao nhiêu chữ số**, và ta sẽ gọi số này là $d$ (ví dụ: nếu $n = 15$ thì $d = 2$ vì chữ số thứ $15$ nằm trong số $12$, một số có $2$ chữ số).
* **Tổng số lượng chữ số** của các số mà **số chữ số bé hơn $d$**, ta sẽ gọi là $cnt$ (ví dụ: nếu $d = 3$ thì $cnt = 189$, vì từ $1$ tới $99$ là các số có $< 3$ chữ số, tổng số lượng chữ số các số này là $189$, các bạn có thể thử viết dãy 123456789101112...99 ra và đếm thử :>).
* Cuối cùng là $num$, con số **chứa chữ số thứ $n$** trong chuỗi (ví dụ: nếu $n = 15$ thì $num = 12$).

* Bằng cách tính tổng số lượng chữ số từ các số có $1$ chữ số, $2$ chữ số, $3$ chữ số, $...$, cho tới khi số lượng chữ số vượt quá $n$, ta sẽ tìm được $d$ và $cnt$. Để làm được điều này, để ý rằng tổng số lượng chữ số của các số có $1$ chữ số là $9$, của số có $2$ chữ số là $180$, của $3$ chữ số là $2700$, $...$, hay nói cách khác, tổng số lượng chữ số của các số có $x$ chữ số là $9 \times 10^{x-1} \times x$.
Vậy ta sẽ lần lượt tăng $d$ và cộng biểu thức trên vào $cnt$, làm cho tới khi $cnt$ lớn nhất nhưng bé hơn $n$ sẽ tính được $2$ giá trị này. Từ đây ta sẽ bắt đầu xét các chữ số bắt đầu từ $10^{d-1}$ (các số có $d$ chữ số) và không còn quan tâm tới các số có số chữ số bé hơn $d$, nên số lượng chữ số $n$ cũng sẽ trừ đi $cnt$.

* Cuối cùng là tìm $num$ sau khi đã tính được $d$. Vì từ $10^{d-1}$ tới $num$ là các số có $d$ chữ số, nên $num - 10^{d-1} = \lfloor\frac{n - 1}{d}\rfloor$. Lí do tại sao lại là $n - 1$ vì thực chất các chữ số phải được đánh số từ $0$ chứ không phải từ $1$ (các bạn có thể lấy một số ví dụ nhỏ để hiểu rõ). Như vậy cuối cùng $num = 10^{d-1} + \lfloor\frac{n - 1}{d}\rfloor$.

* Sau khi có $num$, chữ số vị trí thứ $n$ sẽ là chữ số thứ $(n - 1) \bmod d$ (vì $num$ có $d$ chữ số nên cần đưa về vị trí trong khoảng $[0, d-1]$), xét từ trái sang phải của $num$, với vị trí chữ số đầu tiên của $num$ tính từ $0$. Lúc này có thể đổi $num$ sang dạng string sau đó lấy ra vị trí $(n - 1) \bmod d$, hoặc làm các cách khác tùy chọn.
:::spoiler **Code mẫu**

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

int get(long long n) {
    long long cnt = 0, d = 1, p = 1, num;
    // cnt: tổng số lượng chữ số của các số có số chữ số < d
    // d: số lượng chữ số của số chứa chữ số thứ n
    // p: 10^(d-1)
    // num: là số có d chữ số chứa chữ số thứ n
    while(cnt + 9 * d * p < n) {
        cnt += 9 * d * p;
        ++d;
        p *= 10;
    }
    n -= cnt;
    --n; // n - 1
    num = p + n / d;
    for(int i = 0; i < n % d; ++i) {
        num %= p;
        p /= 10;
    }
    return num / p;
}

void solve() {
    long long n;
    cin >> n;
    cout << get(n) << get(n + 1) << get(n + 2) << get(n + 3);
}

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

    freopen("PASSWORD.inp", "r", stdin);
    freopen("PASSWORD.out", "w", stdout);

    solve();
    
    return 0;
}

:::
* Độ phức tạp: $O(\log_{10} n)$.