Google Code Jam 2020 - Pattern Matching
Xem PDFĐề bài
Nhiều trình dòng lệnh dùng dấu sao (*) để biểu thị "một chuỗi bất kỳ", kể cả chuỗi rỗng. Chẳng hạn, khi liệt kê các tệp khớp với BASH*, trình dòng lệnh có thể liệt kê BASH, BASHER và BASHFUL. Với *FUL, nó có thể liệt kê BEAUTIFUL, AWFUL và BASHFUL. Khi liệt kê B*L, nó có thể liệt kê BASHFUL, BEAUTIFUL và BULL.
Trong bài này, nói một cách hình thức, một mẫu là một chuỗi chỉ gồm các chữ cái tiếng Anh in hoa và các dấu sao (*), còn một tên là một chuỗi chỉ gồm các chữ cái tiếng Anh in hoa. Mẫu \(p\) khớp với tên \(m\) nếu ta có thể thay mỗi dấu sao trong \(p\) bằng một chuỗi (có thể rỗng) để thu được \(m\). Lưu ý rằng mỗi dấu sao có thể được thay bằng một chuỗi khác nhau.
Cho \(N\) mẫu, bạn có thể tìm một tên duy nhất gồm không quá \(10^4\) chữ cái và đồng thời khớp với tất cả các mẫu đó, hay xác định rằng điều này là không thể?
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\): số lượng mẫu cần được khớp đồng thời. Sau đó là \(N\) dòng, mỗi dòng chứa một chuỗi \(P_i\) biểu diễn mẫu thứ \(i\).
Dữ liệu ra
Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ 1), còn y là một tên bất kỳ gồm không quá \(10^4\) chữ cái sao cho mỗi \(P_i\) đều khớp với y theo định nghĩa trên; nếu không tồn tại tên như vậy, in * (tức là chỉ một dấu sao).
Ràng buộc
- \(1 \le T \le 100\).
- \(2 \le N \le 50\).
- \(2 \le \operatorname{length}(P_i) \le 100\) với mọi \(i\).
- Mỗi ký tự của \(P_i\) là một chữ cái tiếng Anh in hoa hoặc một dấu sao (
*), với mọi \(i\). - Ít nhất một ký tự của \(P_i\) là một chữ cái tiếng Anh in hoa, với mọi \(i\).
Phân nhóm
Test Set 1 (Visible Verdict)
- Trong mỗi \(P_i\) có đúng một ký tự là dấu sao (
*). - Ký tự ngoài cùng bên trái của mỗi \(P_i\) chính là dấu sao (
*) duy nhất đó.
Test Set 2 (Visible Verdict)
- Trong mỗi \(P_i\) có đúng một ký tự là dấu sao (
*).
Test Set 3 (Visible Verdict)
- Trong mỗi \(P_i\) có ít nhất một ký tự là dấu sao (
*).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 5/28 | 17,86% |
| Test Set 2 | 5/28 | 17,86% |
| Test Set 3 | 18/28 | 64,28% |
Ví dụ
Ví dụ 1
Input
2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZOutput
Case #1: COCONUTS
Case #2: *Giải thích
Trong trường hợp mẫu số 1, còn có các đáp án khả dĩ khác, trong đó có COCOCONUTS và ILIKECOCONUTS. Cả COCONUTSAREGREAT lẫn COCOANUTS đều không được chấp nhận. Lưu ý rằng cùng một mẫu có thể xuất hiện nhiều lần trong một bộ test.
Trong trường hợp mẫu số 2, không có tên nào được chấp nhận, vì vậy đáp án là *.
Các trường hợp sau không thể xuất hiện trong Test Set 1, nhưng có thể xuất hiện trong Test Set 2 hoặc Test Set 3:
4
H*O
HELLO*
*HELLO
HE*
HELLO và HELLOGOODBYEHELLO là những ví dụ về đáp án được chấp nhận. OTHELLO và HELLOO thì không được chấp nhận.
2
CO*DE
J*AM
Không có tên nào khớp với cả hai mẫu, vì vậy đáp án sẽ là *.
2
CODE*
*JAM
CODEJAM là một ví dụ về đáp án được chấp nhận.
Các trường hợp sau không thể xuất hiện trong Test Set 1 hoặc Test Set 2, nhưng có thể xuất hiện trong Test Set 3:
2
A*C*E
*B*D*
ABCDE và ABUNDANCE là hai trong số các đáp án có thể được chấp nhận, còn BOLDFACE thì không.
2
A*C*E
*B*D
Không có tên nào khớp với cả hai mẫu, vì vậy đáp án sẽ là *.
2
**Q**
*A*
QUAIL và AQ là hai trong số các đáp án có thể được chấp nhận ở đây.
Nguồn
Google Code Jam 2020, Vòng 1A, bài Pattern Matching.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2020 - Round 1A (11 Tháng tư, 2020)
Bình luận