TLE-oj Cup Round 4 - Quân Hậu k chiều

Xem PDF

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ứ ia_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_ic_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

Không có bình luận nào.