# Lời giải đề Tuyển sinh 10 môn Tin HCM 2024 - 2025
**Author: Tập thể lớp 10CTIN Gen 10 trường THPT Gia Định**
# Bài 1: CASE
++**Đề bài: (Có thể skip xuống phần tóm tắt)**++
Ông Pascal xây dựng một kệ tài liệu theo dạng hình tam giác có chiều cao $h$. Các tầng được đánh số từ $1, 2, \dots, h$. Tổng $i$ có $i$ ngăn đánh số từ $1, 2, \dots, i$. Minh họa hình bên:

Tầng $1$: $1$

Tầng $2$: $1$ $2$

Tầng $3$: $1$ $2$ $3$

Tầng $4$: $1$ $2$ $3$ $4$

[$\dots$]

Tầng $h$: $\dots$

$N$ tài liệu được đánh số từ $1, 2, \dots, N$ được cắt vào các ngăn trên kệ theo thứ tự từ trái sang phải và từ trên xuống dưới.

Do kệ quá cao nên ông thiết kế một hệ thống robot tự động có thể di chuyển đến ngăn cắt tài liệu thứ $P$ mà ông cần.

**Yêu cầu:** Hãy viết chương trình xác định tầng và ngăn cắt tài liệu thứ $P$.

**Dữ liệu:** Đọc vào từ file văn bản `CASE.INP` gồm một số nguyên $P$ ($1 \leq P \leq 10^{18}$).

**Kết quả:** Ghi ra file `CASE.OUT` gồm 2 số nguyên lần lượt là số tầng và số ngăn cắt tài liệu, hai số cách nhau 1 khoảng trắng.

**Giải thích:**
Các tài liệu được cắt trên kệ lần lượt là:

$1$

$2, 3$

$4, 5, 6$

$7, 8, 9, 10$

$11, 12, 13, 14, 15$

$\dots$

$\Rightarrow$ Tài liệu thứ $13$ được cắt ở tầng $5$, ngăn $3$.

==++**Tóm tắt:**++==
Ta được cho một số $x$ và yêu cầu tìm vị trí (hàng, cột) xuất hiện của số $x$ ở bảng trên.

**INPUT**
Số nguyên dương $x$ ($1 \leq x \leq 10^{18}$).

**OUTPUT**
Hàng và cột của số nguyên dương $x$.

**SAMPLE INPUT**

13

**SAMPLE OUTPUT**

5 3

**SUBTASKS**

| Subtask | Điểm | Ràng buộc |
|---------|------|----------------------|
| $1$ | $50%$% | $x \leq 1000$ |
| $2$ | $30%$% | $x \leq 10^{12}$ |
| $3$ | $20%$% | $x \leq 10^{18}$ |

==++**Cách giải:**++==

**Bước 1:** Tiến hành tìm kiếm nhị phân để tìm ra vị trí hàng của $x$.
+ Do $x \leq 10^{18}$ nên sẽ chỉ tồn tại tối đa $2 \times 10^9$ hàng mà ta cần sử dụng.
+ Tiến hành tìm kiếm nhị phân (Binary search) trong khoảng từ $1$ - $2 \times 10^9$ và tìm ra hàng $pos$ đầu tiên, với giá trị đầu tiên của hàng $pos$ lớn hơn $x$. Suy ra: $pos - 1$ chính là vị trí hàng của $x$ (tạm gọi là $u$).

**Bước 2:** Sau khi đã có $u$ ta đã giải quyết xong $1$ nửa bài toán, tiếp đến ta sẽ đi tìm vị trí cột của $x$.
+ Gọi $res$ là giá trị đầu tiên của hàng $u$ (dùng công thức để tính).
+ Vị trí cột của $x$ tạm gọi là $v$, $v = x - res + 1$.

**Bước 3:** in ra $u$, $v$.

==++**Minh hoạ:**++==

- **Delta:**
- Ta nhận thấy giữa các phần từ đều có 1 độ chênh lệch (**Delta** $\Delta$) giữa phần tử trước và sau theo 1 cấp số cộng, cụ thể là: $1$, $2$, $3$, $4$, $5$, $\dots$
$\Rightarrow$ Từ đó ta có công thức để tính được giá trị đầu tiên của hàng thứ $n$ là:

:::info
$\frac{n \times (n - 1)}{2} + 1$
:::

==++**Code:**++==

<details>
<summary>Click to show code</summary>

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

int val(int n) {
    return n * (n - 1) / 2 + 1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    freopen("case.inp", "r", stdin);
    freopen("case.out", "w", stdout);
    int x;
    cin >> x;
    int l = 1;
    int r = 2e9;
    int u;
    while (l <= r){
        int mid = (l + r) / 2;
        if (val(mid) > x) {
            u = mid - 1;
            r = mid - 1;
        } else l = mid + 1;
    }
    int v = x - val(u) + 1;
    cout << u << " " << v;
    
}

</details>

[**Link CODE tại đây**](https://ideone.com/FORYMW)

# Bài 2: LUCKYNUM
++**Đề bài: (Có thể skip xuống phần tóm tắt)**++

Trong hội trại cuối năm, nhà trường tổ chức trò chơi xổ số may mắn. Thể lệ trò chơi như sau:

Người chơi sẽ chọn cặp số may mắn, cặp số may mắn là cặp số mà tích của chúng có chữ số ở hàng đơn vị bằng với số $P$ do ban tổ chức công bố.

Tuy nhiên, người chơi sẽ có rất nhiều cách chọn cặp số khác nhau, vì thế ban tổ chức giới hạn phạm vi giá trị người chơi có thể chọn bằng hai số $L$ và $R$ ($L < R$), số được chọn có giá trị không nhỏ hơn $L$ và không lớn hơn $R$.

Nhằm chuẩn bị tốt cho trò chơi, ban tổ chức cần biết được có bao nhiêu cặp số may mắn theo thể lệ trên.

**Ví dụ:** Với $L=1$, $R=7$ và $P=1$, sẽ có $3$ cặp số may mắn là $(1; 1)$, $(3; 7)$ và $(7; 3)$ vì tích của chúng đều có chữ số ở hàng đơn vị bằng $1$.

**Yêu cầu:** Hãy viết chương trình giúp BTC biết được số lượng cặp số may mắn khi dự kiến công bố giá trị $L$, $R$ và $P$.

**Dữ liệu:** Đọc vào file `Luckynum.inp` 3 dòng:

- Dòng đầu tiên là số $L$,

- Dòng thứ 2 là số $R$,

- Dòng thứ 3 là số $P$ ($1 \leq L \leq R \leq 10^9$, $0 \leq P \leq 9$).

**Kết quả:** Ghi ra file `Luckynum.out` gồm một dòng cho biết số lượng cặp số may mắn theo yêu cầu.

**INPUT**
Cho ba số nguyên $L$, $R$ và $P$ ($1 \leq L \leq R \leq 10^9$, $0 \leq P \leq 9$).

**OUTPUT**
Đếm số cặp $(i, j)$ ($L \leq i, j \leq R$) sao cho chữ số tận cùng của $i \times j$ bằng $P$.

**SAMPLE INPUT**

1 4 4

**SAMPLE OUTPUT**

3

- Các cặp may mắn: $(1, 4)$, $(2, 2)$, $(4, 1)$.

## SUBTASKS
| Subtask | Điểm | Ràng buộc |
|---------|------|----------------------|
| $1$ | $35%$% | $R \leq 1000$ |
| $2$ | $15%$% | $R \leq 10^8$, $P = 5$ |
| $3$ | $15%$% | $P = 5$ |
| $4$ | $35%$% | Không ràng buộc |

==++**Tóm tắt đề:**++==
Cho 3 số nguyên $L$, $R$, $P$ yêu cầu đếm số cặp $(i, j)$ không phân biệt thứ tự ($L \leq i, j \leq R$) sao cho tận cùng của $i \times j$ là $P$ ($L, R \leq 10^9$, $0 \leq P \leq 9$).

Đơn giản hoá bài toán: Đếm số cặp $(i, j)$ sao cho $i \times j \mod 10 = P$.

==++**Cách giải:**++==

**Bước 1**: Đếm số lượng các số trong $[L, R]$ có chữ số tận cùng là $d$ ($0 \leq d \leq 9$).
- Gọi mảng $cnt[d]$ là số lượng số có tận cùng là $d$ trong đoạn $[L, R]$.

**Bước 2**: Tính $cnt[d]$ cho từng $d$ từ $0$ đến $9$:
- Với mỗi $d$, tìm số nhỏ nhất $\geq L$ có tận cùng $d$:
$$start = L + ((d - (L \mod 10) + 10) \mod 10$$
- Nếu $start > R$: $cnt[d] = 0$.
- Ngược lại: $cnt[d] = \left\lfloor \frac{R - start}{10} \right\rfloor + 1$.

**Bước 3**: Duyệt tất cả cặp $(a, b)$ (từ $0$ đến $9$) và kiểm tra điều kiện:
- Nếu $a \times b \mod 10 = P$, cộng thêm $cnt[a] \times cnt[b]$ vào kết quả.

**Bước 4**: In kết quả.

==++**Code:**++==
<details>
<summary>Click to show</summary>

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

int dem(int l, int r, int d) {
    int start = l + ((d - l % 10 + 10) % 10);
    if (start > r) return 0;
    return (r - start) / 10 + 1;
}

int cnt[10];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int l, r, p;
    freopen("luckynum.inp", "r", stdin);
    freopen("luckynum.out", "w", stdout);
    cin >> l >> r >> p;

    for (int d = 0; d < 10; d++) cnt[d] = dem(l, r, d);
    
    int ans = 0;
    for (int a = 0; a < 10; a++) 
        for (int b = 0; b < 10; b++) 
            if ((a * b) % 10 == p) 
                ans += cnt[a] * cnt[b];
            
        
    cout << ans;
    return 0;
}

</details>

[**Link CODE tại đây**](https://ideone.com/KBBDoI)

# Bài 3: HOSTING
++**Đề bài: (Có thể skip xuống phần tóm tắt)**++
Công ty VinasatX cho thuê máy chủ hiện đang có $N$ khách hàng. Mỗi khách hàng có nhu cầu sẽ đăng ký các thông tin gồm: ngày bắt đầu thuê ($X_i$), số ngày sử dụng ($D_i$) và dung lượng cần dùng ($K_i$).

Nhằm chuẩn bị cho việc đầu tư cơ sở hạ tầng, công ty cần đánh giá quá trình biến động về dung lượng cho thuê trong suốt quá trình hoạt động. Ngày công ty bắt đầu máy chủ được xem là ngày $1$, các ngày tiếp theo ghi nhận lần lượt là ngày $2$, ngày $3$, $\dots$

Để đánh giá biến động về dung lượng máy chủ cần cung cấp, công ty sẽ tính tổng dung lượng cho tất cả khách thuê theo từng ngày. Nhưng ngày không có khách thuê thì dung lượng cần dùng được xem là $0$.

Công ty cần lập bảng theo dõi quá trình biến động này từ ngày bắt đầu cho thuê ($X_i$ nhỏ nhất) cho đến ngày cuối cùng máy chủ được khách hàng sử dụng.

**Yêu cầu:** Viết chương trình thông báo biến động dung lượng trong quá trình hoạt động.

**Dữ liệu:** Đọc vào file `HOSTING.INP` theo mô tả sau:

- Dòng đầu tiên chứa số nguyên dương $N$ ($1 \leq N \leq 8 \times 10^5$).

- $N$ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương $X_i$, $D_i$, $K_i$ ($X_i + D_i \leq 10^5$, $1 \leq K_i \leq 10^9$), mỗi số cách nhau một khoảng trắng.

**Kết quả:** Ghi ra file `HOSTING.OUT` gồm 1 dòng duy nhất là dãy số cho biết quá trình biến động về dung lượng theo yêu cầu trên, mỗi số cách nhau một khoảng trắng.
**INPUT**
Dòng đầu tiên chứa số nguyên dương $n$ là số khách hàng.

$n$ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương $x_i$, $d_i$ và $k_i$ thể hiện một khách hàng.

**OUTPUT**
Bảng biến động sử dụng của công ty đó.

**Constraint:**
- $1 \leq n \leq 8 \times 10^5$
- $1 \leq x_i + d_i \leq 10^5$, $1 \leq k_i \leq 10^9$

**SAMPLE INPUT 1**

3
6 2 15
3 6 9
4 5 7

**SAMPLE OUTPUT 2**

9 16 31 16


==++**Tóm tắt đề:**++==
Cho mảng ban đầu là $0$ và $n$ truy vấn có dạng vị trí bắt đầu $L$, độ dài $len$ và giá trị $val$, yêu cầu tăng dãy từ vị trí $L$ sao cho độ dài là $len$ lên $val$ đơn vị. Xuất ra mảng nhưng sao cho không có giá trị **trùng**.

==++**Ý tưởng:**++==
- Ở đây chúng ta sử dụng kĩ thuật **mảng hiệu** để giải quyết.
- Khi được cho vị trí bắt đầu, độ dài, và giá trị cần tăng thì:
- Ta sẽ đánh dấu (tức là cộng vào) tại vị trí bắt đầu là giá trị cần tăng: `pre[L] += val;`
- Và đánh dấu đối số của giá trị đó tại vị trí $R+1$: `pre[R + 1] += -val;`
- Vì sao ý tưởng này đúng?
**VD:**

- Trong hình là đoạn và giá trị mà ta cần cập nhật trên mảng `pre[]`.
- Sau khi cập nhật xong, bằng cách sử dụng công thức: `pre[i] += pre[i - 1]` thì ta đã có thể kéo dài được giá trị tới đoạn $R$ mong muốn.

==++**Minh hoạ:**++==

==++**Code:**++==

<details>
<summary>Click to show code</summary>

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5 + 7;
int pre[MAXN], n, L, R, maxi;

signed main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    freopen("hosting.inp", "r", stdin);
    freopen("hosting.out", "w", stdout);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        int L, R, len, val;
        cin >> L >> len >> val;
        R = L + len;
        maxi = max(maxi, R - 1);
        pre[L] += val;
        pre[R] -= val;
    }
    
    for(int i = 1; i <= maxi; i++){
        pre[i] += pre[i - 1];
        if (pre[i] != pre[i-1]) cout << pre[i] << " ";
    }    
    
    return 0;
}

</details>

[**Link CODE tại đây**](https://ideone.com/oMK2uO)