| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | Google Code Jam 2018 - A Whole New Word | 28 | 1.0s | 1G |
| 2 | Google Code Jam 2018 - Ant Stack | 43 | 1.0s | 1G |
| 3 | Google Code Jam 2018 - Lollipop Shop | 100 | 1.0s | 1G |
Vincent và Desta là bạn từ thuở nhỏ. Hôm nay, Vincent dùng các miếng chữ để cho Desta xem \(N\) từ phân biệt, mỗi từ dài \(L\) ký tự. Mỗi miếng mang một chữ cái tiếng Anh in hoa và một số từ 1 đến \(L\). Một từ được tạo bởi \(L\) miếng có số từ 1 đến \(L\) theo đúng thứ tự. Các từ của Vincent không nhất thiết là từ tiếng Anh có nghĩa.
Ví dụ, nếu \(N=3\), \(L=4\) và các từ là {CAKE, TORN, SHOW}, Vincent phải cho Desta xem các miếng sau:
C₁ A₂ K₃ E₄
T₁ O₂ R₃ N₄
S₁ H₂ O₃ W₄
Desta cho rằng tạo từ rất dễ và muốn tạo một từ mới tuân thủ quy tắc trên nhưng không trùng bất kỳ từ nào của Vincent. Desta không có miếng chữ riêng, nên phải dùng các miếng của Vincent.
Với ví dụ trên, Desta có thể tạo CORN, SAKE hoặc CHRE (từ của Desta cũng không cần có nghĩa):
C₁ O₂ R₃ N₄
S₁ A₂ K₃ E₄
C₁ H₂ R₃ E₄
Ba dòng trên độc lập; Desta chỉ cần tạo một từ mới. Tuy nhiên, cậu không thể tạo WAKE vì không có miếng chữ W mang số 1, và cũng không thể tạo COO vì từ đó sai độ dài.
Đôi khi không thể tạo từ mới. Nếu Vincent chỉ có một từ thì Desta không thể tạo gì khác. Hoặc nếu Vincent có {AA, AB, BA, BB}, mọi từ Desta ghép được đều đã có sẵn.
Hãy giúp Desta chọn một từ có thể ghép chỉ từ những miếng Vincent đã dùng, hoặc cho biết điều đó là bất khả thi.
Dòng đầu chứa số bộ test \(T\).
Mỗi bộ test bắt đầu bằng hai số nguyên \(N,L\): số từ của Vincent và độ dài mỗi từ. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa một chuỗi gồm \(L\) chữ cái tiếng Anh in hoa biểu diễn từ thứ \(i\).
Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là một từ hợp lệ Desta có thể chọn, hoặc - (một dấu gạch ngang duy nhất, mã ASCII 45) nếu không tồn tại từ hợp lệ. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nà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 | 11/28 | 39,29% |
| Test Set 2 | 17/28 | 60,71% |
Ví dụ 1
5
4 1
A
B
C
D
4 2
WW
AA
SS
DD
4 2
AA
AB
BA
BB
3 4
CAKE
TORN
SHOW
5 7
HELPIAM
TRAPPED
INSIDEA
CODEJAM
FACTORYCase #1: -
Case #2: WA
Case #3: -
Case #4: CORN
Case #5: HOLIDAYHai test mẫu cuối không xuất hiện trong Test Set 1.
Trong test mẫu 1, các từ duy nhất ghép được là A, B, C, D, nhưng tất cả đã nằm trong danh sách của Vincent. Trong test mẫu 2 có 12 từ mới khả dĩ, trong đó có WA. Test mẫu 3 là trường hợp {AA, AB, BA, BB} đã giải thích ở trên, nên không có từ mới. Test mẫu 4 cũng là ví dụ ở phần đề bài; SAKE là một đáp án khác. Với test mẫu 5, TRAPJAM cũng là một đáp án khác.
Google Code Jam 2018, Vòng 1C, bài A Whole New Word.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Scott có một trại kiến gồm \(N\) con. Mỗi con kiến có một chiều dài và cân nặng nhất định.
Hôm nay, để thử thách đàn kiến, Scott đặt thức ăn ở trên cao trong trại. Đàn kiến cố với tới bằng cách xếp thành một chồng thẳng đứng, mỗi con trong chồng trực tiếp đỡ con kế tiếp trên lưng. Như vậy, mỗi con phải chịu tổng cân nặng của tất cả kiến phía trên nó. Kiến của Scott rất khỏe so với kích thước: mỗi con mang được tối đa 6 lần cân nặng của chính nó. Chẳng hạn, một con nặng 8 miligam có thể mang hai con khác, mỗi con nặng 24 miligam! Mỗi con còn có chiều dài cơ thể; giá trị chiều dài cụ thể không quan trọng, chỉ biết tất cả chúng khác nhau.
Chồng kiến phải là một đường thẳng: trừ con trên cùng, mỗi con nằm trực tiếp dưới đúng một con; trừ con dưới cùng, mỗi con nằm trực tiếp trên đúng một con. Chiều dài phải giảm nghiêm ngặt từ đáy lên đỉnh, để mỗi con mới tham gia có thể bò lên trên cùng. Với mỗi con, tổng cân nặng của mọi con phía trên không được vượt quá 6 lần cân nặng của nó.
Nhiều nhất bao nhiêu con kiến có thể tạo thành một chồng như vậy?
Dòng đầu chứa số bộ test \(T\).
Mỗi bộ test bắt đầu bằng một dòng chứa \(N\), số kiến trong đàn. Dòng tiếp theo chứa \(N\) số nguyên \(W_1,W_2,\ldots,W_N\), trong đó \(W_i\) là cân nặng tính bằng miligam của con thứ \(i\). Các con được liệt kê theo thứ tự chiều dài tăng nghiêm ngặt. Đề không cho giá trị chiều dài thực; chỉ thứ tự này là quan trọng.
Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là số kiến lớn nhất có thể tạo thành một chồng tuân thủ các quy tắc trên.
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 | 16/43 | 37,21% |
| Test Set 2 | 27/43 | 62,79% |
Ví dụ 1
3
2
9 1
3
8 4 100
9
10 10 10 10 10 10 10 10 100Case #1: 1
Case #2: 3
Case #3: 8Trong test mẫu 1, con thứ nhất nặng 9 mg; con thứ hai nặng 1 mg và dài hơn. Con thứ nhất đủ khỏe để đỡ con thứ hai, vì mang được \(9\times6\) mg, nhưng không thể nằm dưới vì con thứ hai dài hơn. Con thứ hai chỉ mang được \(1\times6\) mg, không đủ đỡ con thứ nhất nặng 9 mg. Do đó chỉ có thể tạo một “chồng” gồm một con.
Trong test mẫu 2, cả ba con đều xếp được: con thứ ba đỡ con thứ hai, và con thứ hai đỡ con thứ nhất.
Trong test mẫu 3, phương án tối ưu đặt con thứ chín ở đáy rồi đặt bảy con khác phía trên.
Google Code Jam 2018, Vòng 1C, bài Ant Stack.
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 sở hữu một cửa hàng kẹo mút. Đầu ngày, bạn làm \(N\) cây kẹo, mỗi cây có một hương vị riêng biệt, chẳng hạn việt quất, anh đào hoặc chanh. Trong ngày có \(N\) khách lần lượt vào cửa hàng. Mỗi khách đưa danh sách những vị họ thích. Bạn có thể bán cho họ một cây thuộc bất kỳ vị nào trong danh sách, miễn là cây vị đó chưa được bán cho người trước, vì mỗi vị chỉ có một cây. Nếu mọi vị họ thích đều đã hết, bạn không thể bán và họ thất vọng rời đi.
Bạn chỉ biết sở thích của khách khi họ tới. Mỗi khách thích hay không thích từng vị một cách ngẫu nhiên, độc lập với việc họ thích vị khác và với sở thích của mọi người khác. Tuy nhiên, nghiên cứu thị trường cho thấy xác suất được thích của các vị có thể khác nhau: chẳng hạn một khách bất kỳ có thể thích chanh với xác suất 10%, nhưng thích anh đào với xác suất 1%. Xác suất của mỗi vị được chọn độc lập và đều trên đoạn \([0.005,0.1]\).
Bạn muốn bán cho càng nhiều khách càng tốt. Vì không biết trước sở thích tương lai, bạn không phải lúc nào cũng quyết định tối ưu: có thể bán một vị cho khách hiện tại rồi về sau ước rằng mình đã bán vị khác.
Giả sử biết trước sở thích của tất cả khách và có thể lập kế hoạch, gọi \(M\) là số kẹo lớn nhất có thể bán. Dù không được biết trước, chương trình của bạn phải bán ít nhất 90% của \(M\) trong mỗi bộ test.
Đây là bài tương tác: khái niệm input và output khác bài thông thường. Chương trình tương tác với một tiến trình riêng vừa cung cấp thông tin vừa đánh giá câu trả lời. Mọi thông tin đi vào qua đầu vào chuẩn; mọi nội dung cần giao tiếp phải gửi qua đầu ra chuẩn.
Nhiều ngôn ngữ mặc định đệm output, vì vậy phải bảo đảm dữ liệu thực sự được gửi đi — chẳng hạn flush bộ đệm — trước khi chặn để chờ phản hồi. Mọi thứ ghi ra lỗi chuẩn bị bỏ qua, nhưng vẫn có thể tiêu tốn bộ nhớ, nên không được ghi tràn lan.
Mọi lựa chọn bán kẹo được gửi tới judge qua đầu ra chuẩn theo giao thức dưới đây. Mỗi câu trả lời phải được flush trước khi chương trình chờ dữ liệu tiếp theo.
Ban đầu đọc một dòng chứa số nguyên \(T\), số bộ test, rồi xử lý lần lượt \(T\) bộ.
Ở đầu mỗi bộ test, đọc một dòng chứa \(N\), vừa là số cây kẹo vừa là số khách. Với từng khách, đọc một dòng các số nguyên cách nhau bằng dấu cách. Số đầu tiên là \(D\), số vị khách đó thích; tiếp theo là \(D\) ID vị theo thứ tự tăng nghiêm ngặt. ID vị nằm trong \([0,N-1]\) và là duy nhất. \(D\) có thể bằng 0 đối với một số hoặc tất cả khách.
Ngay sau mỗi dòng đó, phải ghi một dòng chứa ID của một trong \(D\) vị sẽ bán cho khách, hoặc -1 nếu không bán. Sau khi ghi dòng thứ \(N\) của bộ test, nếu đó là bộ cuối thì kết thúc; nếu không thì bắt đầu đọc bộ tiếp theo.
Nếu chương trình làm sai — chẳng hạn bán lại một vị đã bán, bán vị khách không thích, dùng sai định dạng hoặc in giá trị ngoài miền — judge gửi -1 vào input và không gửi gì thêm. Nếu chương trình vẫn chờ judge sau khi nhận -1, nó sẽ hết thời gian. Chương trình có trách nhiệm thoát kịp thời để nhận kết quả phù hợp thay vì TLE. Không bán đủ kẹo trong một bộ test không khiến judge gửi -1.
Không gửi thêm thông tin sau khi xử lý xong tất cả bộ test; nếu tiếp tục in sau bộ cuối, kết quả là Wrong Answer.
Ở đầu mỗi bộ test, judge xác định toàn bộ sở thích khách hàng bằng một danh sách ẩn các xác suất \(P_i\in[0.005,0.1]\), mỗi vị một xác suất. Mỗi khách thích vị \(i\) với xác suất \(P_i\); với một \(i\) cố định, các biến ngẫu nhiên cho biết khách \(j\) có thích vị \(i\) hay không là độc lập và cùng phân phối. Toàn bộ sở thích được cố định trong suốt bộ test và không bị sửa để phản ứng với lựa chọn của chương trình.
Các giá trị \(T,N\) trong ví dụ nhỏ hơn dữ liệu thật; công cụ kiểm thử cục bộ cũng dùng các trường hợp nhỏ hơn.
Ví dụ tương tác
t = readline_int() // reads 10 into t
n = readline_int() // reads 4 into n (four customers & flavors)
prefs = readline_int_list() // reads 1 2 (customer only likes flavor 2)
printline 2 to stdout // sells this customer flavor 2
flush stdout
prefs = readline_int_list() // reads 0 (customer likes nothing)
printline -1 to stdout // no flavor to sell to the customer!
flush stdout
prefs = readline_int_list() // reads 1 2 (customer only likes flavor 2)
printline -1 to stdout // already used flavor 2, so no flavor to sell
flush stdout
prefs = readline_int_list() // reads 2 1 3 (customer likes 1 and 3)
printline 3 to stdout // note: we could have also sold flavor 1
flush stdout
n = readline_int() // (start of case 2) reads 1
prefs = readline_int_list() // reads 1 0
printline -1 to stdout // non-optimal but legal choice
flush stdout
n = readline_int() // (start of case 3) reads 5
prefs = readline_int_list() // reads 2 1 3
printline 1 to stdout
flush stdout
prefs = readline_int_list() // reads 2 1 2
printline 1 to stdout // error -- tried to give same flavor twice!
flush stdout
prefs = readline_int_list() // reads -1 (judge has given up on us)
exit // exits to avoid an ambiguous TLE error
Trong bộ test đầu, chương trình bán được tổng cộng hai cây. Không thể bán nhiều hơn hai, nên số bán được chắc chắn đạt ít nhất 90% tối ưu.
Trong bộ test thứ hai, để minh họa, chương trình chọn không bán dù có thể bán. Nó bán 0 thay vì tối ưu 1, nên không đạt Test Set; tuy nhiên, việc không đạt tỷ lệ không khiến judge ngừng gửi input.
Trong bộ test thứ ba, chương trình cố tình phạm lỗi khiến judge ngừng gửi input. Chương trình nhận ra điều đó và kết thúc; người dùng nhận kết quả Wrong Answer.
Có thể dùng công cụ kiểm thử cục bộ chính thức trên máy hoặc nền tảng. Khi chạy cục bộ, cần chạy công cụ song song với chương trình, có thể dùng interactive runner. Hướng dẫn nằm trong phần chú thích của tệp; bạn được khuyến khích bổ sung test riêng.
Lưu ý
Công cụ chỉ mô phỏng hệ thống chấm, không phải judge thật và có thể hành xử khác. Việc qua công cụ không bảo đảm qua judge thật. Nếu chương trình qua công cụ nhưng trượt judge thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm đang dùng cùng trình biên dịch với hệ thống chấm.
Google Code Jam 2018, Vòng 1C, bài Lollipop Shop.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.