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?

Cách giải bài này

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ữ liệu vào

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 độ.

Dữ liệu ra

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

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le D_i \le 359\).
• \(1 \le N \le 1000\).
• \(1 \le H_i\).
• \(1 \le M_i \le 10^9\). (Cận này chỉ giới hạn thời gian hoàn thành một vòng của người nhanh nhất trong mỗi nhóm; những người chậm hơn sẽ mất nhiều thời gian hơn.)

Phân nhóm

• Test Set 1 (Nhỏ 1): Tổng số người đi bộ trong mỗi bộ test không vượt quá 2.
• Test Set 2 (Nhỏ 2): Tổng số người đi bộ trong mỗi bộ test không vượt quá 10.
• Test Set 3 (Lớn): Tổng số người đi bộ trong mỗi bộ test không vượt quá 500000.

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

Nguồn

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.