이맥스++ timer 60s memory 1024MB

2016년의 Distributed Code Jam에서는, 괄호 밀도가 더 높은 것을 선호하는 Lisp 팬들을 위해 Lisp++ 언어를 소개했다. 이 언어의 문법이 어떻게 동작하는지 다시 한 번 상기해 보자:

Lisp++ 프로그램은 균형잡힌 괄호 문자열이다. 좀 더 정확히 말하면, Lisp++ 프로그램은 다음 중 하나로 이루어진다. (이 명세에서 C는 어떤 프로그램 코드 — 매번 같은 코드일 필요는 없음 — 를 의미한다.)

• () 그대로 여는 괄호 하나와 닫는 괄호 하나이다. 이 (는 이 )와 매칭된다고 하며, 반대도 마찬가지다.
• (C) 괄호 한 쌍 안에 들어 있는 하나의 프로그램이다. 이 (는 이 )와 매칭된다고 하며, 반대도 마찬가지다.
• CC 서로 같을 필요가 없는 두 프로그램을 연달아 이어 붙인 것이다.

올해 우리는 Lisp++용 텍스트 뷰어인 Emacs++를 발표하게 되어 기쁘다. Emacs++는 길이가 K인 Lisp++ 프로그램을 한 줄로 길게 표시하고, 그 위에서 커서를 움직일 수 있게 해 준다. 커서는 문자 사이가 아니라 프로그램의 K개 문자 중 하나 위에 항상 놓이는 "블록 커서"다.

어느 시점에서든 커서를 움직이기 위해 다음 세 가지 동작 중 하나를 수행할 수 있다. (i는 커서의 현재 위치이며, 가장 왼쪽이 1이다.)

• 커서를 왼쪽으로 한 글자 이동한다. (커서가 이미 가장 왼쪽 글자 위에 있다면 아무 일도 일어나지 않는다.) 이 동작에는 L_i초가 걸린다.
• 커서를 오른쪽으로 한 글자 이동한다. (커서가 이미 가장 오른쪽 글자 위에 있다면 아무 일도 일어나지 않는다.) 이 동작에는 R_i초가 걸린다.
• i번째 글자인 괄호와(위에서 설명한 규칙에 따라) 매칭되는 괄호로 커서를 순간이동(teleport)한다. 이 동작에는 P_i초가 걸린다.

우리는 Emacs++가 파워 유저에게는 단순할 것이라고 생각하지만, 그 효율이 얼마나 되는지 이해할 필요가 있다. Lisp++ 프로그램 하나와 그 프로그램에 대한 Q개의 질의가 주어진다. 각 질의는 시작 위치 S_j와 끝 위치 E_j로 이루어진다. j번째 질의에 답하려면, 최적으로 움직였을 때 커서를 S_j에서 E_j로 옮기는 데 드는 최소 시간 N_j(초)을 구해야 한다.

모든 N_j 값의 합을 출력하라.