trang chủ / bài tập / chessplace

Xếp quân cờ cùng màu

Đề bài

Mô tả

Cho một bàn cờ kích thước 1×N với N chẵn. Các ô được đánh số từ 1 đến N và tô màu xen kẽ theo mẫu "BWBW...BW": ô lẻ màu đen, ô chẵn màu trắng.

Trên bàn cờ có đúng N/2 quân cờ, mỗi ô chứa nhiều nhất một quân. Mỗi bước đi, bạn chọn một quân và dịch nó sang ô liền trái hoặc liền phải. Không được đi ra ngoài bàn cờ và không được đi vào ô đang có quân khác.

Hãy tìm số bước ít nhất để đưa tất cả các quân về các ô cùng màu: hoặc tất cả nằm trên ô đen, hoặc tất cả nằm trên ô trắng.

Dữ liệu vào

  • Dòng đầu chứa số nguyên chẵn N là kích thước bàn cờ.
  • Dòng thứ hai chứa N/2 số nguyên p1,p2,…,pN/2 là vị trí ban đầu của các quân cờ. Các vị trí đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất: số bước đi ít nhất cần thực hiện.

Ràng buộc

  • 2≤N≤100, N chẵn
  • 1≤pi≤N
  • Các pi đôi một khác nhau

Ví dụ

Input Output Giải thích
6
1 2 6		 2 Đưa tất cả về ô lẻ: quân ở ô 6 đi sang ô 5, quân ở ô 2 đi sang ô 3, tổng 2 bước. Nếu chọn ô chẵn thì cần tới 3 bước.
10
1 2 3 4 5		 10 Đưa về các ô lẻ 1,3,5,7,9: quân ở ô 5 đi 4 bước tới ô 9, quân ở ô 4 đi 3 bước tới ô 7, quân ở ô 3 đi 2 bước tới ô 5, quân ở ô 2 đi 1 bước tới ô 3, tổng 10 bước.
2
2		 0 Chỉ có một quân, nó đã nằm trọn trên một màu nên không cần di chuyển.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 csc 6.12.0.200 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 kotlinc 2.4.10 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0