| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | Google Code Jam 2016 - Close Match | 33 | 1.0s | 1G |
| 2 | Google Code Jam 2016 - Getting the Digits | 23 | 1.0s | 1G |
| 3 | Google Code Jam 2016 - Technobabble | 44 | 1.0s | 1G |
Bạn đang dự khán trận đấu quan trọng nhất lịch sử thể thao: Oceania Coders gặp Eurasia Jammers trong chung kết thế giới Centrifugal Bumble-Puppy. Vì thiếu ngủ trong lúc mong chờ, bạn đã ngủ quên giữa trận!
Bảng điểm hiện hiển thị cả hai tỷ số, có thể có một hoặc nhiều số 0 ở đầu vì bảng dùng số chữ số cố định. Trong lúc bạn ngủ, những cú bóng mạnh làm hỏng một số đèn, nên một hoặc nhiều chữ số ở một hoặc cả hai tỷ số không còn hiển thị.
Bạn thấy trận đấu sít sao hấp dẫn hơn và muốn hình dung hai tỷ số gần nhau nhất có thể. Hãy điền mọi chữ số thiếu để tối thiểu hóa hiệu tuyệt đối giữa hai tỷ số. Nếu có nhiều cách cùng đạt hiệu nhỏ nhất, chọn cách làm tỷ số Coders nhỏ nhất. Nếu vẫn còn nhiều cách, chọn cách làm tỷ số Jammers nhỏ nhất.
Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng có hai chuỗi không rỗng \(C\) và \(J\) cùng độ dài, chỉ gồm chữ số thập phân và dấu ?, biểu diễn hai tỷ số đang thấy. Mỗi bộ test có ít nhất một dấu ?.
Với mỗi bộ test, in Case #x: c j, trong đó \(x\) bắt đầu từ 1; \(c\) và \(j\) lần lượt là \(C\) và \(J\) sau khi thay dấu ? bằng chữ số sao cho \(|c-j|\) nhỏ nhất. Nếu hòa, ưu tiên \(c\) nhỏ nhất, rồi \(j\) nhỏ nhất.
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/33 | 30,3% |
| Test Set 2 | 23/33 | 69,7% |
Ví dụ 1
4
1? 2?
?2? ??3
? ?
?5 ?0Case #1: 19 20
Case #2: 023 023
Case #3: 0 0
Case #4: 05 00Ở trường hợp #4, đáp án không thể là 15 10: cách đó tối thiểu hiệu tuyệt đối nhưng không tối thiểu tỷ số Coders. Cũng không thể là 05 10: cách đó tối thiểu cả hiệu và tỷ số Coders nhưng chưa tối thiểu tỷ số Jammers.
Google Code Jam 2016, Vòng 1B, bài Close Match.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Bạn vừa làm quen một người bạn mới tại hội nghị câu đố quốc tế và hỏi cách giữ liên lạc. Hôm sau, bạn thấy mảnh giấy sau được luồn dưới cửa phòng khách sạn:
“Xin chào, người bạn mới! Tôi đã thay mỗi chữ số trong số điện thoại bằng cách viết nó bằng chữ tiếng Anh in hoa (
ZERO,ONE,TWO,THREE,FOUR,FIVE,SIX,SEVEN,EIGHT,NINEtương ứng các chữ số từ 0 đến 9), rồi xáo trộn tất cả các chữ cái để tạo chuỗi \(S\). Bạn phải dùng \(S\) để tìm số điện thoại có bao nhiêu chữ số và chúng là gì; tôi chỉ tiết lộ rằng các chữ số trong số điện thoại ở thứ tự không giảm. Hãy gọi cho tôi... nếu bạn làm được!”
Bạn muốn gọi để nói rằng đây là cách đưa số điện thoại thật khó chịu, nhưng phải tìm được số thì mới gọi được. Số điện thoại là gì?
Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng chứa chuỗi \(S\) các chữ cái tiếng Anh in hoa.
Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là chuỗi chữ số của số điện thoại.
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 | 11/23 | 47,83% |
| Test Set 2 | 12/23 | 52,17% |
Ví dụ 1
4
OZONETOWER
WEIGHFOXTOURIST
OURNEONFOE
ETHERCase #1: 012
Case #2: 2468
Case #3: 114
Case #4: 3Google Code Jam 2016, Vòng 1B, bài Getting the Digits.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Mỗi năm, giáo sư của bạn dán một tờ đăng ký trống lên cửa phòng để sinh viên đăng ký tham dự một hội nghị nghiên cứu khoa học danh giá. Nếu muốn thuyết trình tại hội nghị, sinh viên chọn một chủ đề gồm hai từ chưa có trên tờ giấy rồi viết chủ đề đó vào. Khi hết hạn đăng ký, giáo sư nhờ một nghiên cứu sinh sắp xếp ngẫu nhiên các chủ đề để không thiên vị người đăng ký sớm hay muộn, rồi đưa danh sách cho bạn xem xét.
Đồ ăn nhẹ ở hội nghị rất ngon, nên một số sinh viên tìm cách giả mạo để được tham dự. Họ lấy từ thứ nhất của một chủ đề đã có trên tờ giấy và từ thứ hai của một chủ đề đã có trên tờ giấy, rồi ghép chúng theo đúng thứ tự đó thành một “chủ đề” mới, miễn là chủ đề mới chưa có trên tờ giấy. Vì giáo sư của bạn rất cởi mở, đôi khi mánh này thật sự thành công!
Những người giả mạo hoàn toàn thiếu sáng tạo và không thể tự nghĩ ra từ thứ nhất hay từ thứ hai mới; họ buộc phải dùng những từ đã có trên tờ giấy. Hơn nữa, họ không dùng một từ vốn xuất hiện ở vị trí thứ nhất làm từ thứ hai của mình, trừ khi từ đó cũng đã xuất hiện ở vị trí thứ hai trên tờ giấy; chiều ngược lại cũng tương tự.
Bạn có danh sách gồm toàn bộ \(N\) chủ đề đã nộp theo một thứ tự tùy ý, nhưng không biết thứ tự thực tế chúng được ghi lên tờ giấy. Số chủ đề lớn nhất có thể đã bị giả mạo là bao nhiêu?
Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), sau đó là \(N\) dòng. Mỗi dòng biểu diễn một chủ đề khác nhau và chứa hai chuỗi chữ cái tiếng Anh viết hoa: hai từ của chủ đề, theo đúng thứ tự.
Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số nguyên lớn nhất các chủ đề có thể đã bị giả mạo.
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 | 14/44 | 31,82% |
| Test Set 2 | 30/44 | 68,18% |
Ví dụ 1
3
3
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
3
CODE JAM
SPACE JAM
PEARL JAM
2
INTERGALACTIC PLANETARY
PLANETARY INTERGALACTICCase #1: 1
Case #2: 0
Case #3: 0Trong bộ test mẫu số 1, một khả năng là các chủ đề được thêm vào tờ giấy theo thứ tự sau:
QUAIL BEHAVIOR (thật)
HYDROCARBON COMBUSTION (thật)
QUAIL COMBUSTION (giả)
Không có kịch bản nào cho phép nhiều hơn một chủ đề là giả.
Trong bộ test mẫu số 2, mọi chủ đề đều phải là thật. Dù chúng được ghi theo thứ tự nào, không thời điểm nào ta có thể dùng các từ đã có để tạo ra một chủ đề mới chưa nằm trong danh sách.
Trong bộ test mẫu số 3, cả hai chủ đề đều không thể là giả. Chẳng hạn, nếu INTERGALACTIC PLANETARY là chủ đề đầu tiên và duy nhất đã được ghi, người giả mạo chỉ có thể dùng INTERGALACTIC làm từ thứ nhất và PLANETARY làm từ thứ hai. Chủ đề duy nhất họ tạo được là chính INTERGALACTIC PLANETARY, nhưng chủ đề đó bị cấm vì đã có trên tờ giấy. Do đó PLANETARY INTERGALACTIC cũng phải là chủ đề thật.
Google Code Jam 2016, Vòng 1B, bài Technobabble.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.