Google Code Jam 2012 - Round 1A

Cruise control (kiểm soát hành trình) là một hệ thống cho phép xe ô tô chạy ở tốc độ không đổi, trong khi người lái chỉ điều khiển vô lăng. Tất nhiên, người lái có thể tắt hệ thống kiểm soát hành trình để tránh va chạm.

Trong bài toán này, chúng ta sẽ xem xét một con đường một chiều có hai làn xe và \(N\) chiếc xe đang sử dụng hệ thống kiểm soát hành trình trên đường. Mỗi chiếc xe dài 5 mét và chạy với một tốc độ không đổi nào đó. Một chiếc xe có thể chuyển làn bất cứ lúc nào nếu việc đó không gây ra va chạm với xe khác (tiếp xúc nhau không được tính là va chạm). Giả sử việc chuyển làn diễn ra tức thời và chỉ đơn giản là khiến chiếc xe chuyển sang làn kia. Chúng ta quan tâm đến việc liệu có người lái nào cuối cùng sẽ phải tắt hệ thống kiểm soát hành trình để tránh va chạm hay không, hoặc liệu tất cả họ có thể lái xe mãi mãi (có thể chuyển làn, nhưng ở tốc độ không đổi) mà không xảy ra va chạm hay không. Lưu ý rằng mặc dù việc chuyển làn là tức thời, hai chiếc xe đang chạy song song không thể đổi chỗ cho nhau bằng cách chuyển làn cùng một lúc.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu bằng số \(N\). \(N\) dòng tiếp theo, mỗi dòng mô tả một chiếc xe duy nhất. Mỗi dòng chứa một ký tự \(C_i\) (biểu thị xe ban đầu ở làn trái hay làn phải), hai số nguyên mô tả tốc độ \(S_i\) của xe (tính bằng mét trên giây) và vị trí ban đầu \(P_i\) của xe (tính bằng mét), biểu thị khoảng cách giữa đuôi xe và một vạch cố định ngang qua đường. Tất cả các xe đều đang di chuyển ra xa vạch này và không có xe nào ở phía sau vạch.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là từ "Possible" (trong ngoặc kép chỉ để làm rõ), nếu các xe có thể lái ở tốc độ không đổi đã cho mãi mãi, hoặc số giây tối đa chúng có thể lái trước khi ai đó phải thay đổi tốc độ để tránh va chạm. Các câu trả lời chính xác trong khoảng sai số tuyệt đối hoặc tương đối \(10^{-5}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 30\).
• \(1 \le S_i \le 1000\).
• \(0 \le P_i \le 10000\).
• Mỗi ký tự \(C_i\) sẽ là L (biểu thị làn trái) hoặc R (biểu thị làn phải).
• Ban đầu, vị trí của các xe được sắp xếp sao cho chúng không va chạm, nghĩa là nếu hai xe \(i\) và \(j\) có cùng làn xuất phát ban đầu (\(C_i = C_j\)), thì \(|P_i - P_j| \ge 5\).

Phân nhóm

• Tập thử nghiệm 1 (Visible): \(1 \le N \le 6\).
• Tập thử nghiệm 2 (Hidden): \(1 \le N \le 50\).

Đ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.

Ví dụ

4
2
L 5 10
L 100 0
3
L 100 0
R 100 0
L 50 505
6
L 30 0
R 30 2
L 10 39
R 10 42
L 25 13
L 15 29
4
L 4 0
L 2 29
L 1 35
L 1 44

Case #1: Possible
Case #2: 10.0
Case #3: 1.4
Case #4: 12.0

Nguồn

Google Code Jam 2012, Vòng 1A, bài Cruise Control.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Ryan đang chơi Kingdom Rush, một trò chơi phòng thủ tháp (tower defense) dành cho một người chơi được phát triển bởi Ironhide Game Studio. Trong Kingdom Rush, người chơi kiếm được sao bằng cách hoàn thành các màn chơi theo cách được mô tả dưới đây. Có nhiều sao hơn giúp người chơi mạnh mẽ hơn; vì vậy, mặc dù Ryan có thể không hoàn thành được màn 2 ngay lập tức, anh ấy có thể hoàn thành nó sau khi kiếm được sao từ màn 1.

Trò chơi Kingdom Rush thực tế không hoạt động hoàn toàn giống như bài toán này. Việc đã từng chơi trò chơi này hay chưa không quan trọng để giải quyết bài toán.

Trong phiên bản Kingdom Rush của bài toán này, khi người chơi hoàn thành một màn chơi, người đó sẽ nhận được xếp hạng 1 sao hoặc xếp hạng 2 sao. Xếp hạng đó có thể cho phép người chơi kiếm được sao như sau:

• Nếu người chơi chưa bao giờ hoàn thành màn đó trước đây và hoàn thành nó với xếp hạng 1 sao, người chơi đó kiếm được 1 sao.
• Nếu người chơi chưa bao giờ hoàn thành màn đó trước đây và hoàn thành nó với xếp hạng 2 sao, người chơi đó kiếm được 2 sao.
• Nếu người chơi trước đó chỉ mới hoàn thành màn đó với xếp hạng 1 sao và lần này hoàn thành nó với xếp hạng 2 sao, người chơi kiếm thêm được 1 sao nữa.

Ngoài ra, không có cách nào khác để người chơi kiếm thêm sao.

Ryan có thể không hoàn thành được mọi màn chơi ngay lập tức. Đối với mỗi màn, trước khi có thể hoàn thành nó với xếp hạng 1 sao, anh ấy cần phải kiếm được một số lượng sao nhất định; và anh ấy sẽ cần một số lượng sao lớn hơn hoặc bằng thế để hoàn thành màn đó với xếp hạng 2 sao.

Ví dụ, giả sử có hai màn chơi:

• Màn 1 yêu cầu 0 sao để hoàn thành với xếp hạng 1 sao, và 1 sao để hoàn thành với xếp hạng 2 sao.
• Màn 2 yêu cầu 0 sao để hoàn thành với xếp hạng 1 sao, và 2 sao để hoàn thành với xếp hạng 2 sao.

Đây là một chuỗi các sự kiện có thể xảy ra với Ryan:

1. Ryan bắt đầu với 0 sao. Anh ấy có thể chọn hoàn thành màn 1 hoặc màn 2 với xếp hạng 1 sao. Anh ấy chọn hoàn thành màn 1 với xếp hạng 1 sao. Bây giờ anh ấy có 1 sao.
2. Bây giờ Ryan có thể hoàn thành màn 2 với xếp hạng 1 sao, hoặc màn 1 với xếp hạng 2 sao. Anh ấy chọn hoàn thành màn 1 với xếp hạng 2 sao. Bây giờ anh ấy có 2 sao.
3. Bây giờ Ryan có thể hoàn thành màn 2 với xếp hạng 2 sao. Anh ấy thực hiện điều đó, và bây giờ anh ấy có 4 sao.
4. Bây giờ anh ấy đã xong, đã hoàn thành tất cả các màn với xếp hạng 2 sao và kiếm được 4 sao (2 sao mỗi màn). Anh ấy đã hoàn thành các màn chơi tổng cộng 3 lần: màn 1 hai lần, và màn 2 một lần.

Ryan rất giỏi các trò chơi phòng thủ tháp, nhưng anh ấy cần sự giúp đỡ để phá đảo Kingdom Rush nhanh nhất có thể. Nhiệm vụ của bạn là tính toán xem anh ấy cần hoàn thành các màn chơi bao nhiêu lần để đạt được xếp hạng 2 sao ở mọi màn.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất N, cho biết có bao nhiêu màn chơi trong trò chơi. N dòng tiếp theo. Dòng thứ i chứa hai số nguyên \(a_i\) và \(b_i\): tương ứng là số sao cần thiết để đạt được xếp hạng một sao hoặc xếp hạng hai sao ở màn i.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lần tối thiểu Ryan phải hoàn thành các màn chơi để đạt được xếp hạng 2 sao ở mọi màn. Nếu Ryan không thể đạt được xếp hạng 2 sao ở mọi màn, y thay vào đó phải là chuỗi "Too Bad" (không có dấu ngoặc kép, nhưng viết hoa chính xác như vậy). Điều này cho thấy Ryan quá kém cỏi để có thể hoàn thành toàn bộ trò chơi Kingdom Rush.

Ràng buộc

• 1 ≤ T ≤ 100.
• 0 ≤ \(a_i\) ≤ \(b_i\) ≤ 2001.

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): 1 ≤ N ≤ 10.
• Tập kiểm tra 2 (Hidden Verdict): 1 ≤ N ≤ 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.

Ví dụ

4
2
0 1
0 2
3
2 2
0 0
4 4
1
1 1
5
0 5
0 1
1 1
4 7
5 6

Case #1: 3
Case #2: 3
Case #3: Too Bad
Case #4: 6

Kingdom Rush được tạo ra bởi Ironhide Game Studio. Ironhide Game Studio không xác nhận và không có liên quan đến Google Code Jam.

Nguồn

Google Code Jam 2012, Vòng 1A, bài Kingdom Rush.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Tôi có một mật khẩu rất dài, và đôi khi tôi gõ nhầm. Hiện tại tôi đã gõ được một phần mật khẩu, nhưng có thể tôi đã mắc lỗi. Cụ thể, tôi có thể đã nhấn sai phím khi gõ một hoặc nhiều ký tự trước đó. Cho biết xác suất tôi gõ đúng từng ký tự, tôi nên làm gì?

Tôi có ba lựa chọn:

1. Tiếp tục gõ phần còn lại của mật khẩu, sau đó nhấn "enter". Tôi biết mình sẽ gõ các ký tự còn lại một cách hoàn hảo. Nếu hóa ra một trong các ký tự trước đó bị sai, tôi sẽ phải gõ lại toàn bộ mật khẩu và nhấn "enter" lần nữa -- nhưng tôi biết mình sẽ gõ đúng ở lần thứ hai này.
2. Nhấn "backspace" một số lần nhất định, xóa (các) ký tự cuối cùng đã gõ, sau đó hoàn thành mật khẩu và nhấn "enter" như trong lựa chọn 1. Nếu một trong các ký tự tôi không xóa bị sai, tôi sẽ phải gõ lại toàn bộ và nhấn "enter", biết rằng tôi sẽ gõ đúng ở lần thứ hai.
3. Bỏ cuộc bằng cách nhấn "enter" ngay lập tức, gõ lại mật khẩu từ đầu và nhấn "enter" lần nữa. Tôi biết mình sẽ gõ đúng lần này.

Tôi muốn cực tiểu hóa số lần nhấn phím kỳ vọng cần thiết. Mỗi ký tự trong mật khẩu tốn 1 lần nhấn phím; mỗi lần "backspace" tốn 1 lần nhấn phím; nhấn "enter" để hoàn thành một lần thử hoặc để bỏ cuộc tốn 1 lần nhấn phím.

Lưu ý: Số lần nhấn phím "kỳ vọng" là số lần nhấn phím trung bình cần thiết nếu tình huống tương tự xảy ra rất nhiều lần. Xem ví dụ bên dưới.

Ví dụ

Giả sử mật khẩu của tôi là "guest" và tôi đã gõ xong hai ký tự đầu tiên, nhưng tôi có 40% khả năng mắc lỗi khi gõ mỗi ký tự đó. Khi đó có bốn trường hợp:

• Tôi đã gõ "gu" mà không có lỗi. Điều này xảy ra với xác suất \(0.6 \times 0.6 = 0.36\).
• Tôi đã gõ đúng chữ 'g' nhưng mắc lỗi khi gõ chữ 'u'. Khi đó tôi vẫn có hai chữ cái đã gõ, nhưng chữ thứ hai bị sai: "gX". (Ở đây, ký tự 'X' đại diện cho một chữ cái gõ sai.) Điều này xảy ra với xác suất \(0.6 \times 0.4 = 0.24\).
• Tôi đã gõ đúng chữ 'u' nhưng mắc lỗi khi gõ chữ 'g': "Xu". Điều này xảy ra với xác suất \(0.4 \times 0.6 = 0.24\).
• Tôi mắc lỗi khi gõ cả hai chữ cái, vì vậy tôi có hai chữ cái sai: "XX". Điều này xảy ra với xác suất \(0.4 \times 0.4 = 0.16\).

Tôi không biết mình thực sự đã mắc bao nhiêu lỗi, nhưng với bất kỳ chiến lược nào, tôi có thể tính toán số lần nhấn phím kỳ vọng cần thiết để sử dụng nó. Điều này được thể hiện trong bảng dưới đây:

Nếu tôi tiếp tục gõ, xác suất là \(0.36\) tôi sẽ cần \(4\) lần nhấn phím, và xác suất \(0.64\) tôi sẽ cần \(10\) lần nhấn phím. Nếu tôi lặp lại thử nghiệm nhiều lần, tôi sẽ sử dụng \(4\) lần nhấn phím trong \(36\%\) thời gian và \(10\) lần nhấn phím trong \(64\%\) thời gian còn lại, vì vậy số lần nhấn phím trung bình cần thiết sẽ là \(0.36 \times 4 + 0.64 \times 10 = 7.84\). Tuy nhiên, trong trường hợp này, tốt hơn là chỉ cần nhấn enter ngay lập tức, việc này yêu cầu \(7\) lần nhấn phím.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên, A và B. A là số ký tự tôi đã gõ và B là tổng số ký tự trong mật khẩu của tôi.

Tiếp theo là một dòng chứa A số thực: \(p_1, p_2, \dots, p_A\). \(p_i\) đại diện cho xác suất tôi gõ đúng chữ cái thứ \(i\) trong mật khẩu của mình. Các số thực này sẽ bao gồm các chữ số thập phân và tối đa một dấu chấm thập phân. Dấu chấm thập phân sẽ không bao giờ là ký tự đầu tiên hoặc cuối cùng trong một số.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lần nhấn phím bổ sung kỳ vọng tối thiểu mà tôi cần, không tính các chữ cái tôi đã gõ cho đến nay, và giả sử tôi chọn chiến lược tối ưu. y phải chính xác trong khoảng sai số tuyệt đối hoặc tương đối là \(10^{-6}\).

Ràng buộc

• \(1 \le T \le 20\).
• \(0 \le p_i \le 1\) với mọi \(i\).

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): \(1 \le A \le 3\); \(A < B \le 100\).
• Tập kiểm tra 2 (Hidden Verdict): \(1 \le A \le 99999\); \(A < B \le 100000\).

Đ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.

Ví dụ

3
2 5
0.6 0.6
1 20
1
3 4
1 0.9 0.1

Case #1: 7.000000
Case #2: 20.000000
Case #3: 4.500000

Nguồn

Google Code Jam 2012, Vòng 1A, bài Password Problem.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.