Contest 03

Có một nhóm bạn gồm \(n\) người bạn, được đánh số từ \(1\) đến \(n\) xếp thành một vòng tròn theo nguyên tắc: bên phải bạn số \(1\) là bạn số \(2\), bên phải bạn số \(2\) là bạn số \(3\), \(\ldots\) bên phải bạn số \(n - 1\) là bạn số \(n\) và bên phải bạn số \(n\) là bạn số \(1\). Nhóm bạn này chơi trò đếm số theo chiều kim đồng hồ, bắt đầu đếm từ bạn có số thứ tự là \(1\). Nghĩa là bạn số \(1\) sẽ đếm số \(1\), bạn số \(2\) sẽ đếm số \(2\), \(\ldots\) bạn số \(n\) sẽ đếm số \(n\), rồi quay lại bạn số \(1\) sẽ đếm số \(n + 1\), bạn số \(2\) sẽ đếm số \(n + 2\), \(\ldots\)

Tuy nhiên, vì thấy trò chơi quá đơn giản nên thầy giáo đã quyết định đố các bạn bằng cách nâng cấp độ khó cho trò chơi. Giờ đây, thay vì bắt đầu từ bạn số \(1\) đếm, bạn thứ \(k\) bất kì được chỉ định bất kì sẽ bắt đầu đếm đầu tiên. Hỏi số thứ \(m\) sẽ được đếm bởi bạn số mấy?

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((n \leq 10^{15})\).
• Dòng thứ hai chứa số nguyên dương \(m\) \((m \leq 10^{15})\).
• Dòng thứ ba chứa số nguyên dương \(k\) \((k \leq n)\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số thứ tự của bạn đếm số thứ \(m\).

Scoring

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

Example

4
5
1

1

Bạn được cho một mảng \(a\) gồm \(n\) (\(n\) chia hết cho \(3\)) phần tử. Bạn được thực hiện vô số thao tác sau: tăng hoặc giảm \(1\) phần tử bất kỳ lên hoặc xuống \(1\) đơn vị. Gọi \(c_{0}, c_{1}\) và \(c_{2}\) lần lượt là số lượng các phần tử trong mảng \(a\) khi chia lấy dư cho 3 có số dư bằng \(0, 1\) và \(2\). Một mảng được gọi là cân đối khi \(c_{0} = c_{1} = c_{2}\).

Yêu cầu: bạn hãy tìm cách cân đối mảng \(a\) ban đầu bằng cách thực hiện \(0\) hoặc nhiều thao tác và in ra số thao tác ít nhất để cân đối mảng \(a\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) \((1 \leq n \leq 5 \times 10^{5}, n \mod 3 = 0)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số thao tác ít nhất để cân đối mảng.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 3\).
• Subtask \(2\) (\(40\%\) số điểm): \(a_{i} \leq 2\).
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

6
5 3 8 9 11 34

1

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