PreVOI 2025 - Trò chơi trí tuệ

Xem dạng PDF

Gửi bài giải

Điểm: 90,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong 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

Hãy đọc nội quy trước khi bình luận.


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