Biến đổi hai xâu

Xem PDF



Thời gian:
Java 3.0s
Python 3.0s

Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai xâu độ dài bằng nhau \(s_1,s_2\) và hai nút bấm thần kỳ: nút màu xanh khi bấm vào sẽ giúp xóa đi một ký tự đầu của xâu \(s_1\) và một ký tự cuối của xâu \(s_2\), nút màu đỏ khi được bấm sẽ giúp xóa đi một ký tự đầu của xâu \(s_2\) và một ký tự cuối của xâu \(s_1\). Hỏi nếu muốn thu được hai xâu bằng nhau thì ta phải bấm các nút trên ít nhất bao nhiêu lần?

Input

  • Dòng đầu chứa số nguyên dương \(n\) thể hiện độ dài của \(s_1\)\(s_2\).

  • Dòng thứ hai và thứ ba lần lượt chứa xâu \(s_1\) và xâu \(s_2\) chỉ gồm các ký tự latin in thường.

Output

  • Đưa ra một số nguyên duy nhất là số lần bấm nút để có thể thu được hai xâu bằng nhau. Dữ liệu đảm bảo tồn tại một cách bấm nút để đưa cả hai xâu về cùng bằng một xâu khác rỗng.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n \leq 300\).
  • Subtask \(2\) (\(60\%\) số điểm): \(n \leq 3000\).

Example

Test 1

Input
3
abc
cba 
Output
2
Note

Ta cần bấm nút màu xanh đúng một lần và nút màu đỏ đúng một lần để thu được xâu b.


Bình luận


  • -6
    volantuan0908    10:31 a.m. 16 Tháng 9, 2022

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.