Tin học trẻ C - Tỉnh Bắc Giang 2023

Trường THPT Chuyên Lê Quý Đôn đang tổ chức một cuộc thi giải mã thu hút rất nhiều sự quan tâm của các bạn học sinh, đặc biệt là các bạn có đam mê với lập trình. Đề bài của vòng đầu tiên được ban tổ chức đưa ra như sau:

Ban đầu, hệ thống mã hoá sinh ra một xâu gồm \(3 \times k\) ký tự, đầu tiên là \(k\) ký tự L, tiếp theo là \(k\) ký tự Q và cuối cùng là \(k\) ký tự D. Sau đó, hệ thống sẽ thêm một số ký tự L, Q hoặc D vào những vị trí bất kỳ trong xâu cho đến khi xâu có độ dài \(n\). Sau đó, hệ thống sẽ cho người dùng biết \(n\), \(k\) và xâu sau khi đã biến đổi. Người giải mã cần chọn ra một xâu con gồm các ký tự liên tiếp và đếm số lượng ký tự cần xoá ít nhất để thu được xâu ban đầu mà hệ thống sinh ra. Nếu kết quả của người chơi trùng khớp với kết quả của hệ thống thì người đó sẽ được xem là hoàn thành vòng thi và nhận được tấm vé đến vòng tiếp theo.

Là một người đã có nhiều kinh nghiệm với lập trình, liệu bạn có thể giành được tấm vé này chứ?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \(\left(3 \leq n \leq 10^{7}, 1 \leq k \leq \left \lfloor \dfrac{n}{3} \right \rfloor \right)\).
• Dòng tiếp theo chứa một xâu độ dài \(n\) chỉ gồm các ký tự L, Q và D.

Output

• Một dòng duy nhất chứa một số nguyên là kết quả của bạn. Trường hợp đặc biệt: nếu không thể chọn ra xâu con nào để thu được xâu ban đầu mà hệ thống sinh ra, bạn cần in ra -1

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 21\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 3 \times 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 2 \times 10^{5}\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 2
LLDLQDQDDL

2

Hàm băm (hash function) là một hàm số giúp chuyển dữ liệu bất kì thành một mã băm (hash code), thường có dạng một xâu có độ dài cố định. Hàm băm có ứng dụng rộng rãi trong nhiều lĩnh vực, trong đó có mật mã học (cryptography), và thậm chí là ứng dụng trong blockchain. Người ta có thể thiết kế ra một hàm băm \(f\) bất kì có tính chất sau:

• Đụng độ (hash collision) có tỉ lệ rất thấp, hầu như không xảy ra. Tức \(x \neq y \Rightarrow f(x) \neq f(y)\)
• Giả sử ta biết \(y = f(x)\), việc tìm ra \(x\) là rất khó (tốn độ phức tạp thời gian quá lớn)
• Khi đó, hàm băm có tính chất "một chiều" và có thể áp dụng được vào trong mã hóa, mật mã học.

Sau khi nghe hội thảo về những kiến thức trên, Nghĩa cảm thấy rất thú vị và muốn áp dụng ngay. Cậu muốn mã hóa hai dãy số nguyên dương \(a,b\) có kích thước lần lượt là \(n, m\) phần tử. Cậu định nghĩa:

• \(A = a_{1} \times a_{2} \times \dots \times a_{n}\) (tích các số trong dãy \(a\))
• \(B = b_{1} \times b_{2} \times \dots \times b_{m}\) (tích các số trong dãy \(b\))
• \(f(a,b) = \gcd(A, B) \mod (10^{9} + 7)\), tức là ước chung lớn nhất của tích hai dãy, chia lấy dư cho \((10^{9} + 7)\) vì số rất lớn.

Nghĩa nhận thấy hàm \(f\) trên có tính chất "một chiều" như đã nêu trên, nhưng do cậu không giỏi lắm về tin học nên chưa thiết kế được thuật toán hiệu quả để tính \(f\). Nghĩa cần được các bạn thí sinh THT trợ giúp!

Yêu cầu: Cho hai dãy \(a,b\), hãy tính và in ra \(f(a, b)\)

Input

• Dòng thứ nhất chứa hai số nguyên \(n, m\) \((1 \leq n, m \leq 5 \times 10^{5})\) - lần lượt là kích thước hai dãy.
• Dòng thứ hai chứa \(n\) số nguyên \(a_{i}\) \((1 \leq a_{i} \leq 10^{7})\).
• Dòng thứ ba chứa \(m\) số nguyên \(b_{i}\) \((1 \leq b_{i} \leq 10^{7})\).

Output

• Gồm một dòng duy nhất chứa \(f(a, b)\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, m \leq 14\) và \(a_{i}, b_{i} \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(n = 1\)
• Subtask \(3\) (\(20\%\) số điểm): \(n, m, a_{i}, b_{i} \leq 10^{5}\)
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm

Example

4 4
5 3 2 18
6 7 10 3

180

Thạch đang ở một trò chơi đặc biệt trong khu vui chơi. Đó là một mê cung có dạng bảng hình chữ nhật, có kích thước \(m \times n\) (\(m\) dòng, \(n\) cột). Trong này có \(k\) ô chứa vật cản. Ô nằm ở hàng \(i\), cột \(j\) được kí hiệu là ô \((i, j)\).

Vào thời điểm ban đầu, Thạch đứng ở ô \((1, 1)\). Tại mỗi lượt, cậu chỉ được đi xuống dưới hoặc sang phải. Dĩ nhiên, Thạch không được phép đi vào ô có vật cản. Mục tiêu của trò chơi là đi tới ô đích ở \((m, n)\).

Tuy nhiên, điểm đặc biệt ở mê cung này là: Mọi vật cản đều di chuyển theo mỗi bước chân của Thạch (có lẽ là do sân này có gắn cảm biến và nhiều cỗ máy đặc biệt chăng?). Quy luật như sau:

• Sau khi đi xuống dưới một hàng thì mọi vật cản dịch lên trên \(1\) đơn vị, riêng những vật cản ở dòng \(1\) bây giờ sẽ được đẩy "lên" dòng cuối \(m\)
• Nếu đi qua phải thì mọi vật cản dịch sang trái \(1\) đơn vị, riêng những vật nằm trên cột \(1\) sẽ được đẩy sang cột cuối \(n\).
• Nói cách khác, các vật cản dịch chuyển theo vòng tròn.
• Sau một bước đi bất kì của Thạch, nếu có vật cản nào đó dịch tới chỗ cậu đang đứng thì Thạch sẽ bị loại khỏi mê cung và coi như thua cuộc (kể cả sau khi bước tới ô đích).

Việc giành chiến thắng có vẻ quá đơn giản với một gamer như Thạch. Vì thế điều cậu ấy đang quan tâm hơn hết là: Đếm số cách khác nhau để cậu có thể đi tới được đích đến tại vị trí \((m, n)\), chia lấy dư cho \(2004010501\).

Bạn hãy lập trình giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa ba số \(m, n, k\) \((0 \leq k \leq m \times n, 1 \leq m, n \leq 1000)\)
• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\). Nếu kí tự thứ \(j\) trên dòng thứ \(i\) là #, ô \((i, j)\) là ô chứa vật cản. Ngược lại, nếu là . thì ô \((i, j)\) là ô trống.
• Dữ liệu đảm bảo có đúng \(k\) ô # trong mê cung, và ô \((1, 1)\) lúc đầu không chứa vật cản.

Output

• In ra một dòng duy nhất là kết quả bài toán

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m + n \leq 20\)
• Subtask \(2\) (\(25\%\) số điểm): \(k = 0\)
• Subtask \(3\) (\(15\%\) số điểm): \(n = 2\)
• Subtask \(4\) (\(35\%\) số điểm): không có ràng buộc gì thêm

Example

2 3 1
...
..#

2

Bạn Tuyết, như cái tên của bạn, rất thích vẻ đẹp của các bông tuyết. Bạn có thể dành hàng giờ chỉ để ngắm chúng.

Khác với thế giới bình thường, nơi mà các bông tuyết đa phần có 6 nhánh với cấu trúc đối xứng và phức tạp; bông tuyết ở thế giới của bạn Tuyết có hình dạng là một cây (đồ thị vô hướng không có chu trình) gồm có \(n\) đỉnh, được đánh số từ \(1\) tới \(n\). Đỉnh của cây được đánh số \(1\).

Tuyết muốn chọn trọng tâm của một nhánh con (hay còn gọi là cây con) của bông tuyết để cân bằng. Tuy nhiên, bạn ấy chưa biết nên chọn nhánh con nào. Bạn được biết \(q\) lựa chọn nhánh con sơ bộ của Tuyết, hãy tìm một trọng tâm của từng nhánh con đó cho Tuyết nhé!

Ta gọi đỉnh \(u\) là tổ tiên của đỉnh \(v\), hay đỉnh \(v\) là hậu duệ của đỉnh \(u\), nếu trên đường đi trực tiếp từ đỉnh \(v\) đến gốc \(1\) có chứa đỉnh \(u\). Đỉnh \(u\) được gọi là cha của đỉnh \(v\) nếu \(u\) là tổ tiên của \(v\) và \(u\) kề \(v\).
Nhánh con của một đỉnh \(u\) bao gồm chính đỉnh \(u\) và các hậu duệ của đỉnh \(u\). Nhánh con cũng có hình dạng cây.

Trọng tâm của một cây (hoặc một nhánh con) là đỉnh mà nếu như xóa đỉnh đó đi khỏi cây, thì trong số các cây bị tách rời, cây lớn nhất có số đỉnh nhiều bằng nhiều nhất một nửa số đỉnh của cây (hoặc nhánh con) ban đầu.

Input

• Dòng đầu tiên chứa hai số \(n\) và \(q\) \((2 \leq n \leq 5 \times 10^{5}, 1 \leq q \leq 5 \times 10^{5})\) - số đỉnh của bông tuyết, và số nhánh con trong danh sách sơ bộ của Tuyết.
• Dòng thứ hai chứa \(n - 1\) số \(p_{2}, p_{3}, \ldots, p_{n}\) \((1 \leq p_{i} \leq n\), với \(p_i\) cho biết chỉ số đỉnh cha của đỉnh \(i\).
• \(q\) dòng tiếp theo, mỗi dòng gồm một số duy nhất \(v_{i}\) \((1 \leq v_{i} \leq n)\), cho biết đỉnh đại diện cho nhánh con cần tìm trọng tâm.

Output

Với mỗi truy vấn, in ra một dòng chỉ số của đỉnh trọng tâm ứng với nhánh con của đỉnh được hỏi. Nếu có nhiều đỉnh thỏa mãn, in ra bất kỳ đáp án hợp lệ nào. Có thể đảm bảo rằng, mỗi nhánh con đều có ít nhất một đỉnh trọng tâm.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 500\)
• Subtask \(2\) (\(30\%\) số điểm): \(n, q \leq 5000\)
• Subtask \(3\) (\(20\%\) số điểm): \(n, q \leq 10^{5}\)
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm

Example

10 5 
10 10 1 4 3 5 2 3 5
4
6
10
1
5

10
6
3
10
10