Nộp bài
Điểm:
1600 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
KDQUEEN.inp
Output:
KDQUEEN.out
Tác giả:
Dạng bài
Trên một bàn cờ vua k chiều, với kích thước được định trước bởi một dãy số nguyên a_1, a_2, ..., a_k, với ý nghĩa là ở chiều thứ i có a_i ô, có đặt một quân Hậu ở vị trí (b_1, b_2, ..., b_k). Quân Hậu có thể di chuyển đến các ô cùng hàng hoặc cùng đường chéo với nó. Cùng hàng nghĩa là tồn tại giá trị i sao cho c_i \neq b_i và c_j = b_j\ \forall j \neq i. Cùng đướng chéo có nghĩa là |c_1 - b_1| = |c_2 - b_2| = ... = |c_k - b_k|. Đếm số ô mà quân Hậu có thể di chuyển đến trong một nước đi.
Input, Output và Subtasks
Input: (KDQUEEN.inp
)
- Dòng đầu tiên gồm số nguyên dương 2 \le k \le 10^5 là số chiều của bàn cờ.
- Dòng tiếp theo gồm k số nguyên dương a_1, a_2, ..., a_k, a_i \le 10^9 mô tả kích thước của bàn cờ.
- Dòng tiếp theo gồm k số nguyên dương b_1, b_2, ..., b_k, b_i \le a_i mô tả vị trí của quân Hậu.
Output: (KDQUEEN.out
)
- Một dòng duy nhất là kết quả bài toán sau khi chia lấy dư cho 10^9+7.
Subtasks
- Subtask 1 (10\%): k = 2.
- Subtask 2 (15\%): k \le 5, a_i \le 10.
- Subtask 3 (15\%): k \le 5, a_i \le 100.
- Subtask 4 (15\%): k \le 1000, a_i \le 1000.
- Subtask 5 (20\%): a_i \le 10^5.
- Subtask 6 (25\%): Không có giới hạn gì thêm.
Sample
Input (KDQUEEN.inp
)
3
3 3 3
1 2 3
Output (KDQUEEN.out
)
8
Notes
Các ô đi được là: (3, 2, 3); (2, 2, 3); (1, 1, 3); (1, 2, 1); (1, 3, 3); (1, 2, 2); (2, 1, 2); (2, 3, 2).
Bình luận