COCI 2020/2021 - Contest 1 - Bajka

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 1
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cậu bé Fabijan cảm thấy nhàm chán với những cuốn sách tranh, vì vậy cậu quyết định chuyển sang đọc truyện cổ tích. Thật không may, Fabijan thường gặp phải một từ khiến cậu sợ hãi. Để vượt qua nỗi sợ hãi của mình, Fabijan sẽ chơi một trò chơi do cậu tự sáng chế ra.

Từ đáng sợ có thể được biểu diễn dưới dạng một mảng gồm ~n~ chữ cái thường. Để bắt đầu trò chơi, Fabijan đặt ngón tay của mình lên một vị trí bất kì của mảng và viết chữ cái từ vị trí đó lên một tờ giấy. Sau đó cậu thực hiện một trong các động tác sau với số lần tùy ý:

  • Di chuyển ngón tay sang trái hoặc sang phải so với vị trí hiện tại một ký tự với điều kiện vị trí đó tồn tại ký tự. Sau đó, Fabijan sẽ viết thêm chữ cái tại vị trí mà cậu vừa chỉ lên trên giấy.
  • Di chuyển ngón tay đến bất kỳ vị trí nào có ký tự giống với ký tự hiện tại. Fabijan sẽ không viết bất kỳ điều gì trên giấy trong trường hợp này.

Cậu bé phải mất |~x~ - ~y~| giây để di chuyển ngón tay từ vị trí ~x~ sang vị trí ~y~. Fabijan sẽ vượt qua nỗi sợ hãi của mình nếu vào cuối trò chơi từ yêu thích của cậu bé được viết trên giấy. Fabijan muốn kết thúc câu chuyện cổ tích càng sớm càng tốt, vì vậy cậu bé muốn nhờ bạn tính toán cho cậu biết số giây tối thiểu để cậu có thể vượt qua nỗi sợ hãi về từ đáng sợ đã cho.

Input

Dòng đầu tiên chứa các số nguyên ~n~ và ~m~ ~(1 \leq n, m \leq 300)~.

Dòng thứ hai chứa ~n~ chữ cái thường biểu diễn từ khiến Fabijan sợ hãi.

Dòng thứ ba chứa ~m~ chữ cái thường biểu diễn từ yêu thích của Fabijan.

Output

In ra thời gian ngắn nhất có thể tính bằng giây mà Fabijan cần để viết từ yêu thích của mình lên giấy, hoặc −1 nếu không thể.

Scoring

  • 6 test đầu, từ làm Fabijan sợ hãi có các kí tự đôi một phân biệt.
  • 11 test sau không có điều kiện gì thêm.

Sample 1

Input
2 2
wa
ac
Output
-1

Sample 2

Input
7 7
monolog
nogolom
Output
10

Sample 3

Input
14 5
niskoobrazovan
boook
Output
5

Note

Giải thích ví dụ thứ ba: Đầu tiên Fabijan sẽ đặt ngón tay của mình lên vị trí thứ ~7~ và viết ra chữ cái b. Sau đó, cậu bé sẽ di chuyển ngón tay sang trái hai lần và mỗi lần lại viết ra chữ cái o. Trong bước tiếp theo, cậu sẽ di chuyển ngón tay đến vị trí thứ ~6~ bằng cách sử dụng kiểu di chuyển thứ hai. Cuối cùng, Fabijan sẽ lại di chuyển ngón tay sang trái hai lần và viết ra các chữ cái ok. Cậu mất tổng cộng năm giây, một giây cho mỗi lần di chuyển.


Comments

Please read the guidelines before commenting.



  • 1
    0855250956   commented on Feb. 22, 2022, 4:42 p.m.

    em đã khóc khi đọc test 1 :'(