Kickdown
InterviewTime limit2sMemory limit128 MB
Given two gear strings of 1s and 2s, slide one horizontally to minimize the combined width without any overlapping position having a tooth (2) on both.
- Level
Medium4 of 10
- Topics
- String, Brute force, Simulation
- Solved
- No attempts yet
Problem
Each gear piece is represented by a string made of 1 and 2. A 1 is a groove, and a 2 is a protruding tooth.
Place the two gear pieces in the same direction. You may slide one piece left or right before meshing them. If both pieces have 2 at an overlapping position, two teeth collide, so that placement is invalid. Every other overlap is allowed.
Find the minimum horizontal width that can contain both gear pieces when they are placed without any collision.
Input
The first line contains the string representing the first gear piece.
The second line contains the string representing the second gear piece.
Each string consists only of 1 and 2, and each length is at most 100.
Output
Print the minimum possible horizontal width when the two gear pieces are placed without collision.