Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2020 - Tin học - Khối 11

Do dịch Covid-19, hai bạn Hồng và Chi không được đi học và gặp nhau nhưng hai bạn vẫn thường xuyên nhắn tin cho nhau. Một lần, Hồng muốn gửi mật khẩu tham gia lớp học online cho Chi nhưng không muốn em Phúc tò mò và biết được. Theo ý tưởng giấu tin trong ảnh, Hồng quyết định sẽ giấu mật khẩu vào trong đoạn văn bản gửi cho Chi. Cụ thể, với một văn bản mà Hồng gửi cho Chi được biểu diễn bằng xâu ký tự \(T=t_1t_2 \cdots t_n\) (gồm \(n\) ký tự, mỗi ký tự thuộc \(′a′\) đến \(′z′\)) và dãy số nguyên \(a_1,a_2,…,a_m\) \((1 \leq a_1<a_2< \cdots <a_m \leq n)\) là dãy số mà hai bạn đã thống nhất thì mật khẩu là một xâu \(P=t_{a_1}t_{a_2} \cdots t_{a_m}\), là xâu độ dài \(m\) nhận được bằng cách ghép lần lượt các ký tự ở các vị trí \(a_1,a_2,\cdots,a_m\). Ví dụ, \(T= ′missyouuu′\) và dãy số \(a_1=2,a_2=3,a_3=5,a_4=6,a_5=8\) thì mật khẩu là \(P= “isyou”\).

Hồng nhanh chóng nhận ra rằng, với một xâu \(T\) và mật khẩu \(P\) sẽ tồn tại nhiều dãy số để xác định mật khẩu. Ví dụ, một dãy số khác \(a_1=2,a_2=4,a_3=5,a_4=6,a_5=7\) cũng xác định được mật khẩu \(P= “isyou”\) trong xâu \(T= ′missyouuu′\).

Trong quá trình gửi, xâu \(T\) sẽ được mã hóa theo phương thức RLE (Run Length Encoding). Nghĩa là, một xâu \(T\) chỉ gồm các ký tự \(‘a’\) đến \(‘z’\) được mã hóa thành xâu \(TE\) (chỉ gồm các ký tự \(‘a’\) đến \(‘z’\) và ký tự \(‘0’\) đến \(‘9’\)) bằng cách đi từ trái sang phải, mã hoá dãy các ký tự liên tiếp giống nhau trong \(T\) thành ký tự đại diện và số lượng.

Ví dụ, xâu \(T= ′missyouuuuuuuuuu′\) thì \(TE= ′m1i1s2y1o1u10′\).

Yêu cầu: Cho xâu \(TE\) (là mã hóa của xâu \(T\)) và xâu mật khẩu \(P\), gọi \(R\) là số lượng dãy số khác nhau có thể xác định được mật khẩu \(P\) trong xâu \(T\). Hãy tính \(R\) chia dư cho \(10^9+7\).

Input

• Dòng đầu chứa hai số nguyên dương \(n,m\);
• Dòng thứ hai chứa một xâu là mã hóa của xâu \(T\)
• Dòng thứ ba chứa một xâu là xâu \(P\).

Output

• Ghi ra một số nguyên duy nhất là số \(R\) chia dư cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20,m=1\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 20,m<n\);
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^5,m=3\);
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^5,m \leq 30\);
• Subtask \(5\) (\(20\%\) số điểm): \(n \leq 10^9,m \leq 30\) và xâu mã hóa của xâu \(T\) có độ dài không vượt quá \(10^5\)

Example

9 5
m1i1s2y1o1u3
isyou 

6

11 3
m1i1s2i1s2i1p2i1
isi 

14

Dịch Covid-19 đã được kiểm soát, trong gần một tháng qua, tại Việt nam không có ca nhiễm mới trong cộng đồng. Lệnh cách ly đã được nới lỏng, Hồng và các bạn được đi học trở lại, đó cũng là thời điểm thầy Phương mở trại HCC cho các bạn yêu thích lập trình, một hoạt động mà thầy đã duy trì trong nhiều năm qua. Tham gia HCC, Hồng rất thích thú với một bài toán của thầy Phương, bài toán mô phỏng việc di chuyển của virus, cụ thể bài toán như sau: Xét lưới ô vuông thước \(m \times n\), các dòng được đánh số từ \(1\) đến \(m\) từ trên xuống, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm trên giao của dòng \(i\), cột \(j\) được gọi là ô \((i,j)\) và ô này chứa một số nguyên dương \(a(i,j)\). Nếu một virus đang ở ô \((x,y)\), virus có thể thực hiện bước di chuyển sau:

• Virus di chuyển sang ô kề cạnh với ô \((x,y)\) nằm trong lưới, việc di chuyển này mất 1 đơn vị thời gian;
• Virus di chuyển sang ô \((u,v)\) nằm trong lưới nếu \(u \times v=a(x,y)\), việc di chuyển này mất 3 đơn vị thời gian.

Bài toán yêu cầu tính thời gian nhỏ nhất để virus di chuyển từ ô \((p,q)\) đến ô \((r,s)\).

Đây là bài toán khó đối với Hồng nên Hồng nhờ các anh chị tham gia kỳ thi Duyên Hải năm 2020 giải giúp.

Yêu cầu: Cho lưới kích thước \(m \times n\) và các số trên lưới. Có \(h\) câu hỏi, với câu hỏi thứ \(k\) (\(k=1,2, \cdots ,h\)) cần phải trả lời thời gian nhỏ nhất để virus di chuyển từ ô \((p_k,q_k)\) đến ô \((r_k,s_k)\) là bao nhiêu?

Input

• Dòng đầu chứa ba số nguyên dương \(m,n,h\) \((h \leq 5)\);
• Dòng thứ \(i\) \((i=1,2,\cdots,m)\) trong \(m\) dòng tiếp theo chứa \(n\) số nguyên dương \(a(i,1)\),\(a(i,2)\),\(\cdots\),\(a(i,n)\). Các số có giá trị không vượt quá \(10^6\).
• Dòng thứ \(k\) \((k=1,2,\cdots,h)\) trong \(h\) dòng tiếp theo chứa bốn số nguyên \(p_k,q_k,r_k,s_k\).

Output

• Ghi ra \(h\) dòng, dòng thứ \(k\) \((k=1,2,\cdots,h)\) ghi một số nguyên là thời gian nhỏ nhất để virus di chuyển từ ô \((pk,qk)\) đến ô \((rk,sk)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m \times n \leq 10^2\);
• Subtask \(2\) (\(20\%\) số điểm): \(m \times n \leq 10^3\);
• Subtask \(3\) (\(20\%\) số điểm): \(m \times n \leq 10^4\);
• Subtask \(4\) (\(20\%\) số điểm): \(m \times n \leq 10^5\);
• Subtask \(5\) (\(20\%\) số điểm): \(m \times n \leq 10^6\)

Example

2 5 2
8 6 4 1 1
1 1 1 1 1
1 1 2 5
2 5 1 1 

4
3

Vào ngày 19 tháng 5, là ngày sinh nhật Bác, thầy Phương sẽ tổ chức một buổi liên hoan và tặng thưởng cho các bạn có nhiều tiến bộ khi tham HCC. Có \(n\) bạn được mọi người đánh giá cao, các bạn này sẽ được nhận quà của thầy Phương. Thầy Phương đã chuẩn bị \(m\) món quà, đồng thời thu thập thông tin mong muốn nhận quà của từng bạn. Các bạn được đánh số từ 1 đến \(n\), các món quà được đánh số từ 1 đến \(m\), với bạn thứ \(i(i=1,2,\cdots,n)\) và món quà \(j (j=1,2,\cdots,m)\) thầy Phương có thông tin \(s_{i_j}\) là một số nguyên dương đánh giá nguyện vọng của bạn \(i\) muốn nhận món quà \(j\).

Mỗi một món quà sẽ được tặng cho đúng một bạn, mỗi bạn sẽ được nhận ít nhất một món quà. Gọi \(r_i\) \((i=1,2,\cdots,n)\) là tổng đánh giá nguyện vọng của các món quà mà người \(i\) nhận được và \(w=min\){\(r_1,r_2,\cdots,r_n\)}. Thầy Phương muốn tìm cách tặng quà để giá trị \(w\) đạt giá trị càng lớn càng tốt.

Yêu cầu: Cho \(n,m\) và các giá trị \(s_{i_j}\), em hãy giúp thầy Phương tìm phương án tặng quà để giá trị \(w\) đạt giá trị càng lớn càng tốt.

Input

• Dòng đầu chứa hai số nguyên dương \(n,m\) \((n \leq m)\);
• Dòng thứ \(i (i=1,2,\cdots,n)\) trong \(n\) dòng tiếp theo chứa \(m\) số nguyên dương \(s_{i1},s_{i2},\cdots,s_{im}\). Các số có giá trị không vượt quá 1000.

Output

• Ghi ra \(n\) dòng, dòng thứ \(i (i=1,2,\cdots,n)\) có dạng:
  • Số đầu tiên ghi số \(p_i\) là số món quà mà bạn \(i\) nhận được;
  • Tiếp theo là \(p_i\) số là chỉ số những món quà mà bạn \(i\) được nhận. Các chỉ số được liệt kê theo thứ tự tăng dần.
    Tính điểm:
    Với mỗi test, gọi \(w_p\) là giá trị theo phương án mà thầy Phương tìm được (giá trị này em không được biết, chỉ dùng khi chấm), \(w\) giá trị theo phương án của em, khi đó em sẽ nhận được \(\frac{1000 \times w − 999\times w_p}{w_p}\) trên tổng số 1 điểm của test đó, nếu \(1000 \times w < 999 \times w_p\) em sẽ nhận 0 điểm. Khác với kỳ thi chính thức, các bạn sẽ được bonus nếu đáp án lớn hơn đáp án của thầy.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m,n \leq 12\);
• Subtask \(2\) (\(40\%\) số điểm): \(m \leq 1200,n=2\);
• Subtask \(3\) (\(30\%\) số điểm): \(m=n \leq 1200\)

Example

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

2 4 5
3 1 2 3