Google Code Jam 2012 - Round 1C

Bạn sở hữu một nhà máy với hai dây chuyền lắp ráp. Dây chuyền thứ nhất sản xuất các loại hộp, và dây chuyền thứ hai sản xuất các loại đồ chơi để đặt vào những chiếc hộp đó. Mỗi loại hộp đi kèm với một loại đồ chơi tương ứng và ngược lại.

Ban đầu, bạn lấy một chiếc hộp từ dây chuyền thứ nhất và một món đồ chơi từ dây chuyền thứ hai. Sau đó, bạn có một vài lựa chọn:

• Bạn luôn có thể bỏ chiếc hộp đi và lấy chiếc hộp tiếp theo.
• Bạn luôn có thể bỏ món đồ chơi đi và lấy món đồ chơi tiếp theo.
• Nếu hộp và đồ chơi cùng loại, bạn có thể đặt đồ chơi vào hộp và gửi sản phẩm hoàn thiện đến khách hàng.

Bạn luôn lấy hộp theo đúng thứ tự mà chúng được tạo ra, và tương tự đối với đồ chơi. Bạn biết trước thứ tự các loại hộp và đồ chơi sẽ được sản xuất, và bạn muốn lập kế hoạch để gửi được nhiều đồ chơi đã đóng hộp nhất có thể cho khách hàng.

Cảnh báo: Hai dây chuyền lắp ráp tạo ra rất nhiều hộp và đồ chơi. Tuy nhiên, chúng có xu hướng tạo ra cùng một loại sản phẩm trong một khoảng thời gian dài trước khi chuyển sang loại khác.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. Tiếp theo là T bộ thử nghiệm.

Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa hai số nguyên N và M. Tiếp theo là một dòng chứa \(2 \times N\) số nguyên a₁, A₁, a₂, A₂, ..., aₙ, Aₙ, và một dòng khác chứa \(2 \times M\) số nguyên b₁, B₁, b₂, B₂, ..., bₘ, Bₘ.

Điều này có nghĩa là dây chuyền thứ nhất sẽ tạo ra a₁ chiếc hộp loại A₁, sau đó là a₂ chiếc hộp loại A₂, v.v., cho đến khi kết thúc với aₙ chiếc hộp loại Aₙ. Tương tự, dây chuyền thứ hai sẽ tạo ra b₁ món đồ chơi loại B₁, tiếp theo là b₂ món đồ chơi loại B₂, v.v., cho đến khi kết thúc với bₘ món đồ chơi loại Bₘ.

Một món đồ chơi có thể được khớp với một chiếc hộp khi và chỉ khi chúng có cùng số hiệu loại.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy in ra 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à số lượng đồ chơi đóng hộp tối đa mà bạn có thể gửi cho khách hàng.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le a_i, b_i \le 10^{16}\).
• \(1 \le A_i, B_i \le 100\).

Phân nhóm

• Tập thử nghiệm 1 (Visible): \(1 \le N \le 3, 1 \le M \le 100\).
• Tập thử nghiệm 2 (Hidden): \(1 \le N, M \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.

Ví dụ

4
3 3
10 1 20 2 25 3
10 2 30 3 20 1
3 5
10 1 6 2 10 1
5 1 3 2 10 1 3 2 5 1
3 5
10 1 6 2 10 1
5 1 6 2 10 1 6 2 5 1
1 1
5000000 10
5000000 100

Case #1: 35
Case #2: 20
Case #3: 21
Case #4: 0

Nguồn

Google Code Jam 2012, Vòng 1C, bài Box Factory.

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 được yêu cầu giúp chẩn đoán các sơ đồ lớp để xác định các trường hợp kế thừa hình thoi (diamond inheritance). Sơ đồ lớp ví dụ sau đây minh họa tính chất của kế thừa hình thoi. Có bốn lớp: A, B, C và D. Một mũi tên trỏ từ X đến Y cho biết lớp X kế thừa từ lớp Y.

Trong sơ đồ lớp này, D kế thừa từ cả B và C, B kế thừa từ A, và C cũng kế thừa từ A. Một đường đi kế thừa từ X đến Y được định nghĩa là một chuỗi các lớp X, \(C_1, C_2, C_3, \dots, C_n\), Y trong đó X kế thừa từ \(C_1\), \(C_i\) kế thừa từ \(C_{i+1}\) với \(1 \le i \le n-1\), và \(C_n\) kế thừa từ Y. Có hai đường đi kế thừa từ D đến A trong ví dụ trên. Đường đi thứ nhất là D, B, A và đường đi thứ hai là D, C, A.

Một sơ đồ lớp được cho là chứa kế thừa hình thoi nếu tồn tại một cặp lớp X và Y sao cho có ít nhất hai đường đi kế thừa khác nhau từ X đến Y. Sơ đồ lớp ở trên là một ví dụ điển hình về kế thừa hình thoi. Nhiệm vụ của bạn là xác định xem một sơ đồ lớp cho trước có chứa kế thừa hình thoi hay không.

Dữ liệu vào

Dòng đầu tiên của dữ liệ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ộ mô tả một sơ đồ lớp. Dòng đầu tiên của mỗi bộ thử nghiệm cho biết số lượng lớp trong sơ đồ này, \(N\). Các lớp được đánh số từ 1 đến \(N\). \(N\) dòng tiếp theo. Dòng thứ \(i\) bắt đầu bằng một số nguyên không âm \(M_i\) cho biết số lượng lớp mà lớp \(i\) kế thừa trực tiếp. Tiếp theo là \(M_i\) số nguyên dương phân biệt, mỗi số từ 1 đến \(N\) đại diện cho các lớp đó. Bạn có thể giả định rằng:

• Nếu có một đường đi kế thừa từ X đến Y thì không có đường đi kế thừa từ Y đến X.
• Một lớp sẽ không bao giờ kế thừa từ chính nó.

Dữ liệu ra

Với mỗi sơ đồ, 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à "Yes" nếu sơ đồ lớp chứa kế thừa hình thoi, ngược lại là "No".

Ràng buộc

• \(1 \le T \le 50\).
• \(0 \le M_i \le 10\).

Phân nhóm

• Test set 1 (Visible Verdict): \(1 \le N \le 50\).
• Test set 2 (Hidden Verdict): \(1 \le N \le 1,000\).

Đ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
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0

Case #1: No
Case #2: Yes
Case #3: Yes

Nguồn

Google Code Jam 2012, Vòng 1C, bài Diamond Inheritance.

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

Chiếc xe của bạn đã hết xăng, và bạn muốn về nhà nhanh nhất có thể! May mắn thay, nhà của bạn nằm ở chân đồi và bạn (cùng chiếc xe) đang ở trên đỉnh đồi. Không may là có một chiếc xe khác đang ở phía trước bạn, và bạn không thể vượt qua nó. May mắn thay, phanh của bạn vẫn hoạt động và chúng rất mạnh mẽ.

Bạn bắt đầu tại đỉnh đồi với vận tốc \(0\) m/s tại thời điểm \(0\) giây. Trọng lực kéo xe của bạn xuống đồi với một gia tốc không đổi. Tại bất kỳ thời điểm nào, bạn có thể sử dụng phanh để giảm tốc độ, hoặc tạm thời giảm gia tốc của mình đi bất kỳ lượng nào.

Bạn có thể về nhà nhanh nhất là bao lâu nếu bạn sử dụng phanh theo cách tối ưu nhất?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Dòng đầu tiên của mỗi bộ thử nghiệm chứa ba số cách nhau bởi dấu cách: một số thực \(D\), khoảng cách tính bằng mét đến nhà bạn ở chân đồi; và hai số nguyên, \(N\) và \(A\). Khoảng cách \(D\) sẽ được cho với chính xác 6 chữ số thập phân.

\(N\) dòng tiếp theo, mỗi dòng chứa hai số thực cách nhau bởi dấu cách: thời điểm \(t_i\) tính bằng giây, và vị trí \(x_i\) tính bằng mét. Các giá trị \(t_i\) và \(x_i\) sẽ được cho với chính xác 6 chữ số thập phân.

Một dòng tiếp theo chứa \(A\) số thực cách nhau bởi dấu cách \(a_i\), là các gia tốc tính bằng \(m/s^2\). Các gia tốc sẽ được cho với chính xác 2 chữ số thập phân.

Vị trí của chiếc xe kia được xác định bởi các cặp \((t_i, x_i)\). Vị trí của chiếc xe đó tại thời điểm \(t_i\) giây là \(x_i\) mét tính từ đỉnh đồi (tức là vị trí ban đầu của bạn). Chiếc xe đó di chuyển với vận tốc không đổi giữa thời điểm \(t_i\) và \(t_{i+1}\). Các vị trí và thời gian đều được cho theo thứ tự tăng dần, với \(t_0=0\).

Ví dụ, nếu \(t_5=10, x_5=20, t_6=20, x_6=40\), thì \(10\) giây sau khi bắt đầu, chiếc xe kia cách đỉnh đồi \(20\) mét; \(15\) giây sau khi bắt đầu, chiếc xe kia cách đỉnh đồi \(30\) mét; và \(20\) giây sau khi bắt đầu, chiếc xe kia cách đỉnh đồi \(40\) mét.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, in ra một dòng chứa "Case #c:", trong đó c là số thứ tự bộ thử nghiệm (bắt đầu từ 1). Sau đó in ra \(A\) dòng, dòng thứ \(i\) chứa số giây tối thiểu để bạn về đến nhà nếu gia tốc xuống đồi do trọng lực của bạn là \(a_i\), và bạn sử dụng phanh theo cách tối ưu nhất. Các câu trả lời trong phạm vi sai số tuyệt đối hoặc tương đối \(10^{-6}\) so với đáp án đúng sẽ được chấp nhận. Không nên có dòng trống trong đầu ra.

Ghi chú

• Vị trí và Gia tốc: Một vật với gia tốc không đổi \(a\) \(m/s^2\) và vận tốc bắt đầu \(v_0\) \(m/s\) sẽ di chuyển một quãng đường \(v_0 \cdot t + 0.5 \cdot a \cdot t^2\) sau \(t\) giây.
• Khoảng cách trên dốc: Tất cả các khoảng cách và gia tốc được cho đối với đường thẳng xuống đồi. Chúng không phải là, ví dụ, khoảng cách nằm ngang; vì vậy nếu xe của bạn đang tăng tốc với \(2\) \(m/s^2\) với vận tốc ban đầu \(0\) \(m/s\), và chiếc xe kia đang dừng ở \(x=1\), sẽ mất đúng \(1\) giây để bắt kịp chiếc xe kia.
• Chiếc xe kia: Bạn không bao giờ được vượt qua chiếc xe kia, nghĩa là tại không có thời điểm nào khoảng cách xuống đồi của bạn lớn hơn khoảng cách của chiếc xe kia. Nó có thể bằng nhau. Các xe nên được coi là các chất điểm.
• Giá trị đầu ra: Bạn có thể in bao nhiêu chữ số thập phân tùy thích. Chúng tôi sẽ đọc và so sánh câu trả lời của bạn với đáp án của chúng tôi bằng ngưỡng sai số \(10^{-6}\). Vì vậy \(25, 25.0\) và \(25.000000\) là giống nhau. Các chữ số \(0\) vô nghĩa sau dấu phẩy thập phân không quan trọng.

Ràng buộc

• \(1 \le T \le 20\).
• \(1.0 \le D \le 10^4\).
• \(1.0 \le a_i \le 9.81\).
• \(0.0 \le t_i \le 10^5\).
• \(0.0 \le x_i \le 10^5\).
• \(t_i < t_{i+1}\).
• \(x_i < x_{i+1}\).
• \(t_0 = 0\).
• \(x_{N-1} \ge D\).

Phân nhóm

• Test set 1 (Visible Verdict):

  • \(1 \le N \le 2\).
  • \(1 \le A \le 10\).

  • Test set 2 (Hidden Verdict):

  • \(1 \le N \le 2000\).

  • \(1 \le A \le 250\).

Đ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
1000.000000 2 3
0.000000 20.500000
25.000000 1000.000000
1.00 5.00 9.81
50.000000 2 2
0.000000 0.000000
100000.000000 100.000000
1.00 1.01
10000.000000 3 1
0.000000 0.000000
10000.000000 0.100000
10000.100000 100000.000000
1.00

Case #1:
44.7213595
25.000000
25.0
Case #2:
50000.0
50000.0
Case #3:
10140.974143

Nguồn

Google Code Jam 2012, Vòng 1C, bài Out of Gas.

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