DHBB 2021 đề chính thức

Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), một đoạn \(a_L, a_{L+1},..., a_R (1 \le L \le R \le N)\) được gọi là đoạn đẹp nếu \(L, R\) đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

• Dòng đầu chứa số nguyên dương \(n (n \ge 2)\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (|a_i| \le 10^6)\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\);
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^6\);

Example

6
9 5 -2 6 -1 1

8

Kỳ thi Duyên Hải đã trở thành một kỳ thi chất lượng và uy tín. Quy mô kỳ thi vượt qua ranh giới về mặt địa lý và đã thu hút nhiều tỉnh thành tham gia. Cùng với việc mở rộng về quy mô, kỳ thi cũng thay đổi hình thức thi. Kỳ thi Duyên Hải năm 2222, có học sinh tham gia, các học sinh được đánh số từ \(1\) đến \(n\). Tất cả các học sinh sẽ phải trải qua ba bài thi ở ba môn Lập trình tính toán, Trí tuệ nhân tạo và An toàn thông tin với thể thức như sau:

• Với mỗi bài thi, khi các thí sinh thi xong, ban giám khảo sẽ tiến hành chấm điểm bằng nhiều tiêu chí nhằm đảm bảo rằng, không có hai thí sinh nào bằng điểm nhau. Ban Giám khảo lập bảng xếp hạng các thí sinh trên từng môn thi riêng biệt và gửi lên Ban tổ chức ba dãy số \((p_1,p_2,\ldots,p_n)\), \((a_1,a_2,\ldots,a_n)\), \((s_1,s_2,\ldots,s_n)\) tương ứng là xếp hạng của ba môn Lập trình tính toán, trí tuệ nhân tạo và An toàn thông tin. Các dãy số này đều là hoán vị của dãy số \(1,2,\ldots,n\), với ý nghĩa: học sinh thứ \(i\) xếp thứ \(p_i\) ở môn Lập trình tính toán, xếp thứ \(a_i\) ở môn Trí tuệ nhân tạo và xếp thứ \(s_i\) ở môn An toàn thông tin.
• Từ bảng xếp hạng của các môn, Ban tổ chức dùng phần mềm xếp hạng các thí sinh. Thí sinh thứ \(i\) có mức phân hạng \(2^{a_i}+2^{p_i}+2^{s_i}\) và có thứ hạng chung cuộc được tính bằng số thí sinh có mức phân hạng nhỏ hơn cộng với \(1\). Theo cách xếp hạng của phần mềm, có thể có các thí sinh cùng thứ hạng.

Hiện tại, các thí sinh đã hoàn thành bài thi môn Lập trình tính toán và Trí tuệ nhân tạo, ban giám khảo đã chấm điểm và công bố bảng xếp hạng ở hai môn này. Tiếp theo, thí sinh chuẩn bị bước vào môn thi cuối cùng, môn An toàn thông tin. Để có được chiến lược thi phù hợp, mỗi thí sinh muốn biết thứ hạng chung cuộc tốt nhất và tệ nhất có thể của mình, sau khi môn thi cuối cùng diễn ra.

Yêu cầu: Cho biết thứ hạng của các thí sinh ở hai môn Lập trình tính toán và Trí tuệ nhân tạo, hãy giúp mỗi thí sinh tìm ra thứ hạng tốt nhất và tồi nhất chung cuộc có thể của mình khi xét trên mọi khả năng xảy ra đối với kết quả của môn An toàn thông tin.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(p_1,p_2,\ldots,p_n\) là một hoán vị của dãy số \(1,2,\ldots,n\), mô tả thứ hạng của thí sinh ở môn Lập trình tính toán;
• Dòng thứ ba chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) là một hoán vị của các dãy số \(1,2,\ldots,n\) mô tả thứ hạng của thí sinh ở môn Trí tuệ nhân tạo.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) (\(1 \leq i \leq n\)) gồm hai số nguyên dương \(b_i,w_i\) tương ứng là thứ hạng tốt nhất và thứ hạng tệ nhất chung cuộc của thí sinh thứ \(i\).

Scoring

• Subtask 1 (\(30\%\)): \(n \leq 10\);
• Subtask 2 (\(20\%\)): \(n \leq 50\);
• Subtask 3 (\(20\%\)): \(n \leq 200\);
• Subtask 4 (\(30\%\)): \(n \leq 2000\).

Example

3
1 2 3
2 1 3

1 2
1 2
3 3

Là một học sinh yêu thích môn Tin học, Hồng thường tìm cách áp dụng Tin học vào cuộc sống. Hiện tại, Hồng đang gặp một bài toán khó và muốn nhờ các anh chị tham gia kỳ thi Duyên Hải 2021 giải giúp.

Khu vực mà Hồng ở có ba siêu thị, siêu thị A ở trung tâm và hai siêu thị B, C xa trung tâm. Vì xa trung tâm, nên mỗi siêu thị B, C đều có chương trình tích điểm để giảm giá khi mua hàng. Hai chương trình của hai siêu thị là riêng biệt nhưng có hình thức giống nhau. Cụ thể, nếu một khách hàng đã mua hàng ở một siêu thị \(t\) lần thì khách hàng có \(t\) điểm tích lũy tại siêu thị đó, khi khách hàng mua lần tiếp theo (lần thứ \(t + 1\)), khách hàng sẽ được giảm \(t\) đồng trong lần mua đó và số điểm tích lũy tại siêu thị này được tăng lên thành \(t + 1\).

Hồng dự định mua lần lượt mặt hàng, mỗi mặt hàng sẽ được mua ở một trong ba siêu thị A, B, C. Qua khảo sát, Hồng được biết mặt hàng thứ \(i (1 \le i \le n)\) có giá ở ba siêu thị A, B, C tương ứng là \(x_i, y_i, z_i\)
.
Yêu cầu: Cho các giá trị \(x_i, y_i (1 \le i \le n)\) là giá của mặt hàng tương ứng ở ba siêu thị A, B, C, hãy giúp Hồng tìm cách mua hết ít tiền nhất.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa số nguyên dương \(n\);
• Dòng thứ \(i(i = 1, 2, ..., n)\) trong dòng tiếp theo chứa ba số nguyên dương \(x_i, y_i, z_i (n \le x_i, y_i, z_i \le 10^9)\).

Output

• Ghi ra file thiết bị ra chuẩn một số nguyên là tổng tiền ít nhất để mua được \(n\) mặt hàng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10\);
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 200\):
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 3000\)

Example

5
5 5 9
7 8 5
9 9 5
9 9 5
6 6 9

22

Các bé trường mầm non SuperKids đang chơi trò chơi ghép chữ trên một sân hình chữ nhật kích
thước \(m × n\) được chia thành lưới ô vuông đơn vị. Các hàng ô đánh số từ \(1\) tới \(m\) từ trên xuống
và các cột ô được đánh số từ \(1\) tới n từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) được
gọi là ô \((i,j)\) và trên đó chứa đúng một chữ cái hoa \(a_{ij}\).
Mỗi bé khi chơi được cho trước xâu ký tự \(S\) độ dài \(k\) chỉ gồm các chữ cái hoa. Bé được chọn một
ô để xuất phát và thực hiện trò chơi qua nhiều lượt. Tại mỗi lượt, bé bắt buộc phải di chuyển
sang một trong bốn ô kề cạnh với ô đang đứng, sau đó bé được viết ra đúng một chữ cái bằng
với chữ cái tại ô vừa tới nếu muốn. Mục đích của bé là viết ra được xâu ký tự \(S\) đã cho. Chú ý
rằng các chữ cái phải được viết ra lần lượt theo đúng thứ tự trong xâu \(S\) và khi tới một ô chỉ
được viết ra đúng một chữ cái.
Yêu cầu: Hãy giúp bé thực hiện được mục đích của mình trong trò chơi với số lần di chuyển ít
nhất. Cho biết số lần di chuyển theo phương án tìm được

Input

Vào từ file văn bản SPELL.INP

• Dòng 1 chứa ba số nguyên dương \(m, n, k (2 \le m, n, k \le 300)\) cách nhau bởi dấu cách
• Dòng 2 chứa xâu ký tự \(S\) gồm đúng \(k\) chữ cái hoa viết liền.
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) chữ cái hoa liền nhau, chữ cái thứ \(j\) là \(a_{ij}\)

Output

• Ghi ra file văn bản SPELL.OUT một số nguyên duy nhất là số lần di chuyển ít nhất mà
  bé cần thực hiện để đạt được mục đích của trò chơi.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m, n, k \le 4\)
• Subtask \(2\) (\(30\%\) số điểm): \(m, n, k \le 100\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.

Example

2 4 6
DHDBBB
DHAB
ABBD

7

Một trung tâm mua sắm có \(n\) kiốt (kiosk) đánh số từ \(1\) tới \(n\), kiốt thứ \(i\) bán mặt hàng \(c_i\)
. Siêu thị
có \(n − 1\) con đường hai chiều đánh số từ \(1\) tới \(n − 1\), con đường thứ \(i\) nối giữa kiốt \(u_i\) và kiốt \(v_i\)
.
Hệ thống các con đường đi đảm bảo sự đi lại giữa hai kiốt bất kỳ.

Trong thời kỳ dịch bệnh, người ta muốn ngưng hoạt động một số kiốt để dễ dàng kiểm soát các
hoạt động mua bán cũng như giao tiếp với khách hàng. Khi một kiốt bị ngừng hoạt động, tất cả
các con đường nối tới kiốt đó đều bị chặn để đảm bảo an ninh. Ngoài ra vì không muốn ảnh
hưởng nhiều tới khách hàng, siêu thị muốn lập phương án sao cho các kiốt vẫn còn hoạt động
phải thỏa mãn hai điều kiện sau:

• Các kiốt còn hoạt động phải liên thông với nhau: Tức là giữa hai kiốt bất kỳ vẫn được mở
  cửa phải tồn tại đường đi (qua các con đường không bị chặn)
• Tất cả các mặt hàng mang số hiệu từ \(1\) tới \(k\) (là những mặt hàng thiết yếu) đều phải có bán
  ở ít nhất một kiốt còn hoạt động.

Hai phương án được gọi là khác nhau nếu có một kiốt bị ngưng hoạt động trong một phương án
nhưng được phép hoạt động trong phương án còn lại.
Yêu cầu: Hãy cho biết có bao nhiêu phương án khác nhau thỏa mãn điều kiện nêu trên.

Input

Vào từ file văn bản KIOSKS.INP

• Dòng 1 chứa số nguyên dương \(n \le 10^4 , k \le 10\)
• Dòng 2 chứa n số nguyên dương \(c_1, c_2, ... , c_n (\forall i: c_i \le n)\)
• \(n − 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_i , v_i\)

Output

• Ghi ra file văn bản KIOSKS.OUT một số nguyên duy nhất là số dư trong phép chia: số
  phương án thỏa mãn điều kiện đề bài cho \(1000000007 (10^9 + 7)\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = 1\)
• Subtask \(2\) (\(30\%\) số điểm): Mỗi kiốt có không quá 2 con đường nối tới nó.
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.

Example

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

1

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

11

Cho xâu \(S\) gồm \(n\) ký tự \(\in \{0,1\}\) và số tự nhiên \(k\). Hãy tìm cách đảo một số ít nhất các ký tự của
chuỗi \(S\) (đảo ký tự 0 thành ký tự 1 hoặc ngược lại) sao cho chuỗi kết quả có thể được phân tách
thành không quá \(k\) chuỗi con mà mỗi chuỗi con chỉ chứa các ký tự 0 hoặc chỉ chứa các ký tự 1.
Yêu cầu: Cho biết số ký tự ít nhất trong xâu \(S\) cần đảo.

Input

Vào từ file văn bản BITSTR.INP

• Dòng 1 chứa hai số nguyên dương \(n, k \le 2\times 10^5\) cách nhau bởi dấu cách

• Dòng 2 ghi xâu \(S\) (gồm \(n\) ký tự \(\in \{0,1\}\) viết liền nhau)

Output

• Ghi ra file văn bản BITSTR.OUT một số nguyên duy nhất là số ký tự ít nhất trong xâu \(S\)
  cần đảo.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(20\%\) số điểm): \(n, k \le 400\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 2\times 10^5 ; k \le 400\)

• Subtask \(4\) (\(20\%\) số điểm): \(n \le 2\times 10^5 ; k \le 5000\)

• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.

Example

10 1
1000100011

4

6 2
010110

2