빈 문자열을 안정한 상태라고 하자. 비어 있지 않은 문자열에 대해서는 다음과 같이 왼쪽부터 문자를 확인한다.
현재 높이를 으로 둔다. L을 만나면 를 증가시키고, R을 만나면 를 감소시킨다. M은 를 바꾸지 않는다.
문자열이 다음 조건을 모두 만족하면 안정한 상태라고 하자.
M을 확인하는 순간에는 이다.안정한 상태는 정확히 현재 차례의 플레이어가 패배하는 상태이다.
먼저 안정한 상태에서 한 번의 행동으로 다른 안정한 상태로 이동할 수 없음을 보이자.
표식이 L 또는 M인 번 사과를 골라 왼쪽을 가져갔다고 하자. 남는 문자열은 이다. 이 문자열이 안정하려면 원래 문자열의 번째 문자까지 확인한 높이가 이어야 한다. 그러나 이면 그 높이는 양수이고, 이어도 안정한 상태의 정의에 의해 그 높이는 양수이다. 따라서 남은 문자열은 안정하지 않다.
표식이 R 또는 M인 사과를 골라 오른쪽을 가져가는 경우도 대칭적이다. 남는 접두사가 안정하려면 고른 문자 직전의 높이가 이어야 한다. 하지만 R을 높이 에서 읽으면 음수가 되어 안정성에 어긋나고, M을 높이 에서 읽는 것도 허용되지 않는다.
이제 안정하지 않은 상태에서는 한 번의 행동으로 안정한 상태로 이동할 수 있음을 보이자.
왼쪽부터 확인하면서 처음으로 안정성의 지역 조건을 위반하는 위치를 찾는다. 이런 위치가 있다면, 그 문자는 높이 에서 등장한 R 또는 M이다. 그 직전까지의 접두사는 안정한 상태이다. 해당 사과를 고르고 그 사과와 오른쪽의 모든 사과를 가져가면 그 안정한 접두사만 남길 수 있다.
그런 위치가 없는데 전체 문자열을 확인한 뒤 이라면, 문자열을 오른쪽부터 보면서 L과 R의 역할을 서로 바꾸어 같은 논리를 적용한다. 전체 높이가 반대 부호가 되므로 반드시 처음 위반하는 위치가 존재한다. 그 위치의 원래 표식은 L 또는 M이며, 그 사과와 왼쪽의 모든 사과를 가져가면 안정한 접미사만 남길 수 있다.
따라서 안정한 상태에서는 모든 행동이 불안정한 상태로 가고, 불안정한 상태에서는 안정한 상태로 가는 행동이 항상 존재한다. 빈 문자열은 자신의 차례에 패배하는 상태이므로 귀납적으로 안정한 상태가 정확히 패배 상태이다.
각 테스트 케이스에서 문자열을 한 번 순회하며 위 세 조건을 검사하면 된다. 안정한 상태라면 선공인 루루가 패배하므로 Terra, 그렇지 않으면 Lulu를 출력한다.
시간 복잡도는 이고, 추가 공간 복잡도는 이다. 전체 입력에 대해서는 시간에 해결할 수 있다.
Solution written by GPT5.6