[LHPIC2425]: Statement contest 2

# [LHPIC2425]: CONTEST 2 *Cốt truyện chính: Gấu chuẩn bị đi chơi Noel, được ông già Noel dẫn tới Bắc Cực, thực hiện thử thách, nhận quà* ## KHỞI HÀNH (Biển số đẹp) (Huy Minh)  Vậy là tháng 12 đã đến, trong cái giá lạnh của mùa đông và không khí hân hoan chào đón Giáng Sinh ~~và cả thi học kì~~, Gấu cũng tất bật chuẩn bị cho sự kiện này. Bất thình lình, Gấu nhận được tin nhắn mời đến Nhà ga LHPIC, chọn một phương tiện để đến Bắc Cực để trải nghiệm làm trợ lí của ông già Noel. Trước một cơ hội ngàn năm chưa chắc có một như vậy, Gấu quyết định đến ga. Ở đây, Gấu thấy có vô vàn phương tiện của đủ các kiểu, mỗi phương tiện có một mã xác định. Gấu quyết định chỉ chọn một trong số đó có mã xác định đẹp để đi. Một mã đẹp theo định nghĩa của Gấu thỏa một trong các điều kiện sau: * Đối xứng (Đọc từ trái qua giống với đọc từ phải qua) * Một nửa xâu đầu giống với một nửa xâu cuối ($ACDA|ACDA$) * Số lượng số chữ số khác nhau nhỏ hơn hoặc bằng căn bậc hai độ dài dãy * Tổng của các chữ số trong dãy chia hết cho $10$ Hiện trong Nhà ga đang có $N$ phương tiện, mỗi phương tiện có một mã xác định có độ dài $M$. Hãy giúp Gấu xác định xem phương tiện nào có mã xác định đẹp nhé. #### Constraint $1\le N, M\le 10^{3}$ #### Input * Dòng đầu gồm 2 số nguyên dương $N$, $M$ * $N$ dòng tiếp theo, mỗi dòng gồm một xâu gồm toàn kí tự số có độ dài $M$. #### Output Gồm $N$ dòng, mỗi dòng là $YES$ nếu phương tiện đó có mã xác định đẹp, ngược lại in ra $NO$. #### Scoring * Subtask 1 (50%): $1\le N, M\le 100$ * Subtask 2 (50%): $1\le N, M\le 10^3$ #### Example | Input | Output | |:------------------------------------------------:|:-----------------------------:| | 5 5 34758 12012 23432 34562 80000 | NO NO YES YES YES | | 1 2 66 | YES | ## TÌM NHÀ (Vị trí) (Khoa)  Sau khi đã đến được Bắc Cực, Gấu lại loay hoay trong vấn đề tìm nhà của ông già Noel. May mắn thay, Gấu lại được một trong những yêu tinh làm việc cho ông già Noel chỉ cách để vào. Cụ thể, yêu tinh đã dẫn Gấu đến một cánh cổng, và cho Gấu xâu $S$ có độ dài vô hạn như sau $12345678910111213...$, dãy được đánh số từ $1$. Sau đó yêu tinh gác cổng tiếp tục đưa Gấu hai số $a,b$. Điều kiện qua cổng nhà của ông già Noel chính là trả lời đúng dãy số từ vị trí $a$ đến $b$, bạn hãy giúp Gấu tìm ra dãy số đó nhé. #### Input - Nhập vào hai số nguyên dương $a,b$ $(1 \le a \le b \le 10^9;b - a \le 10^4)$. #### Output - In ra đáp án giúp Gấu được vào nhà ông già Noel. #### Scoring - Subtask 1: $50\%$ số điểm của bài với $(1 \le a \le b \le 10^5; b - a \le 10^3)$. - Subtask 2: $50\%$ số điểm còn lại của bài với $(1 \le a \le b \le 10^9;b - a \le 10^4)$. #### Sample | Input | Output | |-------|:---------:| | 4 12 | 456789101 | ## VÀO NHÀ (Triple operation) (Khoa)  Do nhà ông già Noel là nơi ông sinh hoạt nên ông không muốn có nhiều yêu tinh vào làm phiền mình, vì thế, ông già Noel quyết định đưa ra lắp đặt một số ổ khóa gồm các số nguyên từ $L$ đến $R$. Mỗi thao tác Gấu được chọn $2$ số nguyên $x,y$ trên ổ khóa và biến đổi $x,y$ lần lượt thành $3x,\frac{y}{3}$ (kết quả làm tròn xuống số nguyên gần nhất). Tìm số thao tác ít nhất sao cho mọi số trên ổ khóa đều bằng $0$ để mở khóa. #### Input - Dòng đầu tiên nhập vào hai số nguyên $L,R$ #### Output - In ra một số nguyên duy nhất là số thao tác ít nhất cần thực hiện để thỏa yêu cầu đề bài. #### Scoring - Subtask 1: $50 \%$ số điểm của bài toán với $1 \le L \le R \le 100;1 \le t \le 1000$. - Subtask 2: $50 \%$ số điểm còn lại của bài toán với $1 \le L \le R \le 2 \times 10^5; 1 \le t \le 10^4$. #### Sample |Input | Output| |:--- | :---: | |2 1 3 2 4| 5 6 ## THỬ THÁCH TUẦN LỘC (Truy vấn bậc thang) (Khoa)  Sau khi tham quan được nhà của ông già Noel, vừa hay cũng là lúc ông già chuẩn bị cưỡi tuần lộc đi ~~cháy phố~~ phát quà. Trái với tưởng tượng, do sự chiều chuộng quá mức và thiếu chế độ ăn dinh dưỡng hợp lí, các chú tuần lộc đã bị vỗ béo, mất đi khối cơ cuồn cuộn như trước. Chính vì vậy khi bay dọc núi để phát quà thì ông già Noel lại lo rằng số tuần lộc kéo xe hiện tại không đủ sức để bay lên núi. Tận dụng trí thông minh sẵn có, đồng thời cũng muốn được vào danh sách "bé ngoan" của ông già Noel, Gấu quyết định giúp ông già Noel tính xem độ mệt của những chú tuần lộc khi bay. Biết rằng sườn núi có $n$ điểm cần phát quà, mỗi điểm có độ cao $a_{i}$. Ông già Noel có $q$ dự định, mỗi dự định ông sẽ phát quà trong đoạn [$l,r$], độ mệt của tuần lộc được tính bởi công thức $f(x)=1\times a_l + 2 \times a_{l+1} + ... + (r-l+1) \times a_r$. Hãy giúp Gấu tính độ mệt của những chú tuần lộc. #### Input - Dòng đầu tiên nhập vào hai số nguyên $n$ và $q$. - Dòng tiếp theo nhập vào $n$ số nguyên dương $a_i$. #### Output - In ra $q$ dòng tương ứng với đáp án từng truy vấn. #### Scoring - Subtask 1: $50\%$ số điểm của bài toán với $(1 \le n,q \le 10^3;|a_i| \le 10^6)$. - Subtask 2: $50\%$ số điểm của bài toán với $(1 \le n,q \le 10^5;|a_i| \le 10^6)$. #### Sample |INPUT | OUTPUT| |:--- | :---: | |4 2 3 4 1 2 1 3 2 4|14 12| ## PHÁT QUÀ TRONG THÀNH PHỐ (TBC) (Huy Minh)  Sau khi tính toán xong ở khu vực núi, Gấu chuyển sang tính toán trong trung tâm thành phố. Trong trung tâm thành phố có khu cao ốc, mỗi khu nhiều tòa, mỗi tòa nhiều tầng, mỗi tầng nhiều nhà, mỗi nhà nhiều trẻ, mỗi trẻ muốn nhiều quà. Hiện ông già Noel có dự định phát quà cho các khu cao ốc, biết rằng khu cao ốc trong dự định này có $n$ tòa, và số lượng món quà mà những đứa trẻ trong tòa thứ $i$ muốn là $a_{i}$. Đến đây, Gấu nghĩ đến một số $K$ và tự hỏi liệu có bao nhiêu đoạn [$L, R$] mà trung bình cộng số lượng quà của các tòa nhà này bằng đúng $K$. #### Constraint * $1\le n\le 10^{5}$ * $1\le |a_{i}|, |k|\le10^9 + 220408$ #### Input * Dòng đầu gồm 2 số nguyên dương $N, K$ * Dòng tiếp theo gồm $N$ số nguyên $a_{i}$ #### Output * Gồm 1 số duy nhất là kết quả của bài toán #### Sample | Input | Output | Explanation | |:----------------:|:------:|:------------------------------:| | 5 2 2 1 3 4 4 | 3 | Có 3 đoạn: [1;1], [1;3], [2;3] | ## XÂU RẮC RỐI (Biến đổi xâu) (Huy Minh)  Rảnh rỗi sinh nông nổi, trong lúc vẫn đang ngồi chờ ông già Noel đi phát quà, Gấu bắt đầu suy nghĩ về cách ông già Noel đặt mật khẩu. Gấu nghĩ rằng có thể ông sẽ cho mình một xâu $S$ gồm $n$ kí tự tiếng Anh in thường và Gấu được phép thực hiện phép đảo xâu (ví dụ $acbd$ thành $dbca$). Bỗng Gấu bật mode overthinking và nghĩ phép biến đổi trên cho phép biến đổi trên đoạn có độ dài lớn hơn $1$, thay vì trên cả xâu, và mật khẩu chính là số lượng xâu phân biệt thu được nếu chỉ được thực hiện 1 phép biến đổi (xem ví dụ để hiểu rõ hơn). #### Constraint * $n\le 2\times 10^5$ #### Input * Dòng đầu là số nguyên dương $n$ * Dòng tiếp theo là xâu $S$ gồm $n$ kí tự tiếng Anh in thường #### Output * Gồm $1$ số nguyên duy nhất có thể là mật khẩu kho quà. #### Scoring * Subtask 1 (40%): $2\le n\le 100$ * Subtask 2 (60%): Không có giới hạn gì thêm #### Sample | Input | Output | Explanation | |:-------:|:------:|:---------------------------------------------:| | 5 aaaab | 4 | Các cách biến đổi: [1;5], [2;5], [3;5], [4;5] | ## VẠCH LÁ TÌM ~~SÂU~~ XÂU (Hoán vị xâu con) (Thanh) Do được bạn giúp bài trên, Gấu lại nghĩ đến một khả năng khác. Gấu nhận được 1 xâu **${S}$** và được gợi ý xâu **${T}$** bởi 1 con tuần lộc. Gấu nghĩ đến trường hợp là nếu số xâu con liên tiếp của **${S}$** là hoán vị của xâu **${T}$** càng nhiều thì khả năng đây là mật khẩu càng cao. Với 2 xâu mà Gấu có được, Gấu muốn đếm xem có bao nhiêu xâu con liên tiếp của **${S}$** là hoán vị của **${T}$**. Được biết hoán vị của một xâu là cách sắp xếp các kí tự trong xâu đó (1 xâu có thể có nhiều hoán vị). #### INPUT - Nhập vào hai xâu **${S}$** và **${T}$** (${1\leq|T|\leq |S| \leq 10^5}$) trên hai dòng khác nhau. #### OUTPUT - Xuất ra 1 số nguyên duy nhất là số xâu con mà Gấu đếm được. #### Sample | Input | Output | Explanation | |------------|--------|-----------------------------------| | abcacb abc | 3 | ***abc***acb a***bca***cb abc***acb*** | ## TAI NẠN (Con kiến) (Huy Minh)  Bây giờ ông già Noel đã đi phát quà trên một trục đường thẳng gồm $N$ tòa cao ốc, tòa thứ $i$ có khoảng cách $a_{i}$ tính từ đầu đường. Không may, ông già Noel trong lúc phát quà đã gặp sự cố nên toàn bộ xe chở quà phải đáp xuống 1 trong các tòa cao ốc. Ông già Noel chấn thương nên điều động tuần lộc đi giao quà. Ông không có thời gian tính nên với mỗi con ông giao số quà của 1 tòa cao ốc, kêu nó đi giao rồi quay lại phát tòa khác. Tính tổng quãng đường tuần lộc phải di chuyển **chia 2** cho mỗi vị trí mà ông hạ cánh (vì Gấu không đi theo ông già Noel, không biết ông đáp xuống đâu nên quyết định tính hết). #### Constraint * $n\le 10^6$ * $1\le a_1<a_2<a_3<$ $...$ $<a_{n-1}<a_n\le 10^9$ #### Input * Dòng đầu là số nguyên $n$ * Dòng tiếp theo gồm $n$ số nguyên $a_i$ tăng ngặt #### Output * Một dòng duy nhất gồm $n$ số nguyên là câu trả lời cho mỗi vị trí #### Sample | Input | Output | Explanation | |:-----------:|:-----------:|:---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:| | 5 1 2 3 4 5 | 10 7 6 7 10 | Khoảng cách của tòa cao ốc thứ 2 đến các tòa còn lại lần lượt là $1,1,2,3$ Tổng quãng đường các con tuần lộc phải di chuyển chia đôi là $(2\times 1 + 2\times 1 + 2\times 2 + 2\times 3)\div 2 = 7$ | ## MỞ KHO QUÀ (Nén xâu) (Thanh)  Ông già Noel đã về, bây giờ ông cho biết mật khẩu của kho quà. Trước hết, ông già Noel kể cho Gấu 1 câu chuyện về cách ông đặt tên cho những chú tuần lộc. Ban đầu khi chỉ có 1 con tuần lộc ông đặt cho nó 1 cái tên bất kì. Vì đã già và không còn nhớ được nhiều cái tên ~~ngoại trừ tên những đứa trẻ hư~~, những chú tuần lộc sau này được đặt tên bằng cách ghép tên của con ban đầu lại 1 số lần và con có sau sẽ có tên dài hơn con có trước. Vì muốn tri ân những chú tuần lộc đã theo mình những năm tháng tươi đẹp. Mật khẩu chính là tên của con tuần lộc đầu tiên vì nó là con có nhiều kỉ niệm với ông già Noel nhất. Nhưng những chú tuần lộc giờ đây đã yên giấc bên lò sưởi. May mắn vẫn còn 1 số con còn thức và Gấu đã hỏi được tên của một con tuần lộc. Để có được mật khẩu Gấu phải suy luận từ cái tên Gấu có được để ra được tên của con tuần lộc đầu tiên. Được biết Gấu có thể suy luận ra được nhiều cái tên hợp lí nhưng ông già Noel đã già nên con tuần lộc đầu tiên đã được đặt cái tên ngắn nhất. #### Input - Nhập vào xâu **${S}$** (${|S| \leq 10^3}$) chỉ gồm những chữ cái in thường là cái tên mà Gấu hỏi được. #### Output - Xuất ra 1 xâu duy nhất là cái tên đã được đặt cho chú tuần lộc đầu tiên mà Gấu suy luận được. #### Sample | Input | Output | Explanation | |:----------------:|:------:|:------------------------------:| | aaaaaaaa | a | Xâu "a" được ghép lại 8 lần để được xâu "aaaaaaaa" |noelnoel|noel| Xâu "noel" được ghép lại 2 để được xâu "noelnoel" ## LẤY QUÀ (HSG9) (Thanh) Sau khi mở được kho quà, Gấu thấy 1 bảng $N \times M$ gồm 1 số món quà trên đó. Tuy nhiên, là một chú Gấu thư giãn, Gấu chỉ lấy quà trong một ô hình vuông có kích thước do ông già Noel quyết định. Khi biết được yêu cầu của Gấu, ông già Noel đã chế tạo một cái khung có kích thước $K \times K$ và ông yêu cầu Gấu đặt khung lên bảng sao cho khung nằm hoàn toàn trong bảng và Gấu sẽ nhận được nhữn phần quà nằm hoàn toàn trong khung. Giúp Gấu tìm số món quà lớn nhất mà Gấu có thể lấy được. #### Constraint $3\le K \leq N, M \leq 10^3$ $a_{i, j} \in \{*, .\}$ #### Input - Dòng đầu tiên gồm 3 số nguyên **${N, M , K}$** ($3\le K \leq N, M \leq 10^3$) - **${N}$** dòng tiếp theo, mỗi dòng gồm **${M}$** kì miêu tả các ô của bảng. Kí tự `*` nghĩa là ô có quà còn kí tự `.` nghĩa là ô trống. #### Output - Xuất ra 1 số nguyên duy nhất là số món quà lớn nhất mà Gấu có thể nhận. #### Scoring * Subtask 1 ($50$%): $3\le N, M\le 100$ * Subtask 2 ($50$%): Không có giới hạn gì thêm #### Sample | Input | Output | Explanation | |:-----------------------------------------------------------------------------------------:|:------:|:------------------------------------------------------------------------------------:| | 7 6 4 $......$ $.*.*.*$ $......$ $.*.*..$ $..*...$ $..*...$ $*....*$ | 2 | $......$ $.*.*.*$ $+--+..$ $\|*.\|..$ $\|.*\|..$ $+--+..$ $*....*$ |

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.