Cảnh sát và tội phạm
Đề bài
Mô tả
Có thành phố xếp thành một hàng, đánh số từ đến . Khoảng cách giữa thành phố và thành phố bằng .
Một cảnh sát sống ở thành phố . Mỗi thành phố có nhiều nhất một tên tội phạm. Cảnh sát dùng một thiết bị dò: với mỗi khoảng cách , thiết bị cho biết có bao nhiêu tên tội phạm nằm ở các thành phố cách đúng đơn vị (tức tổng số tội phạm ở hai thành phố và , chỉ tính những thành phố tồn tại).
Sau khi đọc thông tin từ thiết bị, cảnh sát chỉ bắt được tội phạm ở những thành phố mà anh ta chắc chắn có tội phạm. Cụ thể, với khoảng cách :
- Nếu chỉ có một trong hai thành phố , tồn tại thì số tội phạm mà thiết bị báo chính là số tội phạm ở thành phố đó, nên cảnh sát biết chắc.
- Nếu cả hai thành phố tồn tại và thiết bị báo , thì cả hai đều có tội phạm, cảnh sát bắt được cả hai.
- Nếu cả hai thành phố tồn tại và thiết bị báo , cảnh sát không biết tội phạm nằm ở thành phố nào nên không bắt được ai ở khoảng cách đó.
Biết trước vị trí thực tế của các tên tội phạm, hãy đếm số tội phạm mà cảnh sát bắt được.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và (): số thành phố và chỉ số thành phố nơi cảnh sát sống.
- Dòng thứ hai chứa số nguyên (): là số tội phạm ở thành phố thứ .
Dữ liệu ra
In ra một số nguyên: số tội phạm mà cảnh sát bắt được.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 3 1 1 1 0 1 0 |
3 | Cảnh sát ở thành phố . Khoảng cách : một tội phạm ở thành phố , bắt được. Khoảng cách : một tội phạm (thành phố hoặc ), không rõ nên bỏ qua. Khoảng cách : hai tội phạm ở thành phố và , bắt cả hai. Tổng cộng bắt được . |
| 5 2 0 0 0 1 0 |
1 | Thiết bị báo có một tội phạm ở khoảng cách . Chỉ có thành phố ở khoảng cách (thành phố không tồn tại), nên cảnh sát biết chắc và bắt được. |
Bình luận