Google Code Jam 2019 - Alien Rhyme
Xem PDFĐề bài
Trong một chuyến thám hiểm ngoài Trái Đất, bạn đã tìm thấy bằng chứng về thơ ca của người ngoài hành tinh! Nhóm ngôn ngữ học của bạn xác định rằng mỗi từ trong ngôn ngữ ngoài hành tinh có trọng âm ở đúng một vị trí (một chữ cái) trong từ; phần của từ bắt đầu từ chữ cái mang trọng âm được gọi là hậu tố trọng âm. Hai từ được coi là gieo vần nếu hậu tố trọng âm của chúng giống nhau. Chẳng hạn, hai từ PROL và TARPOL gieo vần nếu chữ cái mang trọng âm trong cả hai từ là O hoặc L, nhưng chúng không gieo vần nếu các chữ cái mang trọng âm là hai chữ R, hoặc là R trong PROL và P trong TARPOL, hoặc là O trong PROL và L trong TARPOL.
Bạn đã khôi phục được danh sách \(N\) từ có thể thuộc một bài thơ ngoài hành tinh. Đáng tiếc là bạn không biết chữ cái nào mang trọng âm trong mỗi từ. Bạn tin rằng mình có thể loại bỏ không hoặc nhiều từ trong số này, gán chữ cái mang trọng âm cho các từ còn lại, rồi sắp xếp các từ đó thành từng cặp sao cho mỗi từ chỉ gieo vần với từ còn lại trong cặp của nó và không gieo vần với bất kỳ từ nào thuộc các cặp khác.
Hãy tìm số lượng từ lớn nhất có thể được sắp xếp thành các cặp theo cách này.
Dữ liệu vào
Dòng đầu tiên 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 số nguyên duy nhất \(N\). Sau đó là \(N\) dòng, mỗi dòng chứa một chuỗi \(W_i\) gồm các chữ cái tiếng Anh in hoa, biểu diễn một từ riêng biệt. Lưu ý rằng cùng một từ có thể được gán trọng âm khác nhau trong các bộ test khác nhau.
Dữ liệu ra
Với mỗi bộ test, in ra một dòng theo định dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)) và y là kích thước của tập con lớn nhất gồm các từ thỏa mãn những tiêu chí nêu trên.
Ràng buộc
- \(1 \le T \le 100\).
- \(1 \le |W_i| \le 50\) với mọi \(i\).
- \(W_i\) chỉ gồm các chữ cái tiếng Anh in hoa với mọi \(i\).
- \(W_i \ne W_j\) với mọi \(i \ne j\) (các từ không lặp lại trong cùng một bộ test).
Phân nhóm
Test Set 1 (Hiển thị)
- \(2 \le N \le 6\).
Test Set 2 (Ẩn)
- \(2 \le N \le 1000\).
Đ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 | 10/37 | 27,03% |
| Test Set 2 | 27/37 | 72,97% |
Ví dụ
Ví dụ 1
Input
4
2
TARPOL
PROL
3
TARPOR
PROL
TARPRO
6
CODEJAM
JAM
HAM
NALAM
HUM
NOLOM
4
PI
HI
WI
FIOutput
Case #1: 2
Case #2: 0
Case #3: 6
Case #4: 2Giải thích
Trong trường hợp mẫu số 1, với cách gán trọng âm thích hợp như đã mô tả ở trên, hai từ có thể gieo vần; vì vậy, tập con lớn nhất chính là toàn bộ dữ liệu vào.
Trong trường hợp mẫu số 2, bất kể gán trọng âm như thế nào, không có hai từ nào có thể gieo vần vì hai hậu tố bất kỳ đều khác nhau ít nhất ở chữ cái cuối cùng. Do đó, tập con lớn nhất là tập rỗng, có kích thước \(0\).
Trong trường hợp mẫu số 3, ta có thể dùng toàn bộ tập từ nếu đặt trọng âm của CODEJAM và JAM tại các chữ J, của HAM và NALAM tại các chữ A cuối cùng, và của HUM và NOLOM tại các chữ M.
Trong trường hợp mẫu số 4, hai từ bất kỳ đều có thể được làm cho gieo vần, nhưng luôn phải đặt chữ cái mang trọng âm là I. Vì vậy, nếu đưa hai cặp vào tập con thì các từ thuộc hai cặp khác nhau cũng sẽ gieo vần. Do đó, ta chỉ có thể tạo một tập con kích thước \(2\) bằng cách chọn hai từ bất kỳ trong dữ liệu vào.
Nguồn
Google Code Jam 2019, Vòng 1A, bài Alien Rhyme.
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 2019 - Round 1A (13 Tháng tư, 2019)
Bình luận