[TFL x Tân Khoa] Contest #3 "Ôn thi Tuyển sinh 10" (TS10 Chuyên Tin 2025)

Ngày hội văn hóa dân gian trường THPT Chuyên Lê Quý Đôn được tổ chức vào mùa xuân hằng năm, nhằm thu hút các bạn học sinh trên toàn thành phố tham gia cũng như tạo ra một mùa hoạt động ngoại khóa sôi nổi, giúp các bạn học sinh của trường có những kỉ niệm đáng nhớ sau những kì học căng thẳng, đồng thời rèn luyện, phát triển các kĩ năng mềm, gắn kết mối quan hệ trong nội bộ các lớp và giữa các tập thể với nhau, đồng thời thúc đẩy các bạn tìm hiểu và trân trọng những giá trị văn hóa dân tộc độc đáo, sâu sắc.

Trong Lễ hội năm nay, ban tổ chức thiết kế một trò chơi rút thăm để gắn kết các lớp học. Mỗi lớp nhận một xâu ký tự đại diện cho một thông điệp. Hai xâu được gọi là tương tự nhau nếu có thể sắp xếp lại các chữ cái của xâu này để tạo thành xâu kia. Hai lớp có xâu đại diện tương tự nhau sẽ được xếp vào cùng một nhóm (mỗi lớp là một thành viên của nhóm).

Lớp chuyên Toán, chuyên Lý và chuyên Tin lần lượt nhận được các xâu đại diện \(X\), \(Y\), và \(Z\). Chỉ xét trong ba lớp này, xác định nhóm có số lượng thành viên nhiều nhất là bao nhiêu?

Yêu cầu

Cho biết \(X\), \(Y\), \(Z\), đếm số lượng thành viên trong nhóm lớn nhất.

Input

• Nhập vào từ bàn phím:
  • Dòng đầu tiên chứa xâu \(X\) (xâu đại diện của lớp chuyên Toán)
  • Dòng thứ nhì chứa xâu \(Y\) (xâu đại diện của lớp chuyên Lý)
  • Dòng thứ ba chứa xâu \(Z\) (xâu đại diện của lớp chuyên Tin)
  • Dữ liệu vào đảm bảo độ dài của mỗi xâu không vượt quá \(10^5\)

Output

• In ra màn hình:
  • Dòng duy nhất chứa kết quả bài toán – kích thước nhóm lớn nhất.

Example

GSPVH
HSGVP
TS10

2

Ràng buộc

• \(40\%\) số điểm có độ dài mỗi xâu \(\le 10\);
• \(30\%\) số điểm khác tương ứng với \(X\), \(Y\), \(Z\) là các xâu nhị phân (chỉ chứa các ký tự 0, 1);
• \(30\%\) số điểm còn lại: không có ràng buộc gì thêm.

Tiết mục "Nhảy dân vũ" trong Lễ hội văn hóa dân gian năm nay có \(n\) lớp học tham gia, mỗi lớp đăng ký biểu diễn một tiết mục. Danh sách các tiết mục nhà trường cho phép đăng ký bao gồm \(k\) bài hát khác nhau (ví dụ như: Việt Nam ơi, Trống cơm, Con cào cào, …). Mỗi lớp có thể lựa chọn đăng ký một trong \(k\) bài hát này để biểu diễn. Đánh số thứ tự các bài hát này từ \(1\) tới \(k\). Bài hát thứ \(i\) được \(a_i\) lớp đăng ký.

Ban tổ chức muốn sắp xếp thứ tự biểu diễn của \(n\) tiết mục này để tạo thành một chương trình liên tục. Nhằm đánh giá độ đa dạng của chương trình, Ban tổ chức cần tính số lượng cách sắp xếp khác nhau của các tiết mục. Hai cách sắp xếp được coi là khác nhau nếu tồn tại ít nhất một vị trí \(i\) (\(1 \le i \le n\)) mà tiết mục (bài hát) tại thứ tự \(i\) trong hai cách sắp xếp là khác nhau.

Yêu cầu: Đếm số cách sắp xếp khác nhau (độ đa dạng), chia lấy dư cho \(10^9 + 7\).

Input

• Dọc vào từ tệp DANCE.INP:
  • Dòng đầu tiên gồm hai số nguyên dương \(n, k\) (\(1 \le k \le n \le 10^5\)).
  • Dòng thứ hai chứa \(k\) số nguyên dương \(a_1, a_2, \dots, a_k\) (\(1 \le a_i \le k\)).
  • Dữ liệu đầu vào đảm bảo \(a_1 + a_2 + \dots + a_k = n\).

Output

• Ghi ra tệp DANCE.OUT:
  • Một số nguyên duy nhất là độ đa dạng của chương trình, chia lấy dư \(10^9 + 7\).

Example

4 2
2 2

6

Ràng buộc

• \(30\%\) số điểm tương ứng với \(n \le 8\).
• \(30\%\) số điểm khác tương ứng \(k = 2, a_1 = 2\).
• \(20\%\) số điểm khác tương ứng với \(k = 2, n \le 10^3\).
• \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Lễ hội năm nay, nhà trường tổ chức \(n\) gian hàng ẩm thực, được đánh số từ \(1\) đến \(n\). Mỗi gian hàng ngoài những món ăn vô cùng thích mắt, với mùi vị hấp dẫn không thể cưỡng lại, còn được chuẩn bị một chiếc lồng đèn lấp lánh mang đậm dấu ấn dân gian, một sự trang trí tinh tế giúp ngày hội trở nên rực rỡ sắc màu giữa lòng Đà Nẵng về đêm. Gian hàng thứ \(i\) có độ sáng của lồng đèn là \(a_i\), và độ hấp dẫn của ẩm thực tại đây là \(b_i\).

Dựa trên các món ăn và lồng đèn trang trí tại mỗi gian hàng; tất cả gian hàng đều được ban tổ chức chấm điểm (Lưu ý: Điểm số có thể âm!). Quy tắc tính điểm của Ban giám khảo (BGK) được mô tả cụ thể như sau. Với mỗi gian hàng \(i\) (\(1 \le i \le n\)):

• Lồng đèn tại \(i\) có thể truyền ánh sáng tới những gian hàng có khoảng cách tới nó không quá \(a_i\). Vì vậy, với mọi gian hàng \(j\) thỏa mãn \(0 \le |i - j| \le a_i\), số điểm của gian hàng \(j\) được tăng thêm một lượng là \(a_i - |i - j|\).
• Mùi hương của các món ăn tại \(i\) cũng có thể truyền tới những gian hàng có khoảng cách không quá \(b_i\). Vì mùi hương của gian hàng \(i\) sẽ thu hút BGK cũng như các vị khách mời nên các gian hàng xung quanh có thể bị ảnh hưởng. Bởi vậy, với mọi gian hàng \(j\) thỏa mãn \(0 < |i - j| \le b_i\), số điểm của gian hàng \(j\) bị giảm đi một lượng là \(b_i - |i - j|\).
• Mặt khác, sự hấp dẫn tại gian hàng \(i\) sẽ giúp nó ghi được \(b_i\) điểm trong mắt BGK.

Sau đêm văn hóa dân gian, ban tổ chức sẽ trao phần thưởng và quà lưu niệm cho tập thể có gian hàng ẩm thực đạt điểm cao nhất. Tuy nhiên, vì số lượng gian hàng được bày bán quá nhiều, BGK nhờ đến các bạn học sinh chuyên Tin lập trình để tính toán số điểm.

Input

• Dữ liệu nhập vào từ tệp CUISINE.INP:
  • Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)) – số gian hàng ẩm thực được bày bán tại mùa văn hóa dân gian năm nay.
  • Dòng thứ hai gồm dãy số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) – độ sáng của từng chiếc lồng đèn tại các gian hàng.
  • Dòng thứ ba gồm dãy số nguyên dương \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^9\)) – độ hấp dẫn của các món ăn được bày bán tại các gian hàng.

Output

• Xuất ra tệp CUISINE.OUT:
  • Dòng duy nhất chứa kết quả của bài toán – chỉ số của gian hàng đạt điểm cao nhất, cùng với điểm số của nó. Nếu nhiều gian hàng có cùng số điểm cao nhất, in ra chỉ số nhỏ nhất.

Example

4
2 3 3 2
4 2 2 4

1 7

Ràng buộc

• \(20\%\) số điểm tương ứng với \(n \le 3\);
• \(20\%\) số điểm khác tương ứng với \(n \le 2 \cdot 10^3\);
• \(20\%\) số điểm khác tương ứng với \(a_1 = a_2 = \dots = a_n\); \(b_1 = b_2 = \dots = b_n\);
• \(20\%\) số điểm khác tương ứng với \(n \le 10^5\);
• \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Trong phần thi Trò chơi lớn, lớp chuyên Tin và lớp chuyên Toán cùng đạt số điểm cao nhất. Để phân định thắng thua và tìm ra nhà vô địch, BTC Hội trại đã đưa ra một thử thách cuối cùng, là một câu đố như sau:

“Cho một nền nhà hình vuông có độ dài cạnh \(n = 2^k\). Nền nhà này bị khuyết một số ô theo quy luật đặc biệt. Có hai loại nền nhà như sau:

• Loại I: Khuyết một phần tư, ở một trong bốn góc: 1 - trái trên, 2 - phải trên, 3 - trái dưới, 4 - phải dưới
• Loại II: Khuyết một ô duy nhất, nằm bên trong hình vuông.

Nhiệm vụ của bạn là, tìm cách dùng các viên gạch hình thước thợ (hình chữ L), được tạo bởi 3 ô vuông đơn vị để lát toàn bộ nền nhà (tức phần không bị khuyết).”

Gạch hình thước thợ	Nền loại I (\(k = 3\)), khuyết phần 3	Nền loại II (\(k = 2\)), khuyết ô \((2,3)\)

Một phương án lát nền được coi là hợp lệ nếu thỏa mãn hai điều kiện sau:

1. Mỗi một ô vuông trên nền nhà đều được lát bởi đúng một viên gạch. Đương nhiên, mỗi viên gạch phải lát đúng 3 ô vuông và không nằm đè lên phần bị khuyết.
2. Hai viên gạch kề cạnh nhau phải khác màu nhau. Có 26 màu gạch khác nhau, được ký hiệu bởi các ký tự trong a-z (từ a tới z).

Là một thành viên của lớp chuyên Tin, bạn hãy suy nghĩ giải pháp cho vấn đề này nhé!

Input

• Dữ liệu vào đọc từ tệp PUZZLE.INP:
  • Dòng đầu tiên chứa số nguyên dương \(k\) (\(2 \le k \le 10\)). Kích thước nền là \(n = 2^k\).
  • Dòng thứ hai chứa số \(\lambda\) (\(\lambda \in \{1, 2\}\)) cho biết nền nhà thuộc loại I nếu \(\lambda = 1\) và thuộc loại II nếu \(\lambda = 2\).
  • Dòng thứ ba chứa:
    • Số nguyên \(t\) (\(1 \le t \le 4\)) ký hiệu cho phần bị khuyết, nếu \(\lambda = 1\).
    • Hai số nguyên \(x, y\) (\(1 \le x, y \le n\)) là tọa độ ô khuyết, nếu \(\lambda = 2\).
  • Dữ liệu vào đảm bảo tồn tại cách lát nền thỏa mãn.

Output

• Ghi ra tệp PUZZLE.OUT:
  • Gồm \(n\) dòng, mỗi dòng chứa chính xác \(n\) ký tự mô tả một phương án lát nền.
  • Sử dụng ký tự chữ cái in thường (a-z) biểu thị màu viên gạch. Sử dụng ký tự dấu cách biểu thị cho ô nền khuyết.

Example

2
1
3

zzbb
zaab
  az
  zz

Scoring

• \(20\%\) số điểm tương ứng với \(\lambda = 1\); \(k \le 3\).
• \(20\%\) số điểm khác tương ứng với \(\lambda = 1\); \(k \le 6\).
• \(20\%\) số điểm khác tương ứng với \(\lambda = 1\).
• \(40\%\) số điểm còn lại tương ứng với \(\lambda = 2\).