알파벳 주위를 달리기
면접 대비시간 제한2초메모리 제한512 MB
원주에 놓인 28개 기호를 문자 순서대로 방문할 때 인접 기호 사이는 항상 짧은 호를 택해 이동하고, 잡는 데 1초씩 걸린다고 보고 총 걸린 시간을 계산합니다.
문제
축구 코치 Joe는 선수들의 민첩성과 체력을 기르는 데 도움이 될 새로운 체력 훈련 게임을 고안했다. 축구장의 센터 서클은 지름이 60피트다. 그는 원둘레 위에 28개의 점을 같은 간격으로 찍는다. 첫 번째 점(임의로 정한)에는 'A'가 새겨진 토큰 더미를 놓는다. 두 번째 점에는 'B' 토큰 더미를 놓고, 이런 식으로 28개의 점 중 26개를 채운다. 27번째 점에는 공백(space) 더미를 놓고, 마지막 점에는 작은따옴표가 찍힌 원판 더미를 놓는다.
그는 각 선수에게 "WINNING ISN'T EVERYTHING IT'S THE ONLY THING" 같은 격언이 적힌 종이쪽지를 준다. 사용할 수 있는 구두점은 공백과 작은따옴표뿐이다. 각 선수는 서로 다른 격언을 받는다.
선수는 원 밖에서 자기 격언의 첫 글자 옆에서 시작해, Joe가 "GO" 신호를 보내면 첫 원판을 집고 원 바깥을 따라 달리기 시작하며, 격언에 해당 글자가 나오는 순서대로 나머지 원판을 집는다. 똑똑한 선수는 격언의 연속한 글자 사이를 최단 경로로 이동하며, 필요하면 방향을 바꾼다.
보조 코치 한 명이 선수의 시간을 기록한다. Joe는 처음에 선수 20명이 동시에 원을 도는 것을 생각했지만, 타박상과 골절 때문에 이 아이디어는 폐기되었다.
Joe는 똑똑한 선수 한 명이 각 격언을 완료하는 데 걸리는 예상 시간을 계산하는 프로그램을 원한다. 단순화를 위해 선수는 집기 위해 멈춘 지점 사이를 초속 15피트로 달리고, 원판 하나를 집는 데 1초가 걸린다고 가정한다.
입력
입력은 첫 줄에 격언의 수 N (1 ≤ N ≤ 20)으로 시작한다. 이어서 N개의 줄이 주어지며, 각 줄에는 대문자, 작은따옴표, 공백으로 이루어진 격언이 하나씩 있다. 각 격언의 길이는 8자 이상 120자 이하다.
출력
각 격언마다 똑똑한 선수가 그 일을 완료하는 데 걸리는 시간을 출력한다. 답은 10−6초 이내의 오차로 정확해야 한다.