Tuyến Bay

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie muốn tham dự một chuyến lưu diễn qua $N$ thành phố ( $2 \leq N \leq 750$ ). Giữa mỗi cặp thành phố, có thể tồn tại hoặc không một chuyến bay trực tiếp (vô hướng).

Một tuyến bay từ thành phố $i$ đến thành phố $j$ ( $i < j$ ) là một dãy các thành phố bắt đầu từ $i$ và kết thúc tại $j$ , trong đó các thành phố liên tiếp được nối bằng chuyến bay trực tiếp (mỗi thành phố trung gian nằm giữa $i$ và $j$ ).

Cho tính chẵn lẻ (parity) của số lượng tuyến bay giữa mọi c��p thành phố $(i, j)$ với $i < j$ , hãy xác định tổng số chuyến bay trực tiếp tồn tại.

Dữ liệu vào

Dòng $1$ : Số nguyên $N$ .
$N - 1$ dòng tiếp theo: Dòng thứ $i$ chứa $N - i$ số nguyên, số thứ $j$ là tính chẵn lẻ ( $0$ hoặc $1$ ) của số tuyến bay từ thành phố $i$ đ��n thành phố $i + j$ .

Dữ liệu ra

In ra một số nguyên — tổng số chuyến bay trực tiếp giữa các cặp thành phố.

Ràng buộc

Các test $3$ - $4$ : $N \leq 6$ .
Các test $5$ - $12$ : $N \leq 100$ .
Các test $13$ - $22$ : Không có ràng buộc thêm ( $N \leq 750$ ).

Ví dụ

Input	Output	Giải thích
3 11 1	2	Có chuyến bay trực tiếp 1-2 và 2-3. Tuyến bay 1-3 duy nhất đi qua 2.
5 1111 101 01 1	6	Có 6 chuyến bay trực tiếp: 1-2, 1-4, 1-5, 2-3, 3-5, 4-5.

Bình luận

Không có bình luận tại thời điểm này.