2025 THT bảng B - Buổi 15 - OLP MT&TN 2025

Theo lịch của người Ethiopia, một năm có 13 tháng: trong đó tháng 1 đến tháng 12 có 30 ngày, riêng tháng 13 có 5 ngày. Lưu ý rằng, theo lịch này, không có khái niệm năm nhuận.

Ta định nghĩa ngày dd/mm/yyyy là ngày nguyên tố khi và chỉ khi cả ngày \((dd)\) và tháng \((mm)\) đều là các số nguyên tố, chẳng hạn như ngày 13/7/2008. Lưu ý rằng, giá trị năm \((yyyy)\) không cần là số nguyên tố.

Nhắc lại, số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó.

Yêu cầu: Cho một ngày \(X\) theo định dạng dd/mm/yyyy, các bạn hãy xác định "ngày nguyên tố" gần nhất diễn ra trước và sau ngày \(X\) là những ngày nào?

Input

• Gồm một dòng duy nhất chứa ngày \(X\) theo định dạng dd/mm/yyyy, trong đó:
  • \(dd\) là hai chữ số biểu diễn ngày \(D\)
  • \(mm\) là hai chữ số biểu diễn tháng \(M\)
  • \(yyyy\) là bốn chữ số biểu diễn năm \(Y\)
• Dữ liệu đảm bảo tồn tại ngày nguyên tố trước và sau ngày \(X\).

Output

• Dòng đầu tiên chứa ngày gần nhất trước \(X\) theo định dạng dd/mm/yyyy
• Dòng thứ hai chứa ngày gần nhất sau \(X\) theo định dạng dd/mm/yyyy

Example

07/07/0777

05/07/0777
11/07/0777

03/13/1234

02/13/1234
05/13/1234

Scoring

• Subtask 1 (25% số điểm): \(M = 13\)
• Subtask 2 (25% số điểm): \(D \in \{29, 30\}\) và \(M \geq 3\)
• Subtask 3 (25% số điểm): \(M \in \{1, 2\}\)
• Subtask 4 (25% số điểm): Không có ràng buộc nào thêm

Hiếu mới lắp ráp một robot có thể di chuyển trên trục số.
Robot của Hiếu thực hiện các thao tác di chuyển dựa trên một dãy lệnh \(S=s_1s_2\dots s_n\) \((s_i \in \{\texttt{L, R}\})\).

Nếu robot đang đứng ở vị trí \(x\) trên trục số và di chuyển theo lệnh \(s\) thì robot sẽ thực hiện như sau:

• Nếu \(s_i=\texttt{L}\) thì robot di chuyển sang bên trái trục số 1 đơn vị, hay là \(x \leftarrow x-1\)
• Nếu \(s_i=\texttt{R}\) thì robot di chuyển sang bên phải trục số 1 đơn vị, hay là \(x \leftarrow x+1\)

Ban đầu, robot đứng ở vị trí \(x_0\). Hiếu lập trình robot lần lượt thực hiện việc di chuyển trong \(k\) lượt dựa theo dãy lệnh \(s\):

• Lượt đầu tiên thực hiện lệnh \(1\)
• Nếu lượt trước đó thực hiện lệnh thứ \(i\), thì lượt tiếp theo thực hiện lệnh thứ \((i\ \text{mod}\ n) + 1\)

Để làm được việc này, robot có một ô nhớ chứa chỉ số của lệnh vừa thực hiện trước đó. Nếu sau khi thực hiện một lệnh \(s_i\), ô nhớ này cần chứa giá trị \(i\).

Tuy nhiên, do sự không cẩn thận của mình, Hiếu lại có một lỗi bộ nhớ. Nếu sau khi thực hiện một lệnh \(s_i\) mà robot trở về vị trí \(0\) thì ô nhớ chứa thứ tự lệnh trước đó thực hiện bị gán lại về giá trị \(0\) thay vì chứa giá trị \(i\) (lệnh tiếp theo sẽ là lệnh thứ \(1\)).

Tuy có lỗi bộ nhớ, robot vẫn thực hiện \(k\) lượt. Bạn hãy trả lời hai câu hỏi sau:

1. Robot đến điểm \(0\) tổng cộng bao nhiêu lần?
2. Sau \(k\) lượt, robot đang đứng tại điểm nào?

Input

• Dòng đầu tiên chứa số \(t\) (\(1 \leq t \leq 10\)) -- là số lượng test
• Tiếp theo là \(t\) test, mỗi test được ghi trên 2 dòng theo định dạng:
  • Dòng thứ nhất chứa ba số nguyên \(n, x_0, k\) \((1 \leq n \leq 10^5; 1 \leq |x_0| \leq 10^{18}; 1 \leq k \leq 10^{18})\)
  • Dòng thứ hai gồm duy nhất một xâu \(S\). Dữ liệu đảm bảo độ dài xâu \(S\) là \(n\)

Output

• In ra \(t\) dòng ứng với \(t\) test, mỗi dòng chứa hai số lần lượt là:
  • Số lần mà robot đến tọa độ \(0\)
  • Tọa độ mà robot đang đứng sau \(k\) lượt

Scoring

• Subtask \(1\) (\(35\%\) số điểm): \(k \leq 10^6\)
• Subtask \(2\) (\(20\%\) số điểm): \(s_i = s_1, \forall i\)
• Subtask \(3\) (\(15\%\) số điểm): \(|x| \leq n\)
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc nào thêm

Example

6
3 2 6
LLR
2 -1 8
RL
4 -2 5
LRRR
5 3 7
LRRLL
1 1 1
L
3 -1 4846549234412827
RLR

1 -2
4 1
1 -1
0 2
1 0
2423274617206414 0

Tại vùng đất Miền Trung Tây Nguyên, để mô phỏng sự sống, người ta sử dụng xâu nhị phân \(S\) độ dài \(n\) để mã hóa một dãy \(n\) tế bào. Các tế bào được đánh số từ \(1\) đến \(n\), tế bào thứ \(i\) được mã hóa bởi kí tự thứ \(i\) của xâu \(S\), kí hiệu là \(S_i\). Trong mọi thời điểm, \(S_i\) nhận một trong hai giá trị là \(0\) hoặc \(1\).

Dãy tế bào này sẽ biến đổi theo thời gian. Ở mỗi lần biến đổi, tất cả \(n\) tế bào sẽ thay đổi đồng thời dựa vào trạng thái của tế bào này, tế bào liền trước và tế bào liền sau tại thời điểm trước đó. Cụ thể, tế bào thứ \(i\) biến đổi như sau:

• Gọi \(L\) là trạng thái của tế bào thứ \(i-1\) trước khi biến đổi (coi \(L=0\) nếu \(i=1\))
• Gọi \(M\) là trạng thái của tế bào thứ \(i\) trước khi biến đổi
• Gọi \(R\) là trạng thái của tế bào thứ \(i+1\) trước khi biến đổi (coi \(R=0\) nếu \(i=n\))
• Tế bào thứ \(i\) sẽ biến đổi dựa trên bộ ba \(LMR\) theo quy tắc:
  • Nếu bộ ba là 111 hoặc 001, đảo ngược giá trị của \(S_i\) (tức \(S_i \leftarrow 1-S_i\))
  • Nếu bộ ba là 010 hoặc 110, \(S_i\) không thay đổi
  • Nếu bộ ba là 101 hoặc 011, \(S_i\) trở thành \(1\)
  • Khác tất cả các trường hợp trên, \(S_i\) trở thành \(0\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) \((2 \leq n \leq 20, k \leq 10^{18})\)
• Dòng thứ hai chứa xâu ký tự \(S\)

Output

Gồm một dòng duy nhất chứa xâu ký tự \(S\) sau \(k\) lần biến đổi.

Example

3 3
001

101

6 3
101100

101100

Scoring

• Subtask \(1\) \((10\%\) số điểm): \(q \leq 10\,000\)
• Subtask \(2\) \((15\%\) số điểm): Không có truy vấn ? u nào nằm trước các truy vấn loại khác
• Subtask \(3\) \((20\%\) số điểm): Không tồn tại truy vấn C u
• Subtask \(4\) \((25\%\) số điểm): Với mọi truy vấn A u, nếu rừng đang có \(n\) đỉnh, dữ liệu đảm bảo \(u = n\)
• Subtask \(5\) \((30\%\) số điểm): Không có ràng buộc nào thêm

Có \(N\) điểm trong không gian hai chiều, điểm thứ \(i\) có tọa độ là \((x_i, y_i)\). Có \(M\) loại nguyên tử phóng xạ được đánh số từ \(1\) đến \(M\).

Các nhà khoa học muốn đặt các nguyên tử vào \(N\) điểm, mỗi điểm một loại nguyên tử phóng xạ sao cho độ ổn định là lớn nhất. Độ ổn định của một cách đặt được thể hiện bằng khoảng cách Euclid nhỏ nhất giữa hai nguyên tử phóng xạ cùng loại.

Nhắc lại: khoảng cách Euclid giữa hai điểm \((x_1, y_1)\) và \((x_2, y_2)\) là:

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) \((N \leq 1000, M \leq 5)\)
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\) \((|x_i|, |y_i| \leq 10^6)\) thể hiện tọa độ của điểm thứ \(i\)

Output

• Ghi ra trên một dòng \(N\) số nguyên dương, số thứ \(i\) thể hiện loại của nguyên tử được đặt tại điểm \(i\)

Example

5 3
1 0
2 0
3 0
4 0
5 0

1 2 3 1 2

4 2
0 5
5 0
5 5
0 0

1 1 2 2

Scoring

• Subtask 1 (25% số điểm): \(N \leq 10\)
• Subtask 2 (25% số điểm): \(M = 2\)
• Subtask 3 (25% số điểm): \(\forall 1 \leq i \leq n, y_i = 0\)
• Subtask 4 (25% số điểm): không có ràng buộc nào thêm