| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | Google Code Jam 2015 - Counter Culture | 25 | 1.0s | 1G |
| 2 | Google Code Jam 2015 - Hiking Deer | 48 | 10.0s | 1G |
| 3 | Google Code Jam 2015 - Noisy Neighbors | 27 | 1.0s | 1G |
Trong cuộc thi biểu diễn thơ đếm số, một người biểu diễn cầm micro, chọn một số \(N\) rồi đếm thành tiếng từ 1 tới \(N\). Cụ thể, cô bắt đầu bằng cách đọc 1, sau đó liên tục đọc số lớn hơn số vừa đọc đúng 1 đơn vị và dừng lại sau khi đọc \(N\).
Đến lượt bạn biểu diễn, nhưng bạn thấy quá trình này nhàm chán và muốn thêm một biến tấu để tăng tốc: đôi khi, thay vì cộng 1 vào số trước đó, bạn có thể đảo thứ tự các chữ số của số đó, đồng thời bỏ mọi số 0 ở đầu được tạo ra. Ví dụ, sau khi đọc 16, số tiếp theo có thể là 17 hoặc 61; sau khi đọc 2300, số tiếp theo có thể là 2301 hoặc 32. Bạn có thể đảo số bao nhiêu lần tùy ý, kể cả không lần nào, trong một màn biểu diễn.
Số đầu tiên bạn đọc phải là 1. Số lượng số ít nhất bạn phải đọc để đạt tới \(N\) là bao nhiêu? Cả 1 và \(N\) đều được tính vào tổng này. Nếu đọc cùng một số nhiều lần, mỗi lần đọc đều được tính riêng.
Dòng đầu tiên chứa số bộ test \(T\). Mỗi trong \(T\) dòng tiếp theo chứa một số nguyên \(N\), là số bạn phải đạt tới.
Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số lượng số ít nhất bạn cần đọc.
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/25 | 44% |
| Test Set 2 | 14/25 | 56% |
Ví dụ 1
3
1
19
23Case #1: 1
Case #2: 19
Case #3: 15Trong test 2, đảo số không giúp ích và chiến lược tối ưu là chỉ đếm tăng dần tới 19.\n\n Trong test 3, chiến lược tối ưu là đếm tới 12, đảo thành 21 rồi tiếp tục đếm tới 23. Cụ thể, các số được đọc là 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23.
Google Code Jam 2015, Vòng 1B, bài Counter Culture.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Herbert Hooves, chú hươu, sắp đi bộ đường dài: đi đúng một vòng theo chiều kim đồng hồ quanh con đường tròn yêu thích, xuất phát ở góc 0 độ. Herbert kiểm soát tốc độ hoàn hảo; tại mọi thời điểm, tốc độ có thể là bất kỳ giá trị không âm nào (không nhất thiết nguyên), và chú có thể đổi tốc độ tức thời bất cứ lúc nào. Khi Herbert trở lại điểm xuất phát, chuyến đi kết thúc.
Con đường cũng có những người đi bộ, tất cả đều đi theo chiều kim đồng hồ. Mỗi người có một vị trí xuất phát và di chuyển với tốc độ không đổi của riêng mình. Họ cứ đi hết vòng này đến vòng khác mãi mãi.
Herbert rất nhút nhát và sợ con người. Một lần gặp xảy ra mỗi khi Herbert và một người đi bộ ở chính xác cùng một vị trí tại cùng một thời điểm. Hãy coi Herbert và các người đi bộ là những điểm trên chu vi đường tròn.
Herbert có thể gặp cùng một người nhiều lần riêng biệt. Nếu gặp nhiều người cùng một thời điểm thì mỗi người được tính là một lần gặp riêng. Lần gặp xảy ra đúng vào thời điểm Herbert kết thúc chuyến đi vẫn được tính.
Nếu Herbert gặp một người rồi đổi tốc độ cho đúng bằng tốc độ của người đó và đi sát cùng họ, chú sẽ có vô hạn lần gặp! Dĩ nhiên, Herbert tuyệt đối không được làm như vậy.
Các lần gặp không làm thay đổi hành vi của người đi bộ, và khi những người đi bộ gặp nhau thì không có gì xảy ra.
Herbert biết vị trí xuất phát và tốc độ của từng người. Số lần gặp người đi bộ ít nhất mà chú có thể đạt được là bao nhiêu?
Thông thường, một bài Google Code Jam có 1 bộ dữ liệu Nhỏ và 1 bộ dữ liệu Lớn. Bài này có 2 bộ Nhỏ và 1 bộ Lớn. Bạn phải giải bộ Nhỏ thứ nhất trước khi được thử bộ Nhỏ thứ hai; như thường lệ, bạn có thể thử lại các bộ Nhỏ (chịu phạt thời gian). Sau khi giải cả hai bộ Nhỏ, bạn mới có thể tải bộ Lớn; như thường lệ, bạn chỉ có một lần nộp bộ Lớn.
Dòng đầu 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 mô tả một nhóm người đi bộ cùng xuất phát tại một vị trí trên đường.
Dòng thứ \(i\) trong số đó chứa ba số nguyên cách nhau bởi dấu cách: vị trí xuất phát \(D_i\) (tức là cách điểm xuất phát của hươu \(D_i/360\) vòng), số người \(H_i\) trong nhóm, và \(M_i\), số phút người nhanh nhất nhóm cần để hoàn thành mỗi vòng. Những người còn lại trong nhóm lần lượt hoàn thành một vòng trong \(M_i+1,M_i+2,\ldots,M_i+H_i-1\) phút.
Ví dụ, dòng
180 3 4
nghĩa là ba người xuất phát ở vị trí cách điểm xuất phát của hươu nửa vòng, và họ lần lượt mất 4, 5, 6 phút để hoàn thành một vòng.
Herbert luôn xuất phát tại vị trí 0, và không nhóm nào xuất phát tại đó. Nhiều nhóm có thể xuất phát cùng một vị trí, nhưng không có hai người nào vừa cùng vị trí xuất phát vừa cùng tốc độ.
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) và \(y\) là số lần gặp ít nhất Herbert có thể có.
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 | 13/48 | 27,09% |
| Test Set 2 | 16/48 | 33,33% |
| Test Set 3 | 19/48 | 39,58% |
Ví dụ 1
```sample
3
4
1 1 12
359 1 12
2 1 12
358 1 12
2
180 1 100000
180 1 1
1
180 2 1
???+ success "Output"
```sample
Case #1: 0
Case #2: 1
Case #3: 0
??? "Giải thích"
Trong Case #1, tất cả người đi bộ tình cờ đi cùng tốc độ. Một cách để Herbert không gặp ai là đi đúng bằng tốc độ của họ.
Trong Case #2, người thứ hai nhanh hơn người thứ nhất rất nhiều. Nếu Herbert đi đủ chậm để không vượt người thứ nhất, chú sẽ gặp người thứ hai nhanh nhẹn nhiều lần. Một chiến lược tối ưu là đi đúng bằng tốc độ người thứ hai, gặp người thứ nhất một lần và không bao giờ gặp người thứ hai.
Trong Case #3, hai người xuất phát cùng vị trí nhưng một người nhanh gấp đôi người kia. Một chiến lược tối ưu là Herbert lập tức đuổi kịp người chậm hơn mà không vượt, đi ngay phía sau cho tới khi người đó đi qua điểm xuất phát của hươu, rồi nhanh chóng kết thúc trước khi người nhanh hơn bắt kịp Herbert.
Google Code Jam 2015, Vòng 1B, bài Hiking Deer.
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 là chủ một tòa nhà gồm các căn hộ xếp thành lưới \(R\times C\); mỗi căn hộ là một ô vuông đơn vị có bốn bức tường. Bạn muốn cho thuê \(N\) căn, mỗi căn đúng một người thuê, và để trống các căn còn lại.
Đáng tiếc, tất cả người thuê tiềm năng đều ồn ào. Mỗi khi hai căn hộ có người ở chung một bức tường (không chỉ chạm nhau ở góc), tòa nhà nhận thêm một điểm bất hạnh. Chẳng hạn, một tòa nhà \(2\times2\) có người ở mọi căn có bốn bức tường được hai người hàng xóm dùng chung, nên mức bất hạnh là 4.
Nếu bố trí tối ưu \(N\) người thuê, mức bất hạnh nhỏ nhất của tòa nhà là bao nhiêu?
Dòng đầu chứa số bộ test \(T\). Mỗi bộ test là một dòng gồm ba số nguyên cách nhau bởi dấu cách: \(R\), \(C\), và \(N\).
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) và \(y\) là mức bất hạnh nhỏ nhất có thể của tòa nhà.
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 | 12/27 | 44,44% |
| Test Set 2 | 15/27 | 55,56% |
Ví dụ 1
```sample
4
2 3 6
4 1 2
3 3 8
5 2 0
???+ success "Output"
```sample
Case #1: 7
Case #2: 0
Case #3: 8
Case #4: 0
??? "Giải thích"
Trong Case #1, mọi căn đều có người ở và cả bảy bức tường bên trong đều có người thuê ở hai phía.
Trong Case #2, có nhiều cách đặt hai người sao cho họ không chung tường. Một cách được minh họa bên dưới.
Trong Case #3, chiến lược tối ưu là đặt tám người thành một vòng, để trống căn hộ ở giữa.
Sau đây là hình minh họa cho ba test mẫu đầu. Mỗi bức tường đỏ làm tăng mức bất hạnh thêm một điểm.
https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_ec097aa9.png
Google Code Jam 2015, Vòng 1B, bài Noisy Neighbors.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.