Mật mã kho báu (TS10 QNi 2023)

Điểm: 1400 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: pass.inp

Output: pass.out

Tác giả:

Sunlight

Dạng bài

Gần đây nhóm của An đã khám phá ra một kho báu trên một hòn đảo hoang. Trên cánh cửa lối vào, An thấy có ghi một xâu nhị phân $S$ (xâu chỉ chứa các chữ số $0$ và $1$ ). Ký hiệu $|S|$ là độ dài của xâu $S$ , tức là số ký tự của xâu $S$ . Các ký tự của xâu $S$ được đánh chỉ số từ $1$ đến $|S|$

Sau khi nghiên cứu các tài liệu và bản khảo cổ, An biết được mật mã để mở cửa kho báu này là một bộ 4 số $l_1,r_1,l_2,r_2$ , trong đó $[l_1,r_1]$ và $[l_2,r_2]$ là 2 đoạn chữ số khác nhau của xâu $S$ . Hai đoạn này phải có cùng độ dài và dài nhất có thể, hơn nữa tổng các chữ số của 2 đoạn phải bằng nhau. Cụ thể, mật mã của kho báu là 4 số $l_1,r_1,l_2,r_2$ sao cho:

$1\le l_1\le r_1\le |S|$ và $1\le l_2\le r_2\le |S|$
$[l_1,r_1]$ và $[l_2,r_2]$ là 2 đoạn khác nhau của $S$ , tức là $l_1\ne l_2$ hoặc $r_1\ne r_2$
$r_1-l_1=r_2-l_2$
$S_{l_1}+S_{l_1+1}+\dots+S_{r_1}=S_{l_2}+S_{l_2+1}+\dots+S_{r_2}$
$r_1-l_1$ lớn nhất

Theo như An tìm hiểu được từ bản thảo, nếu có nhiều bộ 4 số thỏa mãn thì bất kỳ bộ nào trong chúng đều có thể làm mật mã. Bây giờ An cần tìm mật mã cho kho báu, nhưng anh ấy không thể tìm được nếu không có sự giúp đỡ của bạn. Bạn hãy giúp An tìm mật mã của kho báu.

Input, Output và Subtasks

Input: (pass.inp)

Dòng đầu tiên chứa số nguyên $t$ ( $1\le t\le 5$ ) là số test. Mỗi dòng trong $t$ dòng tiếp theo chứa một xâu nhị phân $S$ (xâu $S$ chỉ bao gồm các chữ số $0,1$ và $1\le |S|\le 10^6$ )

Output: (pass.out)

Với mỗi test, in kết quả trên 1 dòng: nếu không tồn tại một bộ 4 số như vậy thì in ra $-1$ , ngược lại in ra 4 số $l_1,r_1,l_2,r_2$ là mật mã cần tìm. Nếu có nhiều câu trả lời thì in ra một câu trả lời bất kỳ trong số chúng

Subtasks

Subtask 1 $(25\%)$ : Tổng độ dài tất cả xâu $S$ không vượt quá $50$
Subtask 2 $(25\%)$ : Tổng độ dài tất cả xâu $S$ không vượt quá $500$
Subtask 3 $(25\%)$ : Tổng độ dài tất cả xâu $S$ không vượt quá $10^4$
Subtask 4 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (pass.inp)

Output (pass.out)

1 5 2 6
2 5 3 6
-1

Note

Trong test đầu tiên, đoạn $[1,5]$ ứng với xâu con 11111 và đoạn $[2,6]$ ứng với xâu con 11111 là 2 đoạn khác nhau có cùng độ dài và có cùng tổng các chữ số bằng $5$ . Không tồn tại 2 đoạn nào có độ dài lớn hơn thỏa mãn tất cả các điều kiện
Trong test thứ hai, đoạn $[2,5]$ ứng với xâu con 1010 và đoạn $[3,6]$ ứng với xâu con 0101 là 2 đoạn khác nhau có cùng độ dài và có cùng tổng các chữ số bằng $2$ . Không tồn tại 2 đoạn nào có độ dài lớn hơn thỏa mãn tất cả các điều kiện
Trong test thứ ba, không tồn tại 2 đoạn nào thỏa mãn tất cả điều kiện

Bình luận

Không có bình luận nào.