---
# System prepended metadata

title: Đề

---

## Bài 1

#### Đề bài
Cho một số nguyên dương $n$ $(1 \le n \le 100)$ và dãy số nguyên $a$ gồm $n$ phần tử. 
Hãy đếm số bộ ba số $(a_i, a_j, a_k)$ $(1 \le i < j < k \le n)$ thỏa mãn $a_i, a_j, a_k$ là độ dài ba cạnh của một tam giác.

#### Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 100)$.
- Dòng thứ hai chứa $n$ số nguyên dương $a_i$ $(-10^9 \le a_i \le 10^9)$ 

#### Dữ liệu ra
- Gồm một số duy nhất là số bộ ba thỏa mãn.

#### Ví dụ
| Input | Output |
| -------- | -------- | 
| 4 <br /> 1 3 5 7   | 1     | 
| 5 <br /> 2 3 5 7 8 | Text     | 

## Bài 2

#### Đề bài
Cho mảng $P$ gồm $n$ phần tử là hoán vị của $(1, 2, 3,... n)$. Tìm vị trí của phần tử có giá trị là $x$ $(1 \le x \le n)$.

#### Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 10^5)$.
- Dòng thứ hai gồm $n$ số nguyên dương của mảng $P$. Các phần tử cách nhau bởi một dấu cách và là hoán vị của bộ $(1, 2, 3,... n)$.

#### Dữ liệu ra
- Gồm một dòng duy nhất in ra $n$ số. Số thứ $i$ là vị trí của phần tử trong mảng $P$ có giá trị là $i$.

#### Ví dụ
| Input | Output |
| ----- | ------ | 
| 7 <br /> 6 3 4 2 7 1 5 | 6 4 2 3 7 1 5 |


#### Giới hạn

## Bài 3

#### Đề bài
Khi viết các số tự nhiên tăng dần từ $1, 2, 3,...$ liên tiếp nhau, ta được các chữ số vô hạn $1234567891011121314...$
Yêu cầu: Bạn được cho $q$ câu hỏi, mỗi câu hỏi gồm một số nguyên dương $a_i$ $(1 \le i \le q)$. Hãy in ra chữ số ở vị trí thứ $a_i$ trong dãy chữ số vô hạn trên. 

#### Dữ liệu vào

- Dòng đầu tiên chứa số nguyên dương $q$ $(1 \le q \le 10^5)$ là số câu hỏi.
- $q$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $a_i$ $(1 \le a_i \le 10^5)$.

#### Dữ liệu ra
- Gồm một dòng chứa $q$ chữ số cần tìm, các số cách nhau bởi dấu cách.

#### Ví dụ
| Input | Output | 
| -------- | -------- | 
| q <br /> vjvj  | Text     | 
| q <br /> vjvj  | Text     | 



## Bài 4

#### Đề bài
Một dãy gồm $n$ số nguyên không âm $a_1, a_2,... a_n$ được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả $n-1$ khoảng trắng.

Yêu cầu: Hãy đặt $x$ dấu cộng và 
$n-1-x$ dấu trừ vào $n-1$ khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

#### Dữ liệu vào
- Dòng đầu chứa hai số nguyên $n, k$ $(0 \le k < n \le 10^4)$.
- Dòng thứ hai chứa $n$ số nguyên không âm $a_1, a_2,... a_n$ $(0 \le a_i \le 10^6)$.

#### Dữ liệu ra
- Một số nguyên là giá trị của biểu thức lớn nhất đạt được.

#### Ví dụ
| Input | Output |
| ----- | ------ | 
| 5 2 <br /> 28 9 5 1 69 | 100 |

#### Giới hạn

- Subtask 1: $(70\%)$ $n \le 10^4$.
- Subtask 1: $(30\%)$ Không có giới hạn gì thêm.

## Bài 5

#### Đề bài
Cho số nguyên dương $n$ $(1 \le n \le 10^5)$ và dãy số nguyên $a$ gồm $n$ phần tử. Đoạn con là một dãy liên tiếp các phần tử được lấy từ dãy ban đầu.
Yêu cầu: Tìm đoạn con có tổng lớn nhất.

#### Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 100000)$.
- Dòng thứ hai chứa $n$ số nguyên dương $a_i$ $(-10^9 \le a_i \le 10^9)$ 

#### Dữ liệu ra
- Gồm một số duy nhất là tổng của đoạn con lớn nhất tìm được.

#### Ví dụ
| Column 1 | Column 2 | Column 3 |
| -------- | -------- | -------- |
| Text     | Text     | Text     |


#### Giới hạn
- Subtask 1: $(30\%)$ $1 \le n \le 100$.
- Subtask 2: $(40\%)$ $1 \le n \le 1000$.
- Subtask 3: $(30\%)$ Không có giới hạn gì thêm.

## Bài 6

#### Đề bài
Một số nguyên tố được coi là đẹp nếu tổng các chữ số của nó cũng là một số nguyên tố. Hãy viết chương trình in ra các số nguyên tố đẹp nhỏ hơn $n$ $(3 \le n \le 10^6)$.

#### Dữ liệu vào
- Gồm một số nguyên dương $n$ duy nhất $(3 \le n \le 10^6)$.

#### Dữ liệu ra
- Gồm một dòng chứa tất cả các số nguyên tố đẹp nhỏ hơn $n$.

#### Ví dụ


| Column 1 | Column 2 | Column 3 |
| -------- | -------- | -------- |
| Text     | Text     | Text     |

## Bài 7

#### Đề bài
Ta cần cắt một hình chữ nhật có kích thước $m \times n$ $(1 \le m, n \le 100)$ thành một số ít nhất các hình vuông có kích thước nguyên dương và có cạnh song song với cạnh của hình chữ nhật ban đầu. Biết rằng khi cắt một hình chữ nhật bất kỳ chỉ cắt được theo phương song song với một trong các các cạnh của hình chữ nhật đó.

#### Dữ liệu vào
- Gồm một dòng chứa hai số nguyên dương $m$, $n$ $(1 \le m, n \le 100)$.

#### Dữ liệu ra
- Dòng thứ nhất ghi số $d$ là số hình vuông ít nhất cắt ra.
- Dòng thứ hai gồm $d$ số ghi độ dài cạnh của $d$ hình vuông cắt ra được, mỗi số cách nhau một dấu cách.

#### Ví dụ
| Input | Output | 
| ----- | -------| 
| 5 6   | 5 <br /> 2 2 2 3 3| 

## Bài 8

#### Đề bài
Vũ đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai Phúc về thành quả vừa đạt được. Tuy nhiên,  khi Vũ vừa ra khỏi phòng để gọi anh trai thì cô em Khánh chạy vào phòng và xé rách cuộn giấy thành một số mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã viết. Bây giờ Vũ không thể nhớ chính xác mình đã viết số gì. Vũ chỉ nhớ rằng đó là một số rất lớn. Để làm hài lòng cậu em trai, Phúc quyết định truy tìm  số nào là lớn nhất mà Vũ đã có thể viết lên cuộn giây trước khi bị xé. Bạn hãy giúp Phúc làm việc này.
          Ghi ra số lớn nhất đã có thể viết trên cuộn giấy trước khi bị xé rách.
#### Dữ liệu vào
Ghi một hoặc nhiều dòng. Mỗi dòng là một xâu chứa các kí tự là chữ số từ $0$ tới $9$. Số dòng không vượt quá $100$. Mỗi dòng ghi từ $1$ đến $100$ chữ số. Bảo đảm rằng có ít nhất một dòng mà chữ số đầu tiên khác $0$.

#### Dữ liệu ra

#### Ví dụ
| Input | Output |
| ----- | ------ | 
| 2 <br /> 20 <br /> 004 <br /> 66|66220004|

            
## Bài 9

#### Đề bài

Cho số nguyên dương $n$. Xác định xem có tồn tại cặp số nguyên $(a,b)$ thỏa mãn $3^a + 5^b = n$, nếu có hãy in ra một cặp số $(a,b)$ thỏa mãn.

#### Dữ liệu vào
- Gồm một số nguyên dương $n$ duy nhất $(1 \le n \le 10^{18})$.

#### Dữ liệu ra

- Nếu tìm được cặp số $(a,b)$ thỏa mãn, in ra hai số $a$ và $b$ cách nhau một dấu cách. Ngược lại, in ra $-1$.

#### Ví dụ
| Input | Output | 
| ----- | ------ | 
| 106   |  4 2   | 
| 1024  |   -1   | 

          
## Bài 10: PASSWORD

#### Đề bài

Sau thời gian dài không sử dụng Email, Khang đã quên mật khẩu đăng nhập. Do hay quên nên khi tạo tài khoản, Khang đã lưu lại một xâu kí tự $S$ đã được mã hóa. Xâu đó có thể giải mã như sau:
- Cho $T$ là một xâu rỗng
- Với mỗi $i = 1, 2, ... |S|$ theo thứ tự này, ta làm như sau: ($|S|$ biểu thị độ dài xâu $S$)
    + Nếu $S_i$ = `R`, đảo ngược xâu $T$;
    + Ngược lại, hãy thêm kí tự đó vào cuối xâu $T$;
- Sau thao tác trên, nếu có 2 kí tự giống nhau liên tiếp trong $T$, hãy xóa hai kí tự đó. Lặp lại thao tác này đến khi xâu $T$ không còn hai kí tự liên tiếp như nhau.

Sau khi giải mã xâu $S$, Khang sẽ có được xâu $T$ là mật khẩu Email.

**Yêu cầu:** Cho xâu $S$ đã được mã hóa, hãy giúp Khang tìm lại mật khẩu Email.

#### Dữ liệu vào
- Gồm một dòng duy nhất chứa xâu $S$ $(1 \le |S| \le 500000)$. Xâu $S$ chỉ bao gồm các chữ cái tiếng Anh viết thường và `R`.

#### Dữ liệu ra
- Gồm một dòng duy nhất là mật khẩu Email của Khang.

#### Ví dụ


| Input | Output | 
| -------- | -------- | 
| nnaRbbhcckRng | khang |
| helloworldRhelloworld | | 



          
## Bài 11: ORXOR

#### Đề bài
Cho dãy số $A$ độ dài $n$. Ta chia dãy thành nhiều đoạn con liên tiếp không rỗng. Giá trị của một đoạn được tính bằng cách thực hiện phép toán `XOR` trên các phần tử trong dãy.

**Yêu cầu:** Tìm cách chia đoạn sao cho `OR` của giá trị các đoạn là nhỏ nhất.

#### Dữ liệu vào


#### Dữ liệu ra


#### Ví dụ


| Input | Output | 
| -------- | -------- | 
| 3 <br/> 1 5 7 | 2 |
| helloworldRhelloworld | | 

#### Giải thích
- giải thích or xor :v
- vd: (1|5)^7 = 2

#### Ghan
n <= 20


          
## Bài 12: MACHINE

#### Đề bài
Có $n$ chi tiết sản phẩn cần được gia công trên 2 máy $A$ và $B$. Thời gian gia công chi tiết $i$ trên máy $A$ là $a_i$, trên máy $B$ là $b_i$. Biết rằng:
- Mỗi chi tiết sản phẩm cần hoàn thành gia công trên máy $A$ thì mới chuyển sang gia công trên máy $B$.
- Mỗi thời điểm, một máy chỉ được gia công nhiều nhất một chi tiết sản phẩm.

**Yêu cầu:** Hãy tìm trình tự gia công các chi tiết trên 2 máy sao cho việc hoàn thành $n$ chi tiết là sớm nhất có thể.

#### Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $n$ $(1 \le n \le 10^5)$ là số chi tiết máy.
- Dòng thứ hai gồm $n$ số nguyên dương $a_i$ $(1 \le a_i \le 10^5)$ là thời gian gia công các chi tiết trên máy $A$.
- Dòng thứ hai gồm $n$ số nguyên dương $b_i$ $(1 \le a_i \le 10^5)$ là thời gian gia công các chi tiết trên máy $B$.

#### Dữ liệu ra
- Dòng đầu tiên gồm một số duy nhất là thời điểm sớm nhất có thể hoàn thành.
- Dòng thứ hai gồm $n$ số nguyên dương biểu thị trình tự gia công các chi tiết máy.

#### Ví dụ


| Input | Output | 
| -------- | -------- | 
| 3 <br/> 2 3 1 <br/> 1 2 3| 7 |
| 6 <br/> 3 2 5 4 6 7 <br/> 1 2 4 3 7 4 | 28 | 

#### Giải thích

#### Ghan
- (20%) n <= 10
- (80%) n <= 10^5




          
## Bài 13: SQUARE

#### Đề bài
Cho số nguyên dương $n$. Đếm số cặp $(i, j)$ thỏa mãn:
- $i$, $j$ là các số nguyên dương không quá $n$.
- $i \times j$ là số chính phương.

#### Dữ liệu vào
- Gồm một số nguyên dương $n$ duy nhất $(1 \le n \le 2 \times 10^5)$.

#### Dữ liệu ra
- In ra một số là kết quả cần tìm.

#### Ví dụ


| Input | Output | 
| -------- | -------- | 
| 4 | 6 |
| 254 | 869 | 

#### Giải thích



