Robot chiếm thành
View as PDFTrò chơi Robot chiếm thành là một trò chơi điện tử trí tuệ được nhiều bạn trẻ yêu thích. Nhiệm vụ chính của trò chơi là dịch chuyển các con robot để chiếm được tất cả các ô của một thành.
Trò chơi được thực hiện trên lưới ô vuông gồm 200.000.001 dòng và 200.000.001 cột, các dòng được đánh chỉ số từ -100.000.000 đến 100.000.000 theo hướng từ dưới lên trên, các cột được đánh chỉ số từ -100.000.000 đến 100.000.000 theo hướng từ trái sang phải. Ô ở cột ~i~, dòng ~j~ được gọi là ô ~(i,j)~.
Khi người chơi chọn một tham số ~n~, sẽ có ~2n~ con robot xuất hiện trên lưới ô vuông, con robot thứ ~i~ ~(i = 1, 2, .., 2n)~ đứng tại ô ~(X_i,Y_i)~. Các con robot có thể cùng đứng trên một ô vuông trên lưới. Thành mà các con robot cần chiếm có dạng hình chữ nhật gồm ~2n~ ô vuông nhỏ. Góc trái trên là ô ~(1, 2)~, góc phải dưới là ô ~(n,1)~. Nghĩa là Thành gồm ~2n~ ô ~(x,y)~ với ~1 ≤ x ≤ n~ ; ~1 ≤ y ≤ 2~.
Người chơi phải dịch chuyển ~2n~ con robot này vào đứng ~2n~ ô vuông khác nhau của Thành. Người chơi dịch chuyển robot càng ít lần thì được càng nhiều điểm. Mỗi lần dịch chuyển, robot chỉ được di chuyển sang ô vuông kề cạnh. Trong quá trình di chuyển, có thể nhiều con robot cùng ở một ô vuông.
Yêu cầu: Tính xem, người chơi cần sử dụng ít nhất bao nhiều lần di chuyển các robot để đưa ~2n~ con robot chiếm ~2n~ ô vuông khác nhau của Thành.
Dữ liệu gồm:
- Dòng thứ nhất chứa số nguyên dương ~n~.
- Dòng thứ ~i~ trong ~2n~ dòng tiếp theo, mỗi dòng gồm hai số ~X_i,Y_i~ là tọa độ của ô mà con robot thứ ~i~ đang đứng ~(|X_i|, |Y_i| ≤10^9)~.
Kết quả:
- Số nguyên duy nhất là số lần di chuyển ít nhất để di chuyển ~2n~ con robot đến ~2n~ ô vuông khác nhau của Thành.
Ví dụ:
Input
3
0 0
0 4
4 0
2 1
2 5
-1 1
Output
15
Giải thích:
- Robot 1: (0, 0) → (1, 0) → (1, 1) → (1, 2); mất 3 lần di chuyển.
- Robot 2: (0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2); mất 5 lần di chuyển.
- Robot 3: (4, 0) → (4, 1) → (3, 1); mất 2 lần di chuyển.
- Robot 4: (2, 1) không cần di chuyển.
- Robot 5: (2, 5) → (2, 4) → (2, 3) → (2, 2); mất 3 lần di chuyển.
- Robot 6: (-1, 1) → (0, 1) → (1, 1); mất 2 lần dịch chuyển.
- Vậy tổng: 3 + 5 + 2 + 0 + 3 + 2 = 15 lần dịch chuyển. Đây là số lần dịch chuyển ít nhất cần thiết.
Ràng buộc:
- Có 25 % test ứng với ~n ≤ 10~;
- Có 25 % test ứng với ~n ≤ 1000~;
- Có 50 % test còn lại ứng với ~n ≤ 10^5~;
Comments
abc là cái gì vậy cô?
Có nội dung rồi nha em!
Bài của đội tuyển mà cô chưa edit đề á.