Bedan Contest #05 - F - Đảo ngược

View as PDF

Submit solution


Points: 1200
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho dãy ab gồm n phần tử là hoán vị của n. Bạn được thực hiện thao tác tối đa n lần:

  • Chọn 2 số nguyên dương lr (1 \le l \le r \le n), sau đó đảo ngược đoạn con [l, r] của a.

Nhiệm vụ của bạn là in ra m (0 \le m \le n) là số thao tác và m thao tác bạn cần thực hiện để biến đổi dãy a thành b.

Input and Output

Input
  • Số nguyên dương n (1 \le n \le 10^3).
  • Dãy a gồm n phần tử a_1, a_2, ..., a_n (1 \le a_i \le n).
  • Dãy b gồm n phần tử b_1, b_2, ..., b_n (1 \le b_i \le n).
Output
  • In ra m là số thao tác, sau đó là m dòng tương ứng với m thao tác cần thực hiện.
  • Nếu có nhiều cách thực hiện thao tác thỏa mãn, hãy in ra một cách bất kì.

Test

Input
5
4 2 3 5 1
1 5 4 2 3 
Output
3
3 5
1 3
2 4
Note
  • Ngoài cách trên, đảo ngược đoạn [1, 5] rồi đến [1, 3] cũng được tính là đúng.

Comments

There are no comments at the moment.