¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#10356
Interactivo
Calificación en espera

불균형 방지 20s 1024MB

Problemas

왼쪽 접시와 오른쪽 접시가 있는 특별한 양팔 저울이 있고, 두 접시는 처음에 모두 비어 있다. 또한 서로 동일한 1그램 구슬이 들어 있는 상자가 있다. 구슬은 총 N개이며 1번부터 N번까지 번호가 매겨져 있다.

이 저울은 매우 민감해서, 어느 순간이든 왼쪽 접시의 총 무게와 오른쪽 접시의 총 무게 차이가 1그램을 엄격히 초과하면 저울이 부서진다. 예를 들어 어느 순간 한쪽 접시에 구슬이 4개 있다면, 다른 쪽 접시에는 3개, 4개, 또는 5개의 구슬이 있어야 한다.

친구 리브라(Libra)는 당신에게 다음을 저울을 한 번도 부수지 않고 해 보라고 도전했다:

  • 먼저 1번 구슬, 2번 구슬, ... , N번 구슬 순서대로 모든 구슬을 하나씩 저울 위에 올린다. 각 구슬마다 왼쪽 접시에 올릴지 오른쪽 접시에 올릴지 당신이 선택한다.
  • 그 다음 친구가 정해 준 순서 A1, A2, ..., AN에 따라 구슬을 하나씩 저울에서 모두 제거한다. 이 순서는 1, 2, ..., N의 순열이다. i번째로 제거하는 구슬은 번호가 Ai인 구슬이어야 한다.

이를 수행할 수 있는 방법을 찾아라.


Entrada

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 구슬의 개수 N이 주어진 한 줄로 시작한다. 그 다음 한 줄에 N개의 정수 A1, A2, ..., AN가 주어지며, 이는 처음 N개의 자연수에 대한 순열이다. 제거 단계에서 i번째로 제거해야 하는 구슬은 번호가 Ai인 구슬이다.


Salida

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 길이 N의 문자열이다. (1부터 세었을 때) i번째 문자는 i번 구슬을 왼쪽 접시에 올려야 하면 대문자 L, 오른쪽 접시에 올려야 하면 대문자 R이어야 한다.

적어도 하나의 답이 존재함이 보장된다. 가능한 답이 여러 개라면 그중 아무 것이나 출력해도 된다.


Ejemplo 

2
4
3 1 2 4
4
1 2 3 4
Case #1: LRRL
Case #2: LRLR
샘플 케이스 #1에서는 구슬 1을 왼쪽 접시에, 구슬 2를 오른쪽 접시에, 구슬 3을 오른쪽 접시에, 구슬 4를 왼쪽 접시에 놓는다. 이 과정에서 왼쪽/오른쪽 접시의 총 무게 (1, 0), (1, 1), (1, 2), (2, 2)는 항상 차이가 1을 넘지 않는다. 그 다음 구슬을 3, 1, 2, 4 순서로 제거해야 한다. 이때도 (2, 1), (1, 1), (1, 0), (0, 0)에서 차이는 1을 넘지 않는다. 성공이다! 위와 같은 이유로 RLLR도 이 케이스의 유효한 답이다(두 접시를 바꾼 것뿐). 다음은 이 케이스의 잘못된 답의 예이다: LLRR: 구슬 2를 놓을 때 저울이 깨진다 LRLR: 구슬 1을 제거할 때(두 번째로 제거) 저울이 깨진다 홀수 N 샘플은 없지만(이는 테스트 세트 3에서만 가능함) 다음과 같은 예가 있다: 1: L 또는 R 어느 것이든 가능하다. 2 3 1: LRR과 RLL만 가능하다. LLL, LLR, RRL, RRR은 놓는 단계에서 저울이 깨진다. LRL과 RLR은 제거 단계에서 저울이 깨진다.

Fuente

GCJ 2020iow B

Debes iniciar sesión para escribir código.