1. Google Code Jam 2021 - Broken Clock
Emmett tìm thấy một chiếc đồng hồ cũ trên gác mái. Đồng hồ là hình tròn với ba kim gắn ở tâm, quay đều theo chiều kim đồng hồ: kim giờ, kim phút và kim giây. Lúc nửa đêm, cả ba chỉ thẳng lên. Kim giờ quay một vòng trong \(12\) giờ, kim phút trong \(1\) giờ, kim giây trong \(1\) phút. Một giờ bằng \(60\) phút, một phút bằng \(60\) giây, một giây bằng \(10^9\) nanosecond.
Ví dụ, đồng hồ dưới đây chỉ đúng \(6\) giờ \(30\) phút sau nửa đêm. Kim giờ ngắn màu đen ở giữa \(6\) và \(7\) (\(6{,}5/12\) vòng); kim phút dài màu đen chỉ xuống vì đã quay đúng \(6{,}5\) vòng; kim giây đỏ chỉ lên vì đã quay số vòng nguyên.
Không may, các kim bị hỏng và trông hoàn toàn giống nhau, nên không biết kim nào là kim nào:
Ngoài ra, không còn dấu mốc để biết hướng nào là trên; mọi phép quay của mặt đồng hồ đều có thể đúng (chỉ quay, không phản chiếu):
Emmett biết thời điểm nhỏ hơn nghiêm ngặt \(12\) giờ sau nửa đêm và đã chụp ảnh. Từ ba góc kim so với một trục tùy ý, hãy tìm một thời điểm phù hợp. Trong một số nhóm, Emmett đã tìm được hướng khả dĩ hoặc thu hẹp thời điểm tới giây nguyên; xem ràng buộc.
Dữ liệu vào
Dòng đầu chứa \(T\). Mỗi dòng tiếp theo chứa ba số nguyên đã sắp \(A,B,C\): góc ba kim so với trục tùy ý, đo theo chiều kim đồng hồ bằng tick. Một tick bằng \(\frac1{12}\cdot10^{-10}\) độ. Vì vậy mỗi nanosecond, kim giờ, phút, giây quay lần lượt \(1,12,720\) tick.
Dữ liệu ra
Với mỗi bộ, in Case #x: h m s n: \(h\) là số giờ trọn từ nửa đêm (\(0..11\)), \(m\) là phút trọn từ giờ gần nhất (\(0..59\)), \(s\) là giây trọn từ phút gần nhất (\(0..59\)), \(n\) là nanosecond trọn từ giây gần nhất (\(0..10^9-1\)).
Ràng buộc
- \(1\le T\le100\).
- \(0\le A\le B\le C<360\cdot12\cdot10^{10}\).
Phân nhóm
- Test Set 1 (Visible Verdict): tồn tại thời điểm \(t\) phù hợp, \(t\) là số giây nguyên sau nửa đêm và có thể đọc mà không quay đồng hồ.
- Test Set 2 (Visible Verdict): tồn tại thời điểm phù hợp là số giây nguyên sau nửa đêm.
- Test Set 3 (Visible Verdict): tồn tại thời điểm phù hợp là số nanosecond nguyên sau nửa đêm.
Đ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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 5/30 | 16,67% |
| Test Set 2 | 6/30 | 20% |
| Test Set 3 | 19/30 | 63,33% |
Ví dụ
Ví dụ 1
Input
3
0 0 0
0 21600000000000 23400000000000
1476000000000 2160000000000 3723000000000Output
Case #1: 0 0 0 0
Case #2: 6 30 0 0
Case #3: 1 2 3 0Giải thích
Mẫu #1 có mọi kim chỉ lên, chỉ xảy ra đúng lúc nửa đêm.
Mẫu #2 là hình trong đề, với góc \(0,180,195\) độ, phù hợp \(6\)h\(30\)m mà không quay. Tuy nhiên \(0\)h\(30\)m cũng cho hình giống vậy sau khi quay \(180\) độ; ngay cả Test Set 1 cũng chấp nhận đáp án này vì điều kiện chỉ bảo đảm tồn tại một cách không quay, không cấm đáp án cần quay.
Ở mẫu #3, đầu vào là hình thứ nhất và đáp án tương ứng cách diễn giải ở hình thứ hai.
Ví dụ bổ sung — Test Set 2
??? "Giải thích"
Các trường hợp là ba mẫu trước, nhưng mặt đồng hồ quay theo chiều kim đồng hồ lần lượt $45$, $90$, $180$ độ. Ví dụ không chạy trên lời giải nộp.
```sample
3
5400000000000 5400000000000 5400000000000
10800000000000 32400000000000 34200000000000
23076000000000 23760000000000 25323000000000
```
```sample
Case #1: 0 0 0 0
Case #2: 0 30 0 0
Case #3: 1 2 3 0
```
Trường hợp 6:30 quay 90 độ đã được minh họa ở phần giải thích phía trên.
#### Ví dụ bổ sung — Test Set 3
```sample
1
0 11 719
```
```sample
Case #1: 0 0 0 1
```
Một nanosecond sau nửa đêm, các kim dịch $1,12,720$ tick. Quay đồng hồ ngược chiều kim đồng hồ $1$ tick cho đúng ba góc đầu vào.
Nguồn
Google Code Jam 2021, Vòng 1B, bài Broken Clock.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
