2. Google Code Jam 2008 - How Big Are the Pockets?
Giáo sư Polygonovich, một công dân lương thiện của xứ sở Flatland, thích đi dạo ngẫu nhiên dọc theo các điểm nguyên trên mặt phẳng. Ông bắt đầu từ gốc tọa độ vào buổi sáng, hướng về phía bắc. Có ba loại hành động ông thực hiện:
- 'F': tiến về phía trước một đơn vị độ dài.
- 'L': quay trái 90 độ.
- 'R': quay phải 90 độ.
Vào cuối ngày (vâng, đó là một chuyến đi bộ dài!), ông quay trở lại gốc tọa độ. Ông không bao giờ đi qua cùng một điểm hai lần ngoại trừ gốc tọa độ, vì vậy đường đi của ông bao quanh một đa giác. Trong hình dưới đây, phần bên trong của đa giác được tô màu xanh lam (tạm thời bỏ qua các điểm x, y, z và w; chúng sẽ được giải thích sớm thôi):
Lưu ý rằng miễn là Giáo sư Polygonovich thực hiện nhiều hơn 4 lần rẽ, đa giác đó sẽ không lồi. Vì vậy, có những "túi" (pockets) trong đó.
Cảnh báo! Để làm cho nhiệm vụ của bạn khó khăn hơn, định nghĩa về túi của chúng tôi có thể khác với những gì bạn từng nghe trước đây.
Khu vực màu xám dưới đây cho biết các túi của đa giác.
Về mặt hình thức, một điểm p được gọi là nằm trong một túi nếu nó không nằm bên trong đa giác, và ít nhất một trong hai điều kiện sau được thỏa mãn:
- Có các điểm biên nằm trực tiếp ở cả phía đông và phía tây của p; hoặc
- Có các điểm biên nằm trực tiếp ở cả phía bắc và phía nam của p.
Các điểm biên là các điểm mà ông Polygonovich đã đi qua trong chuyến đi bộ của mình (bao gồm tất cả các điểm trên đường đi, không chỉ các điểm có tọa độ nguyên).
Hãy xem lại hình ảnh đầu tiên ở trên. Điểm x thỏa mãn điều kiện thứ nhất; y thỏa mãn cả hai; z thỏa mãn điều kiện thứ hai. Cả ba điểm đều nằm trong các túi. Điểm w không nằm trong túi.
Cho biết chuyến đi bộ của Polygonovich, nhiệm vụ của bạn là tìm tổng diện tích của các túi.
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, N. N bộ test theo sau.
Mỗi bộ test mô tả một chuyến đi bộ của Giáo sư Polygonovich. Nó bắt đầu bằng một số nguyên L. Tiếp theo là L cặp "S T", trong đó S là một chuỗi bao gồm các ký tự 'L', 'R' và 'F', và T là một số nguyên cho biết chuỗi S được lặp lại bao nhiêu lần.
Nói cách khác, dữ liệu vào cho một bộ test trông như thế này:
S1 T1 S2 T2 ... SL TL
Các hành động được thực hiện là sự kết hợp của \(T_1\) bản sao của \(S_1\), tiếp theo là \(T_2\) bản sao của \(S_2\), và cứ tiếp tục như vậy.
Các cặp "S T" cho một bộ test đơn lẻ có thể không nằm trên cùng một dòng, nhưng các chuỗi S sẽ không bị ngắt quãng giữa nhiều dòng. Ví dụ thứ hai bên dưới minh họa điều này.
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à tổng diện tích của tất cả các túi.
Ràng buộc
- \(1 \le N \le 100\)
- \(1 \le T\) (được giới hạn bởi các ràng buộc trong phần "Small dataset" và "Large dataset")
- Đường đi, khi được nối từ các chuỗi nhập vào, sẽ không có hai lần đổi hướng liên tiếp (nghĩa là sẽ không có 'LL', 'RR', 'LR', cũng như 'RL' trong đường đi đã nối). Sẽ có ít nhất một 'F' trong đường đi.
- Đường đi được mô tả sẽ không tự cắt chính nó, ngoại trừ ở điểm cuối, và nó sẽ kết thúc tại gốc tọa độ.
Phân nhóm
- Small dataset (Test set 1 - Visible):
- \(1 \le L \le 100\)
- Độ dài của mỗi chuỗi S sẽ nằm trong khoảng từ 1 đến 16, bao gồm cả hai đầu.
- Giáo sư sẽ không đi thăm bất kỳ điểm nào có tọa độ có giá trị tuyệt đối lớn hơn 100.
- Large dataset (Test set 2 - Hidden):
- \(1 \le L \le 1000\)
- Độ dài của mỗi chuỗi S sẽ nằm trong khoảng từ 1 đến 32, bao gồm cả hai đầu.
- Giáo sư sẽ không đi thăm bất kỳ điểm nào có tọa độ có giá trị tuyệt đối lớn hơn 3000.
Đ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/20 | 25% |
| Test Set 2 | 15/20 | 75% |
Ví dụ
Ví dụ 1
Input
2
1
FFFR 4
9
F 6 R 1 F 4 RFF 2 LFF 1
LFFFR 1 F 2 R 1 F 5Output
Case #1: 0
Case #2: 4Note
Hình ảnh sau đây minh họa hai bộ test ví dụ.
Nguồn
Google Code Jam 2008, Vòng 3, bài How Big Are the Pockets?.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
