{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Bài toán","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eCho một chuỗi \u003cvar\u003e\\(s\\)\u003c/var\u003e có độ dài \u003cvar\u003e\\(N\\)\u003c/var\u003e.\nĐặt \u003cvar\u003e\\(s_i\\)\u003c/var\u003e là ký tự thứ \u003cvar\u003e\\(i\\)\u003c/var\u003e của \u003cvar\u003e\\(s\\)\u003c/var\u003e.\u003c/p\u003e\n\u003cp\u003eSnuke sẽ biến đổi \u003cvar\u003e\\(s\\)\u003c/var\u003e bằng quy trình sau.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eChọn một chuỗi con có \u003cstrong\u003eđộ dài chẵn\u003c/strong\u003e (không nhất thiết phải liên tục) \u003cvar\u003e\\(x\u003d(x_1, x_2, \\ldots, x_{2k})\\)\u003c/var\u003e của \u003cvar\u003e\\((1,2, \\ldots, N)\\)\u003c/var\u003e (\u003cvar\u003e\\(k\\)\u003c/var\u003e có thể là \u003cvar\u003e\\(0\\)\u003c/var\u003e).\u003c/li\u003e\n\u003cli\u003eĐổi chỗ \u003cvar\u003e\\(s_{x_1}\\)\u003c/var\u003e và \u003cvar\u003e\\(s_{x_{2k}}\\)\u003c/var\u003e.\u003c/li\u003e\n\u003cli\u003eĐổi chỗ \u003cvar\u003e\\(s_{x_2}\\)\u003c/var\u003e và \u003cvar\u003e\\(s_{x_{2k-1}}\\)\u003c/var\u003e.\u003c/li\u003e\n\u003cli\u003eĐổi chỗ \u003cvar\u003e\\(s_{x_3}\\)\u003c/var\u003e và \u003cvar\u003e\\(s_{x_{2k-2}}\\)\u003c/var\u003e.\u003c/li\u003e\n\u003cli\u003e\u003cvar\u003e\\(\\vdots\\)\u003c/var\u003e\u003c/li\u003e\n\u003cli\u003eĐổi chỗ \u003cvar\u003e\\(s_{x_{k}}\\)\u003c/var\u003e và \u003cvar\u003e\\(s_{x_{k+1}}\\)\u003c/var\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eTrong số các chuỗi mà \u003cvar\u003e\\(s\\)\u003c/var\u003e có thể trở thành sau quy trình, tìm chuỗi nhỏ nhất theo thứ tự từ điển.\u003c/p\u003e\n\u003cdetails\u003e\n\u003csummary\u003eThứ tự từ điển là gì?\u003c/summary\u003e\n\u003cp\u003e\nĐơn giản, thứ tự từ điển là thứ tự mà các từ được liệt kê trong từ điển. Với một định nghĩa chính thức hơn, đây là thuật toán để xác định thứ tự từ điển giữa các chuỗi khác nhau \u003cvar\u003e\\(S\\)\u003c/var\u003e và \u003cvar\u003e\\(T\\)\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003cp\u003eDưới đây, đặt \u003cvar\u003e\\(S_i\\)\u003c/var\u003e là ký tự thứ \u003cvar\u003e\\(i\\)\u003c/var\u003e của \u003cvar\u003e\\(S\\)\u003c/var\u003e. Ngoài ra, nếu \u003cvar\u003e\\(S\\)\u003c/var\u003e nhỏ hơn \u003cvar\u003e\\(T\\)\u003c/var\u003e theo thứ tự từ điển, chúng ta sẽ ký hiệu điều đó là \u003cvar\u003e\\(S \\lt T\\)\u003c/var\u003e; nếu \u003cvar\u003e\\(S\\)\u003c/var\u003e lớn hơn \u003cvar\u003e\\(T\\)\u003c/var\u003e, chúng ta sẽ ký hiệu điều đó là \u003cvar\u003e\\(S \\gt T\\)\u003c/var\u003e.\u003c/p\u003e\n\n\u003col\u003e\n \u003cli\u003e Đặt \u003cvar\u003e\\(L\\)\u003c/var\u003e là độ dài nhỏ hơn giữa \u003cvar\u003e\\(S\\)\u003c/var\u003e và \u003cvar\u003e\\(T\\)\u003c/var\u003e. Đối với mỗi \u003cvar\u003e\\(i\u003d1,2,\\dots,L\\)\u003c/var\u003e, chúng ta kiểm tra xem \u003cvar\u003e\\(S_i\\)\u003c/var\u003e và \u003cvar\u003e\\(T_i\\)\u003c/var\u003e có giống nhau không. \u003c/li\u003e\n \u003cli\u003e Nếu có một \u003cvar\u003e\\(i\\)\u003c/var\u003e sao cho \u003cvar\u003e\\(S_i \\neq T_i\\)\u003c/var\u003e, đặt \u003cvar\u003e\\(j\\)\u003c/var\u003e là \u003cvar\u003e\\(i\\)\u003c/var\u003e nhỏ nhất như vậy. Sau đó, chúng ta so sánh \u003cvar\u003e\\(S_j\\)\u003c/var\u003e và \u003cvar\u003e\\(T_j\\)\u003c/var\u003e. Nếu \u003cvar\u003e\\(S_j\\)\u003c/var\u003e đứng trước \u003cvar\u003e\\(T_j\\)\u003c/var\u003e trong thứ tự chữ cái, chúng ta xác định rằng \u003cvar\u003e\\(S \\lt T\\)\u003c/var\u003e và dừng lại; nếu \u003cvar\u003e\\(S_j\\)\u003c/var\u003e đứng sau \u003cvar\u003e\\(T_j\\)\u003c/var\u003e, chúng ta xác định rằng \u003cvar\u003e\\(S \\gt T\\)\u003c/var\u003e và dừng lại.\n \u003c/li\u003e\n \u003cli\u003e Nếu không có \u003cvar\u003e\\(i\\)\u003c/var\u003e sao cho \u003cvar\u003e\\(S_i \\neq T_i\\)\u003c/var\u003e, chúng ta so sánh độ dài của \u003cvar\u003e\\(S\\)\u003c/var\u003e và \u003cvar\u003e\\(T\\)\u003c/var\u003e. Nếu \u003cvar\u003e\\(S\\)\u003c/var\u003e ngắn hơn \u003cvar\u003e\\(T\\)\u003c/var\u003e, chúng ta xác định rằng \u003cvar\u003e\\(S \\lt T\\)\u003c/var\u003e và dừng lại; nếu \u003cvar\u003e\\(S\\)\u003c/var\u003e dài hơn \u003cvar\u003e\\(T\\)\u003c/var\u003e, chúng ta xác định rằng \u003cvar\u003e\\(S \\gt T\\)\u003c/var\u003e và dừng lại. \u003c/li\u003e\n\u003c/ol\u003e\n\n\u003c/details\u003e\n\n\u003c/section\u003e"}},{"title":"Ràng buộc","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq N \\leq 2 \\times 10^5\\)\u003c/var\u003e\u003c/li\u003e\n\u003cli\u003e\u003cvar\u003e\\(s\\)\u003c/var\u003e là một chuỗi có độ dài \u003cvar\u003e\\(N\\)\u003c/var\u003e bao gồm các chữ cái tiếng Anh thường.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eDữ liệu nhập theo định dạng sau từ đầu vào chuẩn:\u003c/p\u003e\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(s\\)\u003c/var\u003e\r\n\u003c/pre\u003e\n\n\u003c/section\u003e"}},{"title":"Xuất","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eIn ra chuỗi \u003cvar\u003e\\(s\\)\u003c/var\u003e nhỏ nhất theo thứ tự từ điển sau quy trình của Snuke.\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"Ví dụ 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\ndcab\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eacdb\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\n\u003csection\u003e\n\u003cul\u003e\n\u003cli\u003eKhi \u003cvar\u003e\\(x\u003d(1,3)\\)\u003c/var\u003e, quy trình chỉ đổi chỗ \u003cvar\u003e\\(s_{1}\\)\u003c/var\u003e và \u003cvar\u003e\\(s_{3}\\)\u003c/var\u003e.\u003c/li\u003e\n\u003cli\u003eChuỗi \u003cvar\u003e\\(s\\)\u003c/var\u003e sau quy trình là \u003ccode\u003eacdb\u003c/code\u003e, kết quả nhỏ nhất theo thứ tự từ điển.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Ví dụ 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\nab\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eab\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\n\u003csection\u003e\n\u003cul\u003e\n\u003cli\u003eKhi \u003cvar\u003e\\(x\u003d()\\)\u003c/var\u003e, chuỗi \u003cvar\u003e\\(s\\)\u003c/var\u003e sau quy trình là \u003ccode\u003eab\u003c/code\u003e, kết quả nhỏ nhất theo thứ tự từ điển.\u003c/li\u003e\n\u003cli\u003eLưu ý rằng \u003cvar\u003e\\(x\\)\u003c/var\u003e có thể có độ dài là \u003cvar\u003e\\(0\\)\u003c/var\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Ví dụ 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e16\r\ncabaaabbbabcbaba\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eaaaaaaabbbbcbbbc\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\n\u003csection\u003e\n\u003c/section\u003e"}},{"title":"Ví dụ 4","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e17\r\nsnwfpfwipeusiwkzo\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eeffwpnwipsusiwkzo\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\n\u003csection\u003e\n\u003c/section\u003e"}}]}