단어 굴리기
시간 제한2초메모리 제한128 MB
매초 한 칸씩 회전하는 N개의 문자 바퀴가 목표 문자열을 동시에 표시하는 가장 빠른 시각을 중국인의 나머지 정리 방식으로 구하고, 불가능하면 -1을 출력합니다.
문제
전광판은 N개의 원형 문자 바퀴로 이루어져 있으며, 각 바퀴는 한 번에 한 글자만 보여 준다. 0초에는 모든 바퀴에서 각자 적힌 문자열의 첫 글자가 보인다. 매초 모든 바퀴가 한 칸씩 앞으로 회전하고, 마지막 글자 다음에는 다시 첫 글자로 돌아간다.
i번째 바퀴에 적힌 문자열을 S_i라고 하면, t초 뒤 그 바퀴에는 S_i[t mod |S_i|]가 보인다. 원하는 문자열 T가 주어졌을 때, 전광판 전체가 처음으로 T를 보여 주는 가장 작은 시간 t를 구하라. 어떤 시간에도 T가 나타나지 않으면 -1을 출력한다.
입력
첫째 줄에 전광판의 크기 N이 주어진다. N은 50 이하의 자연수이다.
둘째 줄부터 N개의 줄에는 각 바퀴에 적힌 문자열이 하나씩 주어진다. 각 문자열은 대문자로만 이루어져 있고, 길이는 3 이상 26 이하이다.
마지막 줄에는 보고 싶은 문자열 T가 주어진다. T의 길이는 N이고, 대문자로만 이루어져 있으며, T 안에 등장하는 알파벳은 서로 다르다.
출력
전광판 전체가 문자열 T를 처음 보여 주는 시간을 출력한다. 그런 시간이 없으면 -1을 출력한다. 출력해야 하는 정답은 9,223,372,036,854,775,807 이하이다.