Nội dung Bài tập
- Mã:
- OLP17.KC2.CAMERA
- Tên:
- Camera quan sát
- Dạng thi:
- oi
- Thang điểm:
- 30 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- Olympic tin học 2017
- Được tạo bởi:
- thuthq
Có n camera quan sát, đánh số tuần tự từ 1 đến n, được đặt lần lượt thẳng hàng trên đường cao tốc từ Tây sang Đông. Camera thứ i được đặt ở độ cao hi và hướng về một trong hai hướng: Tây hoặc Đông.
Camera thứ i có thể quan sát được camera thứ j nếu camera thứ i nhìn về phía camera thứ j và không có bất kỳ camera nào ở giữa hai camera này có độ cao vượt quá độ cao của camera thứ j.
Yêu cầu: Cho biết độ cao và hướng nhìn của n camera. Hãy cho biết mỗi camera có thể quan sát được bao nhiêu camera khác.
Dữ liệu input: CAMERA.INP
- Dòng đầu chứa số nguyên dương n
- Dòng thứ hai gồm n số nguyên dương ℎ1,ℎ2,…,hn là độ cao của mỗi camera (1≤hk≤109 với 1<=k<=n);
- Dòng thứ ba chứa một xâu gồm n ký tự cho biết hướng nhìn của các camera với quy ước: ‘W’ là nhìn sang hướng Tây, ‘E’ là nhìn sang hướng Đông.
Kết quả: CAMERA.OUT
một dòng n số tự nhiên, số thứ k cho biết số lượng camera mà camera thứ k (k=1,2,…,n) có thể quan sát được.
Ví dụ:
Input Output 5 1 2 2 3 1 EEWWE 3 2 1 2 0
Chú ý:
- Có 40% số test có n≤102;- Có 20% số test có n≤103;- Có 40% số test còn lại có n≤105.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận