1. Google Code Jam 2022 - Double or One Thing
Bạn được cho một chuỗi gồm các chữ cái tiếng Anh in hoa. Bạn có thể đánh dấu một số lượng tùy ý các chữ cái (có thể là tất cả hoặc không chữ nào). Các chữ cái được đánh dấu không nhất thiết phải liên tiếp. Sau đó, một chuỗi mới được tạo ra bằng cách xử lý các chữ cái từ trái sang phải: chữ cái không được đánh dấu được nối vào chuỗi mới một lần, còn chữ cái được đánh dấu được nối vào hai lần.
Ví dụ, nếu chuỗi ban đầu là HELLOWORLD, bạn có thể đánh dấu H, chữ L đầu tiên và cuối cùng, cùng chữ O cuối cùng để thu được
HHELLLOWOORLLD, tức HHELLLOWOORLLD.
Tương tự, nếu không đánh dấu chữ nào, bạn thu được HELLOWORLD; nếu đánh dấu tất cả các chữ cái, bạn thu được HHEELLLLOOWWOORRLLDD. Lưu ý rằng mỗi lần xuất hiện của cùng một chữ cái có thể được đánh dấu độc lập.
Với một chuỗi cho trước, tùy vào cách chọn các chữ cái để đánh dấu, ta có thể thu được nhiều chuỗi khác nhau. Trong tất cả các chuỗi ấy, hãy in ra chuỗi đứng đầu tiên theo thứ tự bảng chữ cái (còn gọi là thứ tự từ điển).
Lưu ý: Chuỗi \(s\) đứng trước một chuỗi khác \(t\) theo thứ tự bảng chữ cái nếu \(s\) là tiền tố của \(t\), hoặc nếu tại vị trí đầu tiên mà \(s\) và \(t\) khác nhau, chữ cái trong \(s\) đứng trước chữ cái trong \(t\) trong bảng chữ cái. Ví dụ, các chuỗi sau đang ở đúng thứ tự bảng chữ cái: CODE, HELLO, HI, HIM, HOME, JAM.
Dữ liệu vào
Dòng đầu tiên chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test. Mỗi bộ test được mô tả trên một dòng duy nhất chứa chuỗi \(\mathbf{S}\).
Dữ liệu ra
Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là chuỗi đứng đầu tiên theo thứ tự bảng chữ cái trong tập các chuỗi có thể được tạo từ \(\mathbf{S}\) bằng quy trình đã mô tả.
Ràng buộc
- \(1 \le \mathbf{T} \le 100\).
- Mỗi ký tự của \(\mathbf{S}\) là một chữ cái tiếng Anh in hoa.
Phân nhóm
- Test Set 1 (phán quyết hiển thị): \(1 \le |\mathbf{S}| \le 10\).
- Test Set 2 (phán quyết ẩn): \(1 \le |\mathbf{S}| \le 100\).
Đ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/25 | 40% |
| Test Set 2 | 15/25 | 60% |
Ví dụ
Ví dụ 1
Input
3
PEEL
AAAAAAAAAA
CODEJAMDAYOutput
Case #1: PEEEEL
Case #2: AAAAAAAAAA
Case #3: CCODDEEJAAMDAAYGiải thích
Trong bộ test mẫu số 1, dưới đây là tất cả các chuỗi có thể thu được, theo thứ tự bảng chữ cái: PEEEEL, PEEEELL, PEEEL, PEEELL, PEEL, PEELL, PPEEEEL, PPEEEELL, PPEEEL, PPEEELL, PPEEL và PPEELL.
Trong bộ test mẫu số 2, mọi chuỗi có thể thu được đều chỉ chứa các chữ A. Chuỗi ngắn nhất đứng đầu tiên theo thứ tự bảng chữ cái vì nó là tiền tố của tất cả các chuỗi còn lại.
Trong bộ test mẫu số 3, có \(1024\) chuỗi có thể được tạo ra từ CODEJAMDAY; trong số đó, CCODDEEJAAMDAAY là chuỗi nhỏ nhất theo thứ tự từ điển.
Nguồn
Google Code Jam 2022, Vòng 1A, bài Double or One Thing.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
