Google Code Jam 2008 - What are Birds?
Xem PDFBạn đang nghiên cứu các loài động vật trong một khu rừng và cố gắng xác định loài nào là chim và loài nào không phải.
Bạn thực hiện việc này bằng cách đo hai chỉ số của mỗi con vật – chiều cao và cân nặng của chúng. Để một con vật là chim, chiều cao của nó cần nằm trong một khoảng nhất định và cân nặng của nó cần nằm trong một khoảng khác, nhưng bạn không chắc chắn các khoảng chiều cao và cân nặng đó là gì. Bạn cũng biết rằng mọi con vật thỏa mãn các khoảng này đều là chim.
Bạn đã mang một số con vật mà bạn đo được cho các nhà sinh vật học xem, và họ đã cho bạn biết con nào là chim và con nào không. Điều này đã cung cấp cho bạn một số thông tin về các khoảng chiều cao và cân nặng của chim. Đối với những con vật còn lại, chương trình của bạn nên xác định xem chúng chắc chắn là chim, chắc chắn không phải chim, hoặc bạn không thể biết được từ thông tin hiện có.
Dữ liệu vào
Một dòng chứa một số nguyên C, số lượng bộ dữ liệu kiểm tra.
Sau đó, với mỗi bộ dữ liệu trong số C bộ:
- Một dòng chứa một số nguyên N, số lượng động vật bạn đã cho các nhà sinh vật học xem.
- N dòng, mỗi dòng cho một con vật, theo định dạng "H W X", trong đó H là chiều cao, W là cân nặng, và X là chuỗi "BIRD" hoặc "NOT BIRD". Tất cả các số đều là số nguyên dương.
- Một dòng chứa một số nguyên M, số lượng động vật bạn chưa cho các nhà sinh vật học xem.
- M dòng, mỗi dòng cho một con vật, theo định dạng "H W", trong đó H là chiều cao và W là cân nặng. Tất cả các số đều là số nguyên dương.
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Một dòng chứa chuỗi "Case #X: " trong đó X là số thứ tự của bộ dữ liệu, bắt đầu từ 1.
- M dòng, mỗi dòng chứa một trong các chuỗi "BIRD", "NOT BIRD", hoặc "UNKNOWN".
Ràng buộc
- \(1 \le \mathbf{C} \le 10\)
- \(1 \le\) tất cả chiều cao và cân nặng \(\le 1000000\)
Phân nhóm
- Small dataset: \(1 \le \mathbf{N} \le 10, 1 \le \mathbf{M} \le 10\).
- Large dataset: \(1 \le \mathbf{N} \le 1000, 1 \le \mathbf{M} \le 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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 5/17 | 29,41% |
| Test Set 2 | 12/17 | 70,59% |
Ví dụ
Ví dụ 1
Input
3
5
1000 1000 BIRD
2000 1000 BIRD
2000 2000 BIRD
1000 2000 BIRD
1500 2010 NOT BIRD
3
1500 1500
900 900
1400 2020
3
500 700 NOT BIRD
501 700 BIRD
502 700 NOT BIRD
2
501 600
502 501
1
100 100 NOT BIRD
3
107 93
86 70
110 115Output
Case #1:
BIRD
UNKNOWN
NOT BIRD
Case #2:
UNKNOWN
NOT BIRD
Case #3:
UNKNOWN
UNKNOWN
UNKNOWNNote
Giải thích ví dụ:
- Trường hợp 1:
- Con vật "1500 1500" chắc chắn nằm trong các khoảng của chim, vì chúng ta biết rằng các khoảng cho chiều cao và cân nặng lần lượt bao gồm 1000 và 2000.
- Con vật "900 900" có thể là chim hoặc không; chúng ta không biết liệu các khoảng cho chiều cao và cân nặng có bao gồm 900 hay không.
- Con vật "1400 2020" nằm trong khoảng chiều cao của chim, nhưng nếu 2020 nằm trong khoảng cân nặng, thì con vật "1500 2010" (mà chúng ta biết không phải là chim) cũng sẽ phải nằm trong khoảng cân nặng đó.
- Trường hợp 2:
- Trong trường hợp này, chúng ta biết chim phải có chiều cao 501. Nhưng chúng ta không biết khoảng cân nặng của chim là bao nhiêu, ngoài việc nó bao gồm cân nặng 700.
- Trường hợp 3:
- Trong trường hợp này, chúng ta biết bất cứ thứ gì có chiều cao 100 và cân nặng 100 đều không phải là chim, nhưng chúng ta đơn giản là không biết chim là gì.
Nguồn
Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài What are Birds?.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2008 - APAC Semifinal (22 Tháng 9., 2008)
Bình luận