LQDOJ Cup 2025 - Round #4

Có thể bạn chưa biết, ngoài trà sữa, GSPVH còn có một đặc sản khác đó chính là boardgame. Nếu như trà sữa được GSPVH phát cho tất cả các bạn học trên lớp, thì những bữa tiệc boardgame sẽ được tổ chức vào buổi tối. Boardgame là hình thức giải trí vui vẻ, hấp dẫn và vô cùng lành mạnh. Khi đắm chìm trong những bữa tiệc boardgame, chúng ta sẽ xích lại gần hơn với những người bạn của mình, thay thế tương tác ảo trên mạng xã hội bởi phút giây cuộc trò chuyện thực tế, và không lo bị tốn thời gian vào những trò chơi vô bổ như Genshin hay Liên Quân. Hơn thế nữa, boardgame còn làm tăng khả năng tư duy thuật toán và lý thuyết trò chơi, điều rất quan trọng với các bạn chuẩn bị thi học sinh giỏi quốc gia.

Trong chuyến đi dạy lần này, để đổi món, GSPVH đã tạo ra một trò boardgame mới để thử thách các bạn học sinh.

GSPVH vẽ trên nền nhà một lưới ô vuông gồm \(m\) hàng và \(n\) cột. Các hàng được đánh số từ \(1\) đến \(m\), các cột được đánh số từ \(1\) đến \(n\). Ô ở hàng \(i\) và cột \(j\) được ký hiệu là \((i, j)\). Trên mỗi ô của lưới, GSPVH có ghi một ký tự. GSPVH mời \(q\) bạn lần lượt tham gia trò chơi. GSPVH phát cho mỗi bạn một xâu ký tự, bạn thứ \(i\) nhận được xâu \(s_i\). Sau đó, các bạn lần lượt thực hiện phần chơi "di chuyển trên lưới". Luật chơi như sau:

• Người chơi được phép xuất phát ở một ô bất kỳ trên lưới và kết thúc ở một ô bất kỳ trên lưới.
• Tại mỗi bước, người chơi đi từ ô hiện tại sang một ô kề cạnh.
• Người chơi không được đi ra ngoài bảng.
• Người chơi không được quay lại ô mà mình vừa tới ở bước liền trước đó. Nói cách khác, nếu người chơi thực hiện hai bước di chuyển liên tiếp là từ ô \((x_1, y_1)\) sang ô \((x_2, y_2)\) và từ ô \((x_2, y_2)\) sang ô \((x_3, y_3)\); thì hai ô \((x_1, y_1)\) và \((x_3, y_3)\) phải khác nhau.
• Trong quá trình di chuyển, người chơi có thể đi qua một ô nhiều lần.
• Xét xâu ký tự \(t\) được xây dựng như sau:
  • Ban đầu xâu \(t\) chỉ chứa một ký tự là ký tự được ghi ở ô người chơi chọn làm ô xuất phát.
  • Sau mỗi bước đi, người chơi thêm vào cuối xâu \(t\) một ký tự là ký tự được ghi ở ô người đó vừa đi tới.
• Kết thúc quá trình di chuyển, xâu \(t\) nói trên phải là một xâu bội của xâu mà người chơi nhận được từ GSPVH.

Xâu ký tự \(\alpha\) được gọi là xâu bội của xâu ký tự \(\beta\) khi và chỉ khi tồn tại số nguyên dương \(\kappa\) sao cho \(\alpha\) bằng \(\kappa\) xâu \(\beta\) ghép lại với nhau. Ví dụ, gspvh, gspvhgspvh, gspvhgspvhgspvh đều là các xâu bội của gspvh, nhưng pvhgs hay pvhgspvh thì không.

GSPVH tuyên bố, nếu phần chơi của các bạn càng kéo dài (tức độ dài xâu \(t\) theo mô tả ở trên càng lớn) thì GSPVH càng tặng nhiều trà sữa. Vì vậy, các bạn đều muốn số bước di chuyển mình thực hiện được là lớn nhất. Tuy nhiên, để tránh bị kiệt sức do nhảy quá nhiều, các bạn cũng muốn biết liệu số bước tối đa có lớn quá hay không.

Dữ liệu

Vào từ file văn bản boardgame.inp:

• Dòng đầu tiên chứa một số nguyên \(\tau\) là số bộ dữ liệu.
• Tiếp theo là các bộ dữ liệu, mỗi bộ được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa ba số nguyên dương \(m, n\) và \(q\) \((1 \leq m \cdot n \leq 2 \cdot 10^5, 1 \leq q \leq 10)\).
  • Trong \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) ký tự mô tả lưới ô vuông.
  • Dòng cuối cùng chứa \(q\) xâu ký tự \(s_1, s_2, \ldots, s_q\). Tất cả các xâu đều khác rỗng và thỏa mãn tính chất: các ký tự trong xâu đôi một phân biệt.

Gọi:

• \(\Sigma_{m \cdot n}\) là tổng giá trị \(m \cdot n\) trong tất cả các bộ dữ liệu trong một test.
• \(\Sigma_{q}\) là tổng giá trị của \(q\) trong tất cả các bộ dữ liệu trong một test.
• \(\Sigma_{s}\) là tổng độ dài các xâu \(s_1, s_2, \ldots, s_q\) trong tất cả các bộ dữ liệu trong một test.

Dữ liệu đảm bảo:

• Lưới ô vuông và các xâu \(s_1, s_2, \ldots, s_q\) chỉ chứa các chữ cái in hoa, chữ cái in thường, chữ số và các ký tự !, @, #, $, %, ^, &, *.
• \(\Sigma_{m \cdot n} \leq 10^6\)
• \(\Sigma_{s} \leq 10^6\)

Kết quả

Ghi ra file văn bản boardgame.out:
- Với mỗi bộ dữ liệu, in ra \(q\) số nguyên trên một dòng. Số thứ \(i\) là giá trị lớn nhất của độ dài xâu \(t\) (trong phần mô phỏng luật chơi) mà bạn thứ \(i\) có thể tạo ra, hoặc \(-1\) nếu tồn tại cách để người chơi này đi nhiều hơn \(2207^{1997}\) bước.

Ràng buộc

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(25\) điểm): \(m \cdot n < m + n\)
• Subtask \(2\) (\(20\) điểm): Các xâu \(s_1, s_2, \ldots, s_q\) có độ dài nhỏ hơn \(3\).
• Subtask \(3\) (\(25\) điểm): \(m \cdot n \le 8 \cdot 10^3\) và \(\Sigma_{m \cdot n} \leq 4 \cdot 10^4\).
• Subtask \(4\) (\(30\) điểm): Không có ràng buộc gì thêm.

Với mỗi test, nếu file kết quả của bạn không đúng format (chứa ký tự lạ, chứa nhiều hơn hoặc ít hơn \(\Sigma_{q}\) số nguyên,...), bạn sẽ được \(0\) điểm. Ngược lại, gọi \(\rho\) là số giá trị khớp với đáp án của giám khảo, số điểm bạn nhận được là \((\frac{\rho}{\Sigma_{q}})^{\sqrt{2.27}}\). Điểm tối đa của một test là \(1\).

Ví dụ

2

4 4 2
abca
abab
cabc
abba
abc bc

5 5 3
LQDQd
QDOLJ
LOJLO
QDIQD
LOjLO
LQDOJ DOJI LQD

6 2
-1 -1 3

Chắc hẳn các bạn đã từng nghe tới Sherlock Holmes, nhân vật thám tử hư cấu do nhà văn người Anh Conan Doyle sáng tạo nên. Sherlock Holmes đã làm say đắm biết bao tín đồ truyện trinh thám nhờ những màn phá án thần thánh với tài suy luận logic tuyệt vời cùng khả năng quan sát, diễn dịch và khoa học pháp y điêu luyện. Sherlock Homes đã được sách kỷ lục Guinness liệt kê vào danh sách nhân vật được khắc họa nhiều nhất trong văn học và điện ảnh. Danh tiếng toàn cầu của Conan Doyle gắn liền với Sherlock Homes thì ai cũng biết, nhưng nguồn gốc của tên gọi Sherlock Homes thì nhiều người chưa biết tới. Đó là bởi, nhà văn Conan Doyle có một người họ hàng xa có nghề làm khóa thông minh gia truyền. Thương hiệu khóa của người họ hàng này có tên là Sir Lock Home.

Gần đây, Sir Lock Home cho ra mắt một dòng sản phẩm khóa cửa nhà được hãng mệnh danh là "loại khóa an toàn nhất thế giới, thách thức mọi công nghệ phá khóa hiện đại nhất mọi thời đại". Đây là loại khóa số có thiết kế đặc biệt, với mật khẩu là một bảng gồm \(n\) hàng và \(m\) cột. Các hàng được đánh số từ \(1\) đến \(n\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(m\) theo thứ tự từ trái qua phải. Để nhập mật khẩu, người dùng cần điền một chữ số từ \(0\) đến \(9\) vào mỗi ô của bảng số này.

Thông thường, bạn sẽ nghĩ để mở khóa, người dùng cần nhập chính xác cả \(n \cdot m\) chữ số của bảng mật khẩu này. Nhưng hãng khóa Sir Lock Home không nghĩ như vậy. Họ cho rằng, nếu chỉ nhập và so sánh mật khẩu theo cách thông thường, khách hàng sẽ khó giữ kín mật khẩu. Chỉ cần chủ nhân vô tình để lộ bảng số mật khẩu cho người lạ nhìn thấy, mọi chốt an toàn coi như tan biến. Do đó, cơ chế bảo mật của loại khóa này được hãng Sir Lock Home thiết kế thông minh hơn, cụ thể như sau: Khi giao khóa cho khách hàng, Sir Lock Home đưa cho khách một bảng chữ số gồm \(n\) hàng và \(m\) cột, gọi là bảng cơ sở của khóa. Nếu chỉ nhập y nguyên bảng cơ sở này, khóa (có thể) sẽ không mở. Thay vào đó, người dùng sẽ phải thay đổi chữ số ở một số ô để bảng mật khẩu thỏa mãn các tính chất sau:

• Nếu ghép \(m\) chữ số của mỗi hàng thành một con số có \(m\) chữ số trong hệ thập phân (trong đó chữ số ở cột \(1\) là chữ số lớn nhất, chữ số ở cột \(m\) là chữ số hàng đơn vị, số có thể có chữ số \(0\) ở đầu); thì \(n\) con số ở \(n\) hàng tạo thành một dãy số tăng chặt. Cụ thể, số ở hàng \(1\) nhỏ hơn số ở hàng \(2\), số ở hàng \(2\) nhỏ hơn số ở hàng \(3\), \(\ldots\), số ở hàng \(n\) là số lớn nhất.
• Số ô có chữ số bị thay đổi phải nhỏ nhất có thể.
• Nếu có nhiều cách thay đổi chữ số thỏa mãn đồng thời cả hai điều kiện trên, mọi cách như vậy đều mở được khóa.

Sir Lock Home cho rằng, mặc dù mật khẩu để mở khóa không phải duy nhất, nhưng độ khó của bài toán tìm số ô tối thiểu cần thay đổi này sẽ làm nản lòng những tên đạo trích dốt thuật toán và khiến chúng từ bỏ ý đồ xâm phạm nhà bạn.

Nhưng bạn là một người đạt huy chương vàng IOI thì sao? Liệu bạn có thể tìm ra số ô tối thiểu cần thay đổi và chỉ ra một cách bất kỳ để mở khóa hay không? Hãy cùng thử tài phá loại khóa này nhé!

Dữ liệu

Vào từ file văn bản sirlockhome.inp:

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 400, 1 \leq m \leq 70, n \leq 10^m)\).
• Trong \(n\) dòng còn lại, mỗi dòng chứa \(m\) chữ số từ \(0\) đến \(9\) mô tả bảng cơ sở của khóa.

Kết quả

Ghi ra file văn bản sirlockhome.out:

• Dòng thứ nhất chứa một số nguyên là số ô tối thiểu cần thay đổi.
• Trong \(n\) dòng còn lại, mỗi dòng chứa \(m\) chữ số mô tả một phương án thay đổi các ô chữ số thỏa mãn các điều kiện ở trên.

Nếu có nhiều phương án, bạn được phép đưa ra một phương án bất kỳ.

Ràng buộc

• Subtask \(1\) (\(16\) điểm): \(m \leq 3\)
• Subtask \(2\) (\(22\) điểm): \(m \leq 5\)
• Subtask \(3\) (\(28\) điểm): \(n \leq 100\)
• Subtask \(4\) (\(16\) điểm): Tất cả \(n \cdot m\) chữ số của bảng cơ sở đều giống nhau.
• Subtask \(5\) (\(18\) điểm): Không có ràng buộc gì thêm.

Với mỗi test, bạn được \(0.36\) điểm nếu tìm ra được số ô tối thiểu cần thay đổi, nhưng không tìm ra được phương án thay đổi tối ưu.

Ví dụ

8 2
22
07
19
97
19
97
07
22

6
02
07
19
67
69
77
87
92

Faker -- huyền thoại sống của Liên Minh Huyền Thoại luôn tỏa ra một khí chất lạnh lùng nhưng đầy uy lực. Trên sân khấu, ánh mắt anh sắc bén như thể nhìn thấu mọi bước đi của đối thủ. Những cú di chuyển chuẩn xác, những pha xử lý điêu luyện và tự tin biến Faker thành trung tâm của mọi ánh nhìn. Anh không cần khoa trương, chỉ bằng sự bình tĩnh và phong thái như một "quái vật thầm lặng", Faker khiến người xem vừa nể phục vừa bị cuốn hút. Trong khoảnh khắc quan trọng, khi cả thế giới dõi theo, anh như hóa thân thành "Quỷ Vương Bất Diệt", ung dung định đoạt trận đấu bằng vài thao tác gọn gàng, để rồi khán giả chỉ có thể thốt lên: "Đúng là Faker -- huyền thoại không có người thứ hai".

Mùa chung kết thế giới năm nay, Faker cùng T1 đứng trước cơ hội để viết tiếp một chương nữa cho cuốn tiểu thuyết Chúng tôi đã thống trị thế giới bằng cách nào, bằng việc dành chiếc Summoner's Cup thứ sáu cho SKT-T1, và là chức vô địch thứ ba liên tiếp. Chính vì lẽ đó, hai con số \(3\) và \(6\) được xem là thần số học của Faker năm nay. Trong bài toán này, ta hãy cùng khám phá một loại con số đặc biệt, được gọi là Faker number.

Một số nguyên không âm \(x\) được gọi là Faker Number khi và chỉ khi nó thỏa mãn hai điều kiện sau:

• Trong biểu diễn thập phân, \(x\) chỉ chứa các chữ số \(3\) và \(6\); và số chữ số \(3\) bằng số chữ số \(6\).
• Tỷ lệ đối xứng của \(x\) lớn hơn \(50 \%\).

Tỷ lệ đối xứng của số nguyên không âm \(x\) được xác định như sau. Giả sử biểu diễn thập phân của \(x\) có dạng \(\chi_1 \chi_2 \ldots \chi_{\eta}\), vơi \(\eta\) là số chữ số của \(x\), \(\chi_1\) là chữ số lớn nhất \((\chi_1 > 0)\) và \(\chi_{\eta}\) là chữ số hàng đơn vị. Khi đó:

• Gọi \(\alpha(x)\) là số cặp chỉ số \((\mu, \nu)\) sao cho \(1 \leq \mu \leq \nu \leq \eta\) và dãy chữ số \(\chi_{\mu} \chi_{\mu + 1} \chi_{\mu + 2} \ldots \chi_{\nu}\) là một dãy đối xứng. Một dãy đối xứng là dãy mà đọc từ trái qua phải hay từ phải qua trái đều như sau.
• Gọi \(\beta(x)\) là số cặp chỉ số \((\mu, \nu)\) sao cho \(1 \leq \mu \leq \nu \leq \eta\).
• Tỉ lệ đối xứng của \(x\) được tính theo công thức \(\gamma(x) = \frac{\alpha(x)}{\beta(x)}\).

Ví dụ:

• Với \(x = 3366\), ta có \(\alpha(x) = 6\), \(\beta(x) = 10\). Tỷ lệ đối xứng là \(\gamma(x) = \frac{6}{10}\).
• Với \(x = 336366\), ta có \(\alpha(x) = 10\), \(\beta(x) = 21\). Tỷ lệ đối xứng là \(\gamma(x) = \frac{10}{21}\).
  Từ định nghĩa trên, ta có thể thấy \(36\) hay \(3366\) là các Faker number, còn \(363\) hay \(336366\) thì không.

Bạn được cho một cây gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\). Gốc của cây là đỉnh \(1\). Mỗi đỉnh có giá trị là một số nguyên không âm. Ban đầu, giá trị của các đỉnh lần lượt là \(a_1, a_2, \ldots, a_n\). Bạn cần thực hiện \(q\) thao tác, mỗi thao tác thuộc một trong ba dạng sau:

• \(1\) \(u\) \(v\) \(x\): Tăng giá trị các đỉnh trên đường đi từ \(u\) đến \(v\) (bao gồm cả \(u\) và \(v\)) thêm \(x\).
• \(2\) \(u\) \(v\): Đếm số đỉnh trên đường đi từ \(u\) đến \(v\) (bao gồm cả \(u\) và \(v\)) có giá trị là một Faker Number.
• \(3\) \(u\): Đếm số đỉnh thuộc cây con gốc \(u\) có giá trị là một Faker Number.

Dữ liệu

Vào từ file văn bản fakernum.inp:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n \le 10^5, 1 \le q \le 5 \cdot 10^5 )\) lần lượt là số đỉnh của cây và số thao tác cần thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10^{16})\) thể hiện giá trị ban đầu của các đỉnh trên cây.
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u, v \le n)\) cho biết trên cây có một cạnh nối hai đỉnh \(u\) và \(v\).
• Trong \(q\) dòng cuối cùng, mỗi dòng mô tả một thao tác theo một trong ba dạng ở trên. Các tham số của các thao tác thỏa mãn \(1 \le u, v \le n\) và \(1 \le x \le 10^{16}\). Dữ liệu đảm bảo trong mọi thời điểm, giá trị của mọi đỉnh trên cây không vượt quá \(10^{16}\).

Kết quả

Ghi ra file văn bản fakernum.out:

• Với mỗi thao tác loại \(2\) và \(3\), in ra trên một dòng một số nguyên duy nhất là kết quả của thao tác đó.

Ràng buộc

• Subtask \(1\) (\(13\) điểm): \(n \le 1000, q \le 5000\).
• Subtask \(2\) (\(17\) điểm): Không có thao tác loại \(1\).
• Subtask \(3\) (\(19\) điểm): \(a_1 = a_2 = \ldots = a_n = 0\) và trong mọi thao tác loại \(1\), \(x = 1\).
• Subtask \(4\) (\(19\) điểm): Cây thỏa mãn tính chất sau: tồn tại một hoán vị \((p_1, p_2, \ldots, p_n)\) của các số \((1, 2, \ldots, n)\) sao cho với mọi \(2 \leq i \leq n\), có một cạnh nối hai đỉnh \(p_i\) và \(p_{\lfloor \frac{i}{2} \rfloor}\).
• Subtask \(5\) (\(19\) điểm): Cây thỏa mãn tính chất sau: tồn tại một hoán vị \((p_1, p_2, \ldots, p_n)\) của các số \((1, 2, \ldots, n)\) sao cho với mọi \(2 \leq i \leq n\), có một cạnh nối hai đỉnh \(p_i\) và \(p_{i - 1}\).
• Subtask \(6\) (\(13\) điểm): Không có ràng buộc gì thêm.

Ví dụ

5 7
0 0 0 0 0
1 2
1 3
3 5
3 4
1 2 4 3
1 5 5 3
1 2 5 33
1 4 4 33
2 1 4
2 2 3
3 3

3
3
3