# List bài:

**Bài $1:$** **EASY**
https://codeforces.com/contest/1717/problem/A?fbclid=IwAR22LT4Mr18pwKPXhS3_70rWPBalhwV4E789nDgvjA9I7Dz_OXHFUk_MCvY

**Code AC: (1 dòng)** https://ideone.com/ab1AOM

Cho $1$ số nguyên dương $n$. Tìm số cặp $(a, b)$ thoả mãn: $1$ $\le$ $a, b$ $\le$ $n$ và $\frac{BCNN(a, b)}{UCLN(a, b)}$ $\le$ $3$.

**Input:**
Dòng đầu tiên chứa số nguyên $t$ $(1 \le t \le 10^4)$ - số câu hỏi.
$t$ dòng tiếp theo, mỗi dòng chứa số nguyên $n$ $(1 \le n \le 10^8)$.

**Output**
Mỗi câu hỏi in ra đáp án trên $1$ dòng.

---

**Bài $2:$** **EASY**
https://codeforces.com/contest/1735/problem/A?fbclid=IwAR2VlfqNl6Ca9JjYBfQTwB6PPXRR1sSRqcWxA6hTcsl3kVQSAsDipIw53Ng

**Code AC: (1 dòng)** https://ideone.com/XJ84bg

Cho $1$ số nguyên dương $n$. Độ tốt của $3$ số nguyên dương $x, y, z$ thoả mãn: $x +y + z = n - 3$ là $min(|x - y|, |x - z|, |y - z|)$. Tìm độ tốt lớn nhất.

**Input:**
Dòng đầu tiên chứa số nguyên $t$ $(1 \le t \le 10^3)$ - số câu hỏi.
$t$ dòng tiếp theo, mỗi dòng chứa số nguyên $n$ $(6 \le n \le 10^9)$.

**Output**
Mỗi câu hỏi in ra đáp án trên $1$ dòng.

---

**Bài $3:$** **HARD**
https://atcoder.jp/contests/abc042/tasks/arc058_b

**Code AC (tổ hợp):** https://ideone.com/Reczgl

Cho một bảng kích thước $n \times m$. Các hàng được đánh số thứ tự tăng dần từ trên xuống dưới. Các cột được đánh số thứ tự tăng dần từ trái qua phải.
Ban đầu ta xuất phát ở ô trái trên $(1, 1)$. Mỗi bước di chuyển có thể sang phải $(x, y)$ -> $(x, y + 1)$, hoặc xuống dưới $(x, y)$ -> $(x + 1, y)$.
Ngoài ra, $A$ hàng cuối, trên mỗi hàng $B$ cột trái nhất bị cấm $(A \times B$ ô bị cấm$)$.
Đếm số cách đi từ ô trái trên $(1, 1)$ đến ô phải dưới $(n, m)$ mà không đi vào những ô bị cấm.
Vì đáp án có thể rất lớn, nên in ra số dư khi chia cho $1000000007$.

**Input:**
Một dòng chứa $4$ số nguyên $n, m, A, B$ $(1 \le t \le 10^3)$ - số hàng, số cột, bảng $A \times B$ góc trái dưới bị cấm. $(2 \le n, m \le 10^5,$ $1 \le A < n,$ $1 \le B < m)$

**Output:**
In ra số cách di chuyển từ $(1, 1)$ đến $(n, m)$ không đi qua vùng bị cấm khi chia dư cho $1000000007$.

---

**Bài $4:$** **EASY**
https://codeforces.com/contest/352/problem/A?fbclid=IwAR0l3g4jHFv8OYxiryS0UfYgEit4ypBuqM0JoNkbPz1tJ4aRJiorE0-nAZo
$1$ bài dễ nhưng để code $1$ đấm AC thì hơi chút khó khăn :>

**Code AC:** https://ideone.com/DKBgsw

Cho $n$ tấm thẻ, mỗi tấm chứa $1$ chữ số $0$ hoặc $5$. Ta có thể lấy ra $1$ vài tấm thẻ và xếp chúng trên một đường thẳng, khi đó ta được $1$ số. Tìm số lớn nhất chia hết cho $90$ mà ta có thể tạo ra.
Lưu ý số tạo ra không chứa chữ số $0$ ở đầu, số $0$ là trường hợp đặc biệt :) Không nhất thiết phải dùng tất cả tấm thẻ.

**Input:**
Dòng đầu chứa số nguyên $n$ $(1 \le n \le 10^3)$ - số tấm thẻ.
Dòng tiếp theo chứa $n$ chữ số $a_1, a_2, ..., a_n$ $(a_i = 0$ hoặc $a_i = 5)$ - chữ số trên thẻ thứ $i$.

**Output:**
In ra số lớn nhất có thể tạo chia hết cho $90$. Nếu ta không tìm được số nào, in ra $-1$.

---

**Bài $5:$** **MEDIUM**
đề tự nghĩ

**Code AC:** https://ideone.com/oVzCTK

Cho $n$ tấm thẻ $1, 2, ..., n$. Tấm thẻ $i$ có giá trị $a_i$. Độ tốt của $3$ tấm thẻ $i, j, k$ $(i \ne j, i \ne k, j \ne k)$ là $a_i * a_j * a_k$. Tìm độ tốt lớn nhất.

**Input:**
Dòng đầu gồm số nguyên $n$ $(3 \le n \le 10^5)$.
Dòng tiếp theo gồm $n$ số nguyên $a_1, a_2, ..., a_n$ $(|a_i| \le 10^6)$.

**Output:**
In ra độ tốt lớn nhất của $3$ tấm thẻ tối ưu.

---

**Bài $6:$** **MEDIUM**
https://codeforces.com/contest/1725/problem/G

**Code AC:** https://ideone.com/cydZat


Định nghĩa $2$ số **nguyên dương** $a$ và $b$ $(a < b)$ là độ dài của hai cạnh trong tam giác vuông như trong hình minh họa. Một số nguyên $x$ được coi là **phù hợp** khi $x$ = $b^2 - a^2$. Tìm số **phù hợp** nhỏ thứ $n$.

**Input:**
Một dòng chứa số nguyên dương $n$ $(1 \le n \le 10^9)$.

**Output:**
Số **phù hợp** nhỏ thứ $n$.

---

**Bài $7:$** **MEDIUM**
https://codeforces.com/contest/348/problem/A

**Code AC:** https://codeforces.com/contest/348/submission/139465449

$n$ người bạn rủ nhau chơi bài bạc. Trong mỗi một ván thì phải có $1$ người giám sát (ra coi chừng công an), $n - 1$ người còn lại được chơi. Mỗi người thì ta biết được số ván anh ta muốn trở thành người chơi, không phải đi giám sát: người thứ $i$ muốn chơi ít nhất $a_i$ ván. Tìm số ván bài bạc ít nhất họ cần chơi để thoả mãn tất cả mọi người.

**Input:**
Dòng đầu tiên gồm số $n$ $(3 \le n \le 10^5)$ - số người.
Dòng tiếp theo gồm $n$ số nguyên $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ - người $i$ muốn chơi ít nhất $a_i$ ván.

**Output:**
Số ván ít nhất họ cần chơi để thoả mãn mong muốn của tất cả mọi người.

---

**Bài $8$: MEDIUM**
https://codeforces.com/contest/351/problem/E

**Code AC:** https://codeforces.com/contest/351/submission/171292134

Cho một dãy $a$ có $n$ số $a_1, a_2, ..., a_n$. FIT có thể nhân $1$ số số trong dãy $a$ với $-1$. FIT ghét nghịch đảo, nên FIT muốn dãy sau khi biến đổi của mình có số nghịch đảo nhỏ nhất có thể.
Một nghịch đảo là một cặp $(i, j)$ thoả mãn $i < j$ và $a_i > a_j$.

**Input:**
Dòng đầu chứa số nguyên $n$ $(1 \le n \le 2000)$ - số phần tử của dãy.
Dòng sau chứa $n$ số nguyên $a_1, a_2, ..., a_n$ $(|a_i| \le 10^5)$

**Output**:
In ra số nghịch đảo nhỏ nhất khi biến đổi tối ưu.

---

**Bài $9:$ HARD**
https://codeforces.com/contest/1508/problem/B?f0a28=1

**Code AC:** https://codeforces.com/contest/1508/submission/115827573

Một hoán vị $a_1, a_2, ..., a_n$ của $1, 2, ..., n$ được gọi là gần tăng dần khi $a_{i + 1}$ $\ge$ $a_i - 1$ với $i$ từ $1$ đến $n - 1$.
FIT có một danh sách các hoán vị gần tăng dần của $1, 2, ..., n$ theo thứ tự từ điển, và FIT muốn tìm hoán vị gần tăng dần thứ $k$.

**Input:**

Dòng đầu chứa số nguyên $t$ $(1 \le t \le 10^5)$ - số test.
Mỗi câu hỏi gồm $2$ số nguyên $n$ và $k$ $(1 \le n \le 10^5$, $1 \le k \le 10^{18})$.
Đảm bảo rằng tổng của $n$ tất cả các test không vuợt quá $10^5$.

**Output:**
In ra hoán vị gần tăng dần thứ $k$ hoặc $-1$ nếu không tồn tại.

---

**Bài $10:$ HARD**
https://codeforces.com/problemset/problem/1721/D

**Code AC:** https://codeforces.com/contest/1721/submission/170799359

FIT có hai dãy $a$ và $b$, mỗi dãy gồm $n$ số nguyên. Gọi $f(a, b)$ là:

* Tạo dãy $c$ gồm $n$ số nguyên, $c_i = a_i$ ^ $b_i$ (phép toán XOR bit).
* Giá trị của dãy là $c_1$ $\&$ $c_2$ $\&$ $...$ $\&$ $c_n$ (phép toán AND bit).

Tìm giá trị tối đa của $f(a, b)$ nếu FIT có thể sắp xếp các số trong dãy $b$ một cách tuỳ ý.

**Input:**
Dòng đầu tiên gồm số nguyên $t$ $(1 \le t \le 10^4)$ - số test.
Với mỗi test, dòng đầu gồm số $n$ $(1 \le n \le 10^5)$.
Dòng tiếp theo gồm $n$ số nguyên $a_1, a_2, ..., a_n$ $(0 \le a_i < 2^{30})$.
Dòng tiếp theo gồm $n$ số nguyên $b_1, b_2, ..., b_n$ $(0 \le b_i < 2^{30})$.
Tổng $n$ tất cả các test không vượt quá $10^5$.

**Output:**
Giá trị MAX của $f(a, b)$ khi có thể sắp xếp $b$ một cách tuỳ ý.