Little Shikamaru And Caesar Cipher
Tag(s):

## Medium-Hard

Problem
Editorial
Analytics

Yesterday's number theory class was taught by Shiho a member of the Konoha Cryptanalysis Team. She taught the young ninjas Caesar Cipher Encryption and how it is used in real missions. Little Shikamaru found the method very genius and beautiful.

So, when he came home, he came up with the following problem. Given two strings of digits initial and target, he will take any substring of length K or smaller from the initial string, and apply a right shift of any length he wants. He will repeat this process until he fully converts it to the target string, or he will stop if he thinks it is impossible. Little Shikamaru would like to know the minimum number of moves required to complete the conversion.

Shifting right by x, means substituting every digit by the $x^{th}$ digit after it, wrapping arround if needed. For example, when we shift "9" by 1, it will become "0".

Input Format:

Each test case starts with K the length of the substring. Second and third lines contain the initial and target strings, respectively.

Output Format:

Print the minimum number of moves in order to convert initial to target, else print 1 if it is impossible.

Constraints:

• $0 \le K \le 6$
• Length of initial and target are less than or equal $50$
• Length of initial and target is the same
SAMPLE INPUT
2
0011
1221
SAMPLE OUTPUT
2
Explanation

Apply a right shift of length 1 to the first two characters, then your intial string will become [11 11]. The second move is to update the second and third characters again by a right shift of length 1 to get the final string.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Dynamic Programming