Dây Điện Chuồng Bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Có $N$ con bò (đánh số $1$ đến $N$ , $N$ chẵn) cần được xếp vào một dãy $N$ ô chuồng liên tiếp. Mỗi con bò có đúng $3$ người bạn. Các cặp bạn được kết nối bằng dây — độ dài dây bằng khoảng cách giữa hai vị trí chuồng.

Hãy tìm cách xếp $N$ con bò sao cho tổng độ dài dây là nhỏ nhất.

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $4 \leq N \leq 12$ , $N$ chẵn)
$N$ dòng tiếp theo: dòng thứ $i$ gồm 3 số nguyên — chỉ số 3 người bạn của con bò $i$

Dữ liệu ra

Một số nguyên — tổng độ dài dây tối thiểu.

Ràng buộc

$4 \leq N \leq 12$ , $N$ chẵn
Mỗi con bò có đúng 3 người bạn
Quan hệ bạn bè là đối xứng

Ví dụ

Input	Output	Giải thích
6 6 2 5 1 3 4 4 2 6 5 3 2 4 6 1 1 5 3	17	Xếp theo thứ tự 6,5,1,4,2,3 cho tổng dây = 17.
6 2 4 5 1 5 6 5 6 4 1 3 6 3 2 1 3 4 2	17	Một cấu hình khác cũng cho tổng = 17.

Bình luận

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