PreVOI 2025 - Trò chơi trí tuệ
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Alice thiết kế một trò chơi trên vòng tròn số như sau:
Bắt đầu trò chơi, máy tính sẽ tạo ra một dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ và lần lượt xếp cách đều nhau theo chiều kim đồng hồ để nhận được vòng tròn số ~A~. Khi đó, số thứ ~i~ ~(1 \le i < n)~ sẽ là số kề bên phải của số thứ ~(i+1)~, số thứ ~n~ là kề bên phải của số ~1~. Tương tự, máy tính tạo ra dãy số ~b_1, b_2, \dots, b_n~ để nhận được vòng tròn số ~B~.
Người chơi cần biến đổi vòng tròn ~A~ thành vòng tròn ~B~ bằng dãy thao tác có dạng: Chọn hai số kề nhau và tăng số nhỏ hơn bằng số lớn hơn.
Yêu cầu: Hãy giúp Alice tính số thao tác biến đổi ít nhất để đưa vòng tròn ~A~ về vòng tròn ~B~ hoặc cho biết không thể biến đổi. Chú ý, hai vòng tròn là cố định không được phép xoay.
Input
Dòng đầu tiên chứa số nguyên dương ~n~ ~(3 \le n \le 10^5)~;
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9)~;
Dòng thứ ba chứa ~n~ số nguyên dương ~b_1, b_2, \dots, b_n~ ~(a_i \le 10^9)~.
Output
- Gồm một dòng chứa một số là số thao tác ít nhất để đưa vòng tròn ~A~ về vòng tròn ~B~ hoặc đưa ra -1 nếu không thể biến đổi.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~25\%~ | ~n \le 1000~; ~1 \le a_i, b_i \le 2~ |
| 2 | ~25\%~ | ~a_1, a_2, \dots, a_n~ là một hoán vị của ~1, 2, \dots, n~ |
| 3 | ~25\%~ | ~n \le 1000~ |
| 4 | ~25\%~ | Không có giới hạn gì thêm |
Sample Input 1
5
1 2 1 1 1
2 2 1 2 2
Sample Output 1
3
Sample Input 2
5
1 2 3 4 5
5 4 4 4 5
Sample Output 2
3
Bình luận