---
# System prepended metadata

title: Contest Quý Mão 2023

---

---
title: Contest Quý Mão 2023
---
<style>
    .markdown-body { max-width: 2048px; }
</style>

$\Huge \text{Contest Quý Mão 2023}$

## ISTRIANGLE (Bài 1)

$Tết$ - truyền thống quý báu của ông cha ta để lại - là dịp để mọi người trong gia đình tụ họp, sum vầy bên nhau. Đặc biệt, khi chúng ta cùng nhau ngồi bên đống lửa nấu bánh chưng có lẽ đấy là khoảnh khắc ấm áp nhất. 

Và gia đình **LVT** (a.k.a **Who_You_Knows_Who**) cũng không phải ngoại lệ. Tết đến, **LVT** cùng gia đình trở về quê sau một năm xa cách. Và trùng hợp thay, nhà **LVT** cũng nấu bánh chưng, thế là **LVT** bị bắt đi lấy củi để nấu bánh - một công việc vô cùng nhẹ nhàng đối với **LVT**. Sau khi lấy $N$ cây củi với những độ dài khác nhau, vì quá nhàn rỗi nên **LVT** quyết định ngồi nghịch củi. 

Trong quá trình nghịch ~~ngu~~ ấy, **LVT** đã xếp thành rất nhiều hình khác nhau, tuy nhiên có hai hình **LVT** không thể xếp được, đó là **hình tam giác** và **hình bóng của em :(**. Khi xếp **hình tam giác** thì **LVT** nhận ra rằng trong đống củi đó có ba cây củi không thể xếp thành hình tam giác được. Vì thường xuyên trốn học toán nên **LVT** không biết làm sao để biết được có tồn tại những cây củi đấy hay không. 

Vì thế, các bạn coder trong **HBCCoder** hãy giúp đỡ để anh ấy có một cái tết ấm no hạnh phúc nhé!

### **INPUT**
- Dòng thứ nhất gồm một số nguyên $N$ là số cây củi mà **LVT** đã lượm về $(3 \le N \le 10^5)$.
- Dòng tiếp theo gồm $N$ số nguyên $A_1, A_2, A_3, ... , A_N$ là độ dài các cây củi mà **LVT** đã lượm về $(1 \le A_i \le 10^9)$.
### **OUTPUT**
- Gồm một dòng, nếu tồn tại những cây củi không thể ghép thành hình tam giác thì in ra $"$YES$"$, ngược lại thì in ra $"$NO$"$.

### **SCORING**
- Subtask $1$ $(30\%$ số điểm$)$: $N \le 10^2$
- Subtask $2$ $(40\%$ số điểm$)$: $N \le 10^3$
- Subtask $3$ $(30\%$ số điểm$)$: $N \le 10^5$

## DICEGAME (Bài 2)
Nhân dịp *Tết đến xuân về*, nhóm bạn đã chơi với nhau từ lâu bao gồm **TH, TA, KH** và **A** đã quyết định sẽ gặp nhau và chơi ~~nhau~~ những bộ môn thú vị ngày tết như học ~~đánh~~ bài,... 

Tuy nhiên, sau một khoảng thời gian khá lâu, vì thua quá nhiều nên **TA** rất bực tức và đề xuất một trò chơi mới. Đó là Tài xỉu, một bộ môn phải dùng đến kĩ năng ~~may mắn~~ thượng thừa của người chơi để đoán nó là **chẵn (xỉu)** hay **lẻ (Tài)**. Nhưng vì giận quá nên **TA** đã mất khôn, **TA** đã rủ **TH** (người chơi thắng nhiều nhất) chơi cùng anh và biến tấu lại trò chơi theo ý của **TA**. Sau đó, **TA** còn kéo theo cả **KH** và **A** vào làm kế toán và trọng tài. 

Luật của trò chơi như sau: **A** sẽ là người tung xúc xắc. Trong mỗi lượt chơi, điểm ở mặt trên của xúc xắc sẽ được cộng cho **TA** còn ở mặt dưới sẽ cộng cho **TH**. Tức là nếu **TA** được $x$ $(1 \le x \le 6)$ điểm thì **TH** sẽ được $7 - x$ điểm. Còn **KH** sẽ đảm nhiệm vai trò ghi lại số điểm và cộng lại cho cả hai người.

Sau một số lượt chơi, **KH** đã thấy rằng tổng điểm mà **TA** đạt được là $N$. Và nhiệm vụ của anh là tính tổng số điểm nhỏ nhất và lớn nhất có thể của **TH**. Tuy nhiên, vì con quỷ lười trong anh đã thức tỉnh nên anh đã bỏ ngỏ trò chơi giữa chừng. Vì là một người khó tính nên **TA** đã rất khó chịu về việc đó, rồi giận dỗi **KH**. Vì thế, các bạn hãy giúp cho **KH** tính số điểm đó để ~~giảng~~ giải hòa với **TA** nhé!!!


### **INPUT**
- Gồm $1$ dòng duy nhất chứa số nguyên $N$ là tổng số điểm của **TA** $(N \le 10^{10})$. 

### **OUTPUT**
- In ra $2$ dòng theo thứ tự là tổng số điểm nhỏ nhất và lớn nhất có thể của **TH**.

### **SCORING**
- Không có bất cứ ràng buộc nào thêm.

## HT (Bài 3)
Nhân dịp Tết Quý Mão $2023$, **An** được $1302$ (a.k.a ...) tặng cho $2$ quyển Sử Thi Hy Lạp : $Ἰλιάς$ và $Ὀδύσσεια$. Sau khi đọc, **An** đã thành thạo $7749$ phép thần thông, được $10$ điểm Văn ~~(có dấu phẩy ở giữa)~~, hủy diệt môn Hóa với thành tích $9$ phẩy cả năm ~~($9$ lật ngược)~~. **An** liền tìm hiểu về $Ὅμηρος$ - tác giả của $2$ quyển sử thi để tìm hiểu tại sao nó lại có sức mạnh khủng khiếp đến vậy. Cuối cùng **An** hiểu ra, ông khi xưa làm nghề **hát rong** để truyền bá $2$ quyển sử thi trên. Từ đó An trở nên yêu **hát rong** và **An** quyết định đưa **hát rong** vào chủ đề của bài hôm nay. 

Cho trước một xâu $S$, bạn hãy tìm các xâu con của $S$ sao cho khi sắp xếp lại các kí tự trong xâu con ấy, ta được xâu **hatrong**

### **INPUT**
- Gồm một dòng chứa xâu $S$ $(7 \le |S| \le 10^6$ với $|S|$ là độ dài của xâu $S$).
### **OUTPUT**
- Dòng đầu in ra số nguyên $n$ : Số lượng xâu con của $S$ thỏa mãn đề bài 
- $n$ dòng tiếp theo, mỗi dòng in ra xâu con tìm được. Nếu có nhiều xâu con giống nhau thì vẫn in ra chúng miễn sao đảm bảo in đúng thứ tự xuất hiện của chúng trong xâu $S$. 
### **SCORING**
- Subtask $1$ $(40\%$ số điểm$)$: $|S| \le 10^3$
- Subtask $2$ $(60\%$ số điểm$)$: $|S| \le 10^6$
## MINSTEP (Bài 4)
Lô tô là một trò chơi truyền thống trong dịp Tết của người Việt Nam. Chính vì thế, nhân dịp Tết Quý Mão $2023$, có một nhóm bạn đã tụ tập lại để ~~play~~ chơi chung với nhau. Trong nhóm bạn ấy, có một bạn vô cùng đặc biệt và đam mê với môn tin học tên là **LK**. 

Tuy nhiên, vì đã chơi quá lâu nên **LK** cảm thấy chán nản với những ô vuông trong tờ lô tô. Vì thế **LK** quyết định tự tạo ra một trò chơi cho riêng mình bằng cách sau:

Đầu tiên, ~~là tiền đâu~~ **LK** sử dụng tờ lô tô đang chơi khi nãy rồi nới rộng nó đến mức không thể tưởng tượng được. Tiếp đến **LK** xóa hết số trên tờ lô tô rồi thay bằng những số theo quy luật sau:

Với các dòng được đánh số từ $1$ theo thứ tự từ trên xuống dưới và các cột được đánh số từ $1$ theo thứ tự từ trái sang phải. Ô thứ $i, j$ *(tức là ô vuông nằm trên giao điểm của dòng thứ $i$ và cột thứ $j$)* sẽ có giá trị là $i * j$.

Cuối cùng, với tâm hồn và thân xác trẻ con của mình, **LK** vẽ một con robot xuất phát ở ô $(1,1)$ và sẽ đi đến ô lô tô có giá trị là $N$. Trong mỗi bước đi, con robot của **LK** chỉ có thể đi đến một trong bốn ô kề cạnh ô mà nó đang đứng. Và **LK** muốn biết được số bước đi ít nhất của robot để nó có thể đến ô lô tô có giá trị là $N$. Nhưng vì còn quá nhỏ nên **LK** không thực hiện được việc này. Chính vì thế, các bạn hãy giúp đỡ cho bạn nhỏ **LK** nhóa!!! 

$($Tất nhiên robot sẽ không được phép đi ra ngoài bảng lô tô$)$

### **INPUT**
- Gồm $1$ dòng chứa số nguyên $N$, là giá trị của ô lô tô mà robot phải đi đến $(N \le 10^{12})$.
### **OUTPUT**
- In ra $1$ số nguyên duy nhất là số bước ít nhất mà robot có thể đi đến các ô có giá trị $N$.
### **SCORING**
- Subtask $1$ $(50\%$ số điểm$)$: $N \le 10^3$
- Subtask $2$ $(30\%$ số điểm$)$: $N \le 10^6$
- Subtask $2$ $(30\%$ số điểm$)$: $N \le 10^{12}$
## ROBOT (Bài 5)

**Thin** là một người đam mê với công nghệ thông tin. Đặc biệt là trí tuệ nhân tạo. Chính vì thế, những con robot là thú vui duy nhất của **Thin**. Nhân dịp **Tết Quý Mão $2023$** này **Thin** đã quyết định sẽ ~~báo~~ mua một con robot có hình con mèo bằng tiền của bố mẹ vào đúng mùng $1$ tết. 

Tuy nhiên, để có được quà từ bố mẹ thì bắt buộc **Thin** phải trải qua $1$ thử thách vô cùng khó nhằn. Vì cũng là dân chuyên tin nên bố mẹ **Thin** đã đưa ra thử thách như sau: Hãy lập trình cho một con robot của **Thin** để nó có thể biến đổi một xâu kí tự $S$ với $2$ câu lệnh $R$ và $L$ theo quy luật sau:

Với câu lệnh $L$, sẽ dời các kí tự trong dãy từ phải sang trái, kí tự đầu tiên của dãy sẽ chuyển xuống kí tự cuối cùng của dãy.

Ví dụ: $abcde$, trạng thái dãy sau câu lệnh $L$ là $bcdea$.

Với câu lệnh $R$, sẽ dời các kí tự trong dãy từ trái sang phải, kí tự cuối cùng của dãy sẽ chuyển lên kí tự trên cùng của dãy.

Ví dụ: $abcde$, trạng thái dãy sau câu lệnh $R$ là $eabcd$.

Tuy nhiên, vì còn quá ~~trẻ trâu~~ nhỏ và non nên **Thin** không thể tự lập trình cho con robot của mình nên dựa vào mối quan hệ rộng của bố mẹ với các **admin HBCcoder**, **Thin** đã nhờ các bạn ấy giúp đỡ. Chính vì thế, các bạn hãy cố gắng hết sức mình để có thể mang lại cho anh ấy một con Robot **Quý Mão** nhé!!!

### **INPUT**

- Dòng thứ nhất chứa xâu $S$ $(|S| \le 10^5$ với $|S|$ là độ dài của xâu $S$$)$.
- Dòng thứ $2$ chứa xâu $A$ chỉ gồm các kí tự $L$ và $R$ viết liền nhau $(|A| \le 10^6)$.

### **OUTPUT**

- In ra màn hình xâu $S$ sau khi biến đổi.

### **SCORING**

- Subtask $1$ $(50\%$ số điểm$)$: $|S| \le 255$
- Subtask $2$ $(50\%$ số điểm$)$: $|S| \le 10^6$.

## BEAUTIPASS (Bài 6)

Dạo gần đây, những ngày giáp **Tết Nguyên Đán** đã tồn tại rất nhiều luồng ý kiến khác nhau về việc có nên giao nhiều **Bài tập về nhà** trong dịp **Tết** cho học sinh hay không. Có những ý kiến từ dư luận, báo chí về việc nhà trường, giáo viên cho rằng nên giao nhiều bài tập về nhà trong dịp nghỉ Tết Nguyên đán cho học sinh để tạo sự quan tâm của phụ huynh và có tác động tích cực. Tuy nhiên, với tình hình ~~lười học~~ phức tạp hiện nay của các bạn học sinh nên **hiệu trưởng LT** đã quyết định sẽ không giao bài tập về nhà.

**NHƯNG** với tính cách **bủh dảk lmao** của mình và đặc biệt thích lấy ~~le~~ lòng các bạn nữ ~~(đặc biệt là bạn K)~~ nên anh ấy đã xin phép thầy cô giao **BTVN** trong dịp **Tết**. Vì **LT** đã có lòng thì giáo viên cũng có ~~nước chấm~~ dạ. Thế nên giáo viên chủ nhiệm của **LT** quyết định sẽ và chỉ giao **BÀI TẬP** **Tết** cho mỗi **LT**. Nhưng vì yêu thương học trò của mình nên giáo viên đã ban cho **LT** một ân huệ đó là chỉ giao $1$ bài tập cho **LT** và phù hợp với đam mê số nguyên tố của anh. Nội dung của bài tập như sau: 

Cho $N$ số nguyên (vừa âm vừa dương). Một đoạn được gọi là **đẹp** nếu như vị trí của số đầu và số cuối của đoạn đó đều là số nguyên tố. Và nhiệm vụ mà **thầy/cô giáo** của **LT** giao cho đó là tìm đoạn **đẹp** có tổng lớn nhất trong $N$ số nguyên kia. Và deadline cho **LT** là trước mùng ~~G.O.A.T CR~~ 7 **Tết**.

Tuy nhiên, như các bạn đã biết (hoặc chưa biết) thì **LT** là một cậu học sinh rất thông minh nhưng lại vô cùng lười biếng. Vì thế, sau một phút huy hoàng của mình trên lớp thì anh ấy dường như trở thành một trò hề cho chính bản thân của mình. Chính vì thế các bạn hãy giúp đỡ anh ấy để có một cái **Tết** ấm no bên gia đình nhé :100: :100: :100:. 
### **INPUT**

- Dòng đầu chứa số nguyên dương $N$ $(N \ge 2)$.
- Dòng thứ 2 chứa $N$ số nguyên $a_1, a_2, ..., a_N (a_i \le 10^6)$.

### **OUTPUT**

- In ra một dòng duy nhất là kết quả của bài toán.

### **SCORING**

- Subtask $1$ $(50\%$ số điểm$)$: $N \le 10^2$.
- Subtask $2$ $(30\%$ số điểm$)$: $N \le 3.10^3$.
- Subtask $3$ $(20\%$ số điểm$)$: $N \le 10^5$.

## PERPAIR (Bài 7)
Nhân dịp năm mới *Quý Mão $2023$*, đất nước **HBCcoder** muốn tuyển chọn một cặp đôi hoàn hảo để trình diễn màn khiêu vũ tuyệt đẹp vốn là văn hóa lâu đời của đất nước.

Một cặp đôi được gọi là hoàn hảo nếu cặp đôi đó có cả nam và nữ, chênh lệch chiều cao của hai người không được vượt quá $K$ milimet và chiều cao của bạn nữ không được cao hơn bạn nam.

Đất nước đã tuyển chọn được $N$ vũ công gồm cả nam và nữ và muốn biết có bao nhiêu cách để chọn ra đúng một cặp đôi hoàn hảo.

### **INPUT**

- Dòng đầu ghi hai số nguyên dương $N, K(N ≤ 10^5, K ≤ 5.10^2)$.
- Dòng tiếp theo ghi $N$ dòng bao gồm $2$ số là giới tính $g_i$ và chiều cao $h_i$ của vũ công thứ $i$ $(g_i = 1$ thì vũ công thứ $i$ là nam, ngược lại là nữ).

### **OUTPUT**

- Ghi ra $1$ số duy nhất là số lượng cách có thể chọn được.
### **SCORING**

- Subtask $1$ $(30\%$ số điểm$)$: $N \le 10^2$
- Subtask $2$ $(40\%$ số điểm$)$: $N \le 10^3$
- Subtask $3$ $(30\%$ số điểm$)$: $N \le 10^5$




| Top | Users              | Point       |
| :---: | :------------------: | :-----------: |
| 1   | Phongkhonglongvong | **385/700** |
| 2   | HoangKhanh         | **328/700** |
| 3   | danntt_0103        | **176/700** |
| 4   | bodzhaha           | **104/700**  |
