TLE-oj Cup Round 4 - Quân Mã k chiều

Điểm: 1400 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: KDKNIGHT.inp

Output: KDKNIGHT.out

Tác giả:

Sunlight

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 Mã ở vị trí $(b_1, b_2, ..., b_k)$ .

Trong mỗi nước đi, quân Mã sẽ thực hiện thao tác sau:

Chọn hai chiều $i$ và $j$ .
Thực hiện nước đi hình chữ $L$ như trên bàn cờ hai chiều.

Tổng quát hóa, quân Mã có thể đi được đến ô $(c_1, c_2, ..., c_k)$ khi và chỉ khi thỏa mãn hai điều kiện sau:

$|c_1 - b_1| + |c_2 - b_2| + ... + |c_k - b_k| = 3$ .
$max(|c_1 - b_1|, |c_2 - b_2|, .., |c_k - b_k|) = 2$ .

Đếm số ô mà quân Mã đến được trong một nước đi.

Input, Output và Subtasks

Input: (KDKNIGHT.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 Mã.

Output: (KDKNIGHT.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 $(20\%)$ : $k = 2$ .
Subtask 2 $(20\%)$ : $min(a_i - b_i, b_i) \ge 3$ .
Subtask 3 $(30\%)$ : $k \le 1000, a_i \le 1000$ .
Subtask 4 $(30\%)$ : Không có giới hạn gì thêm.

Sample

Input (KDKNIGHT.inp)

3
3 3 3
1 2 3

Output (KDKNIGHT.out)

Notes

Các ô đi được là: $(2, 2, 1); (3, 2, 2); (3, 3, 3); (3, 1, 3); (1, 3, 1); (1, 1, 1).$

Bình luận

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