# Lời giải đề thi thử Tuyển sinh 10 trường THPT chuyên Khoa học Tự nhiên - Lần 2 - Môn Tin học

Chấm bài tại đây: [ClueOJ](https://oj.clue.edu.vn/contest/khtn_thithuts10_2_25).

## Bài 1 - RECT

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

Cho $n$ điểm $(x_i, y_i)$ trên mặt phẳng tọa độ. Hãy tìm hình chữ nhật diện tích nhỏ nhất chứa cả $n$ điểm này.

### Lời giải

Hình chữ nhật tối ưu sẽ luôn có một (vài) điểm nằm trên cạnh. Nếu không có điểm nào nằm trên cạnh, ta hoàn toàn có thể hạ độ dài cạnh mà không làm ảnh hưởng kết quả.

Vì vậy, ta gọi $min_x$ là $min (x_i)$ với $1 \le i \le n$. Tương tự ta có $max_x$, $min_y$ và $max_y$.

Đây là các tọa độ tối thiểu và tối đa của các cạnh hình chữ nhật. Vì vậy, diện tích tối thiểu của hình chữ nhật là $(max_x - min_x) \times (max_y - min_y)$.

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

## Bài 2 - ONES

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

Cho số gồm $n$ chữ số $1$. Ví dụ, với $n = 4$ ta có số $1111$.

Hãy tính $n$ $\%$ $998244353$.

### Subtask 1: $n \le 18$

Ta có thể tính hẳn giá trị $n$ ra, sau đó tìm ra kết quả.

Ta có thể xây dựng từng chữ số như sau:

int res = 0;
for (int i = 1; i <= n; i++){
    res *= 10; // Lúc này, số đã có thêm một chữ số 0.
    res += 1; // Ta thay chữ số 0 thành chữ số 1.
}

Cuối cùng, ta in ra kết quả.

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

### Subtask 2: $n \le 10^5$

Nhìn vào công thức truy hồi trên, thay vì nhân hết rồi mới mod, ta có thể mod ngay khi nhân, do tính chất của phép cộng và nhân đều có thể modulo được.

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

## Bài 3 - RAND

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

Cho $F(x) = ax + b$ và dãy số $S = {S_1, S_2, ..., S_n}$ được xác định như sau:
- $S_1 = c$
- $S_i = F(S_{i-1}) \mod 100$ với $2 \le i \le n$

Tìm số lớn thứ $k$ trong dãy $S$.

Giới hạn: ($a, b \le 10^9, c < 100, n \le 10^7$)

### Subtask 1: $n \le 2 \times 10^5$

Ở subtask này, ta hoàn toàn có thể mô phỏng dãy $S$ từ $S_1$ đến $S_n$ do giới hạn $n$ không quá to. Sau đó, ta sẽ sắp xếp dãy $S$ để từ đó tìm được số lớn thứ $k$.

Độ phức tạp: $O$ ($n log n$)

### Subtask 2: $n \le 10^7$

Ta có thể để ý rằng, do giá trị $mod$ tương đối nhỏ (tối đa $100$), cũng đồng nghĩa giá trị của $S$ không vượt quá $99$. Từ đó, ta nhận ra rằng, hoàn toàn có thể sử dụng mảng đánh dấu để có thể đánh dấu số lần xuất hiện của từng phần tử $S_i$ trong mảng $S$.

Gọi $cnt_i$ là số lần giá trị $i$ xuất hiện trong mảng $S$. Ta sẽ tiến hành duyệt từ cuối mảng $cnt$ về đầu, và cộng số lần xuất hiện của giá trị $i$ vào biến $res$. Đáp số đề bài chính là giá trị $i$ đầu tiên mà $res \ge k$.

Độ phức tạp: $O$ ($n$)

## Bài 4 - SHOP

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

Cho $n$ món đồ, món đồ thứ $i$ có giá mua là $c_i$ và giá trị là $v_i$. Tuy vậy, có $k$ điều kiện dạng $(a_i, b_i)$ có nghĩa: nếu bạn mua món đồ $a_i$, bạn phải mua món đồ $b_i$.

Với số tiền $m$ đồng, hãy mua các món đồ sao cho tổng giá trị là lớn nhất.

Giới hạn: $n \le 1000$, $k \le 10^4$, $m, c_i, v_i \le 10^9$

### Subtask 1: $c_i, m \le 1000$, $k \le 2$

Với một điều kiện $(a_i, b_i)$ có bốn cách chọn:
- Không mua cả hai: hợp lệ.
- Mua cả hai: hợp lệ.
- Mua $a_i$, không mua $b_i$: Không hợp lệ.
- Không mua $a_i$, mua $b_i$: Hợp lệ.

Vì vậy, với mỗi điều kiện, ta có ba cách chọn. Ta sẽ duyệt $3^k$ cách chọn này.

Ta cần kiểm tra các lựa chọn có mâu thuẫn nhau không. Nói cách khác, chẳng hạn nếu ở điều kiện $1$ ta phải mua vật $x$, nhưng ở điều kiện $2$ ta lại không mua vật $x$, thì đây là mâu thuẫn.

Sau khi có danh sách các vật phải mua, và các vật không được mua, ta có thể quy hoạch động cái túi như bình thường, do giới hạn $n \times m \le 10^6$ khá nhỏ.

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

### Subtask 2: $n \le 20$.

Với subtask này, ta hoàn toàn có thể duyệt mọi tập con của $n$ phần tử. Sau đó, ta cần kiểm tra tập con này có thỏa mãn không.

Trước hết, ta cần kiểm tra tập con này có thỏa mãn $k$ điều kiện nói trên không. Có thể duyệt đủ $k$ điều kiện, tuy nhiên điều này là khá chậm. Ta có thể làm cách khác:
- Với mỗi điều kiện $i$, ta sẽ lưu các **vật phẩm phải mua** nếu mua vật phẩm thứ $i$ **dưới dạng bitmask.**
- Sau đó, ta có thể dễ dàng kiểm tra bằng phép toán AND hai tập hợp. Gọi $mask$ là tập con của $n$ phần tử ta đang thử, $must$ là tập các vật phẩm phải mua khi mua vật phẩm $i$ (mà vật phẩm $i$ cũng phải nằm trong $mask$), thì tập này thỏa mãn nếu $mask$ $\&$ $must = must$.

Sau đó, ta cần tính tổng số tiền phải trả cho tập con này, nếu $\le m$ thì ta cập nhật vào kết quả.

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