CEOI 2016 - Ngày 2

Một dãy ngoặc hợp lệ được định nghĩa như sau:

• Xâu rỗng là một dãy ngoặc hợp lệ.
• Nếu B là một dãy ngoặc hợp lệ thì (B) cũng là một dãy ngoặc hợp lệ.
• Nếu L và R là hai dãy ngoặc hợp lệ thì phép nối LR cũng là một dãy ngoặc hợp lệ.

Gọi B là một dãy ngoặc hợp lệ có độ dài N; ký tự ở vị trí i được ký hiệu là B_i. Với hai vị trí i < j, B_i và B_j là một cặp ngoặc khớp nhau nếu B_i = '(', B_j = ')', và các ký tự nằm giữa chúng tạo thành một dãy ngoặc hợp lệ hoặc j = i + 1.

Cho xâu S gồm N chữ cái tiếng Anh viết thường. Dãy ngoặc hợp lệ B khớp với S nếu B có độ dài N và hai ký tự trong mọi cặp ngoặc khớp của B nằm ở các vị trí có cùng chữ cái trong S.

Hãy tìm dãy ngoặc hợp lệ nhỏ nhất theo thứ tự từ điển khớp với S. Nếu không tồn tại, in -1. Khi so sánh thứ tự từ điển, ký tự ( nhỏ hơn ký tự ).

Dữ liệu vào

Một dòng chứa xâu S gồm N chữ cái tiếng Anh viết thường.

Dữ liệu ra

In ra dãy ngoặc hợp lệ nhỏ nhất theo thứ tự từ điển khớp với S, hoặc -1 nếu không tồn tại.

Ràng buộc

• 2 ≤ N ≤ 100000.

Phân nhóm

• Nhóm 1: N ≤ 18, đạt 10 điểm.
• Nhóm 2: N ≤ 2000, đạt thêm 27 điểm.
• Nhóm 3: Không có ràng buộc bổ sung, đạt 63 điểm còn lại.

Ví dụ

abbaaa

(()())

abab

-1

Nguồn

CEOI 2016, Ngày 2, Bài 1.

Từ tiếng Rumani “popeală” bắt nguồn từ một tiểu thuyết lịch sử Rumani, trong đó Hoàng thân Moldavia Alexandru Lăpușneanul dùng một biến thể của từ này để mô tả cuộc trả thù sắp tới nhằm vào những kẻ tiếm quyền. Gần đây, từ này được dùng trở lại trong cộng đồng lập trình Rumani để chỉ những tình huống mà ban ra đề khiến thí sinh gặp khó khăn theo cách bất thường và thường không cố ý, chẳng hạn giới hạn thời gian quá chặt, bộ kiểm thử sai, đề bài sai hoặc bàn phím bị lấy mất. Bài toán này nói về một tình huống như vậy.

Một cuộc thi có N thí sinh và một bài toán gồm T bộ kiểm thử. Ban ra đề muốn chia các bộ kiểm thử thành tối đa S nhóm. Mỗi bộ kiểm thử thuộc đúng một nhóm; mỗi nhóm không rỗng và gồm các bộ kiểm thử liên tiếp.

Nếu một thí sinh làm sai ít nhất một bộ kiểm thử trong một nhóm thì thí sinh đó nhận 0 điểm cho nhóm ấy. Nếu làm đúng tất cả bộ kiểm thử trong nhóm thì điểm nhận được bằng tổng điểm của các bộ kiểm thử trong nhóm.

Sau cuộc thi, ban ra đề biết mỗi thí sinh làm đúng những bộ kiểm thử nào. Họ muốn chọn cách chia nhóm sao cho tổng điểm mà tất cả thí sinh có thể đạt được là nhỏ nhất.

Cho mảng Points gồm T số nguyên, trong đó Points[i] là điểm của bộ kiểm thử thứ i, và ma trận Results kích thước N × T. Results[i][j] = 1 nếu thí sinh thứ i làm đúng bộ kiểm thử thứ j, ngược lại bằng 0.

Với mỗi K từ 1 đến S, hãy tìm tổng điểm nhỏ nhất có thể đạt được nếu chia các bộ kiểm thử thành đúng K nhóm.

Dữ liệu vào

• Dòng đầu gồm ba số nguyên N, T, S.
• Dòng thứ hai gồm T số nguyên dương là các phần tử của mảng Points.
• N dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài T mô tả một hàng của ma trận Results.

Dữ liệu ra

In ra S dòng. Dòng thứ K chứa số điểm nhỏ nhất có thể đạt được khi chia các bộ kiểm thử thành đúng K nhóm.

Ràng buộc

• 1 ≤ T ≤ 20000.
• 1 ≤ N ≤ 50.
• 1 ≤ S ≤ min(50, T).
• 1 ≤ Points[i] ≤ 10000.
• (Points[1] + Points[2] + ... + Points[T]) × N ≤ 2000000000.

Phân nhóm

• Nhóm 1: T ≤ 40, đạt 8 điểm.
• Nhóm 2: T ≤ 500, đạt thêm 9 điểm.
• Nhóm 3: T ≤ 4000, đạt thêm 9 điểm.
• Nhóm 4: Không có ràng buộc bổ sung, đạt 74 điểm còn lại.

Ví dụ

2 3 3
4 3 5
101
110

0
8
16

Nguồn

CEOI 2016, Ngày 2, Bài 2.

Lưu ý: Câu “Bất cứ mã nào bạn viết đều có thể được dùng để chống lại bạn” trong đề gốc được ghi chú là một câu đùa.

Henry và Hetty được giao thiết kế một bộ định tuyến gồm:

• \(N\) nút vào, đánh số từ \(1\) đến \(N\).
• \(N\) nút ra, đánh số từ \(N+1\) đến \(2N\).
• Một số nút trung gian, được đánh số tiếp theo.
• Các kết nối có hướng giữa những cặp nút khác nhau.

Nút \(X\) có thể truyền dữ liệu đến nút \(Y\) nếu \(X=Y\), hoặc nếu dữ liệu có thể truyền từ \(X\) đến một nút \(Z\) và có kết nối trực tiếp từ \(Z\) đến \(Y\).

Bộ định tuyến hợp lệ phải thỏa mãn tất cả các điều kiện sau:

• Mỗi nút vào truyền được dữ liệu đến mọi nút ra.
• Mỗi nút vào chỉ nhận được dữ liệu từ chính nó.
• Mỗi nút ra chỉ truyền được dữ liệu đến chính nó.
• Nếu \(X\ne Y\) và \(X\) truyền được dữ liệu đến \(Y\), thì \(Y\) không truyền được dữ liệu ngược lại đến \(X\).
• Với mọi cặp nút \(X\ne Y\) mà \(X\) truyền được dữ liệu đến \(Y\), chỉ có duy nhất một đường đi có hướng từ \(X\) đến \(Y\).
• Tổng số nút không vượt quá \(500\,000\).
• Số kết nối không vượt quá giới hạn \(M_{\text{lim}}\).
• Công suất lớn nhất không vượt quá giới hạn \(P_{\text{lim}}\).

Với mỗi nút \(X\), đặt \(IN_X\) là số nút vào có thể truyền dữ liệu đến \(X\) và \(OUT_X\) là số nút ra có thể nhận dữ liệu từ \(X\). Công suất của \(X\) là \(P_X=IN_X\cdot OUT_X\). Công suất lớn nhất của bộ định tuyến là giá trị lớn nhất của \(P_X\) trên mọi nút.

Dữ liệu vào

Bạn không cần viết chương trình giải bài toán. Hệ thống cung cấp các tệp 0-router.in, 1-router.in, ..., 7-router.in. Mỗi tệp gồm ba số nguyên \(N\), \(M_{\text{lim}}\), \(P_{\text{lim}}\).

Dữ liệu ra

Nộp một tệp ZIP chứa thư mục router-out. Với mỗi tệp đầu vào có chỉ số \(i\), thư mục phải chứa i-router.out.

Mỗi tệp đầu ra gồm:

• Dòng đầu chứa hai số nguyên \(N_{\text{tot}}\) và \(M\): tổng số nút và số kết nối.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X,Y\), biểu diễn kết nối có hướng từ \(X\) đến \(Y\).

Các nút vào là \(1,\ldots,N\), các nút ra là \(N+1,\ldots,2N\), và các nút còn lại là nút trung gian. Mọi số hiệu nút phải nằm trong đoạn \([1,N_{\text{tot}}]\).

Phân nhóm

• Tệp kiểm thử 1: \(N=118\), \(M_{\text{lim}}=1\,000\,000\), \(P_{\text{lim}}=1\,000\,000\), chiếm \(4\%\) số điểm.
• Tệp kiểm thử 2: \(N=223\), \(M_{\text{lim}}=1\,000\,000\), \(P_{\text{lim}}=1\,000\,000\), chiếm \(5\%\) số điểm.
• Tệp kiểm thử 3: \(N=1250\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=500\,000\), chiếm \(6\%\) số điểm.
• Tệp kiểm thử 4: \(N=5101\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=500\,000\), chiếm \(6\%\) số điểm.
• Tệp kiểm thử 5: \(N=9934\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=500\,000\), chiếm \(26\%\) số điểm.
• Tệp kiểm thử 6: \(N=9955\), \(M_{\text{lim}}=500\,000\), \(P_{\text{lim}}=100\,000\), chiếm \(30\%\) số điểm.
• Tệp kiểm thử 7: \(N=9978\), \(M_{\text{lim}}=100\,000\), \(P_{\text{lim}}=100\,000\), chiếm \(23\%\) số điểm.

Tệp kiểm thử 0 là ví dụ và không tính điểm.

Ví dụ

Với đầu vào 3 100 200, một bộ định tuyến hợp lệ có thể gồm \(9\) nút và \(8\) kết nối:

9 8
1 7
2 7
3 8
7 8
8 4
8 9
9 5
9 6

Nút 8 nhận dữ liệu từ ba nút vào và truyền đến ba nút ra, nên công suất của nút này là \(3\cdot3=9\). Có thể có nhiều bộ định tuyến hợp lệ cho cùng một bộ giới hạn.

Nguồn

CEOI 2016, ngày 2, bài 3.