310073: CF1779A. Hall of Fame

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Hall of Fame

题意翻译

$\text{Thalia}$ 是一位国际象棋的传奇大师。她有n个奖杯,排成一排,编号从 $1$ 到 $n$(从左到右),每个奖杯旁边都有一盏灯(灯的编号与奖杯的编号一样)。 一盏灯可以指向左边或右边,它照亮那个方向的所有奖杯(但不照亮它旁边的那个)。更正式地说,$\text{Thalia}$ 有一个仅由字符 `L` 和 `R` 组成的字符串 $s$,代表灯的当前方向。 - 如果 $s_i$ 是 `L`,那么这盏灯照亮的奖杯的编号为 $1$,$2$,$\cdots$,$i-1$。 - 如果 $s_i$ 是 `R`,那么这盏灯照亮的奖杯的编号为 $i+1$,$i+2$,$\cdots$,$n$。 她最多可以进行一次以下操作: - 选择一个索引 $i$($1\le i<n$)。 - 调换灯 $i$ 和 $i+1$(不改变其照明的方向)。也就是说,将 $s_i$ 与 $s_{i+1}$ 互换。 $\text{Thalia}$ 要求你照亮她所有的奖杯(使每个奖杯至少被一盏灯照亮),或者告诉她不可能这样做。 如果有可能,你可以选择执行操作或什么都不做。 **注意,灯不能改变方向,只允许调换相邻的灯。** ### 输入 每个测试包含多个测试案例。第一行包含测试用例的数量 $t$($1\le t\le10000$)。 每个测试用例的第一行包含一个正整数 $n$ ($2\le n\le100000$),代表奖杯的数量。 每个测试案例的第二行包含一个长度为 $n$ 的字符串 $s$,仅由字符 `L` 和 `R` 组成。第 $i$ 个字符描述第 $i$ 个灯的方向。 保证所有测试案例的 $n$ 之和不超过 $100000$。 ### 输出 对于每个测试案例,如果不可能通过一个操作(或什么都不做)照亮所有奖杯,则打印 $-1$。否则,如果你选择不执行该操作,则打印 $0$(即通过灯的初始位置照亮奖杯),或者如果你选择交换灯 $i$ 和 $i+1$,则打印索引 $i$($1\le i<n$)。 如果有多个答案,请输出任何一个。

题目描述

Thalia is a Legendary Grandmaster in chess. She has $ n $ trophies in a line numbered from $ 1 $ to $ n $ (from left to right) and a lamp standing next to each of them (the lamps are numbered as the trophies). A lamp can be directed either to the left or to the right, and it illuminates all trophies in that direction (but not the one it is next to). More formally, Thalia has a string $ s $ consisting only of characters 'L' and 'R' which represents the lamps' current directions. The lamp $ i $ illuminates: - trophies $ 1,2,\ldots, i-1 $ if $ s_i $ is 'L'; - trophies $ i+1,i+2,\ldots, n $ if $ s_i $ is 'R'. She can perform the following operation at most once: - Choose an index $ i $ ( $ 1 \leq i < n $ ); - Swap the lamps $ i $ and $ i+1 $ (without changing their directions). That is, swap $ s_i $ with $ s_{i+1} $ . Thalia asked you to illuminate all her trophies (make each trophy illuminated by at least one lamp), or to tell her that it is impossible to do so. If it is possible, you can choose to perform an operation or to do nothing. Notice that lamps cannot change direction, it is only allowed to swap adjacent ones.

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10\,000 $ ). The description of the test cases follows. The first line of each test case contains a positive integer $ n $ ( $ 2 \leq n \leq 100\,000 $ ) — the number of trophies. The second line of each test case contains a string $ s $ of length $ n $ consisting only of characters 'L' and 'R' — the $ i $ -th character describes the direction of the $ i $ -th lamp. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 100\,000 $ .

输出格式


For each test case print $ -1 $ if it is impossible to illuminate all trophies by performing one operation (or doing nothing). Otherwise, print $ 0 $ if you choose not to perform the operation (i.e., the trophies are illuminated by the initial positioning of the lamps), or an index $ i $ ( $ 1 \leq i < n $ ) if you choose to swap lamps $ i $ and $ i+1 $ . If there are multiple answers, print any.

输入输出样例

输入样例 #1

6
2
LL
2
LR
2
RL
2
RR
7
LLRLLLR
7
RRLRRRL

输出样例 #1

-1
1
0
-1
3
6

说明

In the first example, it is possible to swap lamps $ 1 $ and $ 2 $ , or do nothing. In any case, the string "LL" is obtained. Not all trophies are illuminated since trophy $ 2 $ is not illuminated by any lamp — lamp $ 1 $ illuminates nothing and lamp $ 2 $ illuminates only the trophy $ 1 $ . In the second example, it is necessary to swap lamps $ 1 $ and $ 2 $ . The string becomes "RL". Trophy $ 1 $ is illuminated by lamp $ 2 $ and trophy $ 2 $ is illuminated by lamp $ 1 $ , hence it is possible to illuminate all trophies. In the third example, all trophies are initially illuminated — hence, not performing any operation is a valid solution. In the last two examples performing swaps is not necessary as all trophies are illuminated initially. But, the presented solutions are also valid.

Input

题意翻译

$\text{Thalia}$ 是一位国际象棋的传奇大师。她有n个奖杯,排成一排,编号从 $1$ 到 $n$(从左到右),每个奖杯旁边都有一盏灯(灯的编号与奖杯的编号一样)。 一盏灯可以指向左边或右边,它照亮那个方向的所有奖杯(但不照亮它旁边的那个)。更正式地说,$\text{Thalia}$ 有一个仅由字符 `L` 和 `R` 组成的字符串 $s$,代表灯的当前方向。 - 如果 $s_i$ 是 `L`,那么这盏灯照亮的奖杯的编号为 $1$,$2$,$\cdots$,$i-1$。 - 如果 $s_i$ 是 `R`,那么这盏灯照亮的奖杯的编号为 $i+1$,$i+2$,$\cdots$,$n$。 她最多可以进行一次以下操作: - 选择一个索引 $i$($1\le i<n$)。 - 调换灯 $i$ 和 $i+1$(不改变其照明的方向)。也就是说,将 $s_i$ 与 $s_{i+1}$ 互换。 $\text{Thalia}$ 要求你照亮她所有的奖杯(使每个奖杯至少被一盏灯照亮),或者告诉她不可能这样做。 如果有可能,你可以选择执行操作或什么都不做。 **注意,灯不能改变方向,只允许调换相邻的灯。** ### 输入 每个测试包含多个测试案例。第一行包含测试用例的数量 $t$($1\le t\le10000$)。 每个测试用例的第一行包含一个正整数 $n$ ($2\le n\le100000$),代表奖杯的数量。 每个测试案例的第二行包含一个长度为 $n$ 的字符串 $s$,仅由字符 `L` 和 `R` 组成。第 $i$ 个字符描述第 $i$ 个灯的方向。 保证所有测试案例的 $n$ 之和不超过 $100000$。 ### 输出 对于每个测试案例,如果不可能通过一个操作(或什么都不做)照亮所有奖杯,则打印 $-1$。否则,如果你选择不执行该操作,则打印 $0$(即通过灯的初始位置照亮奖杯),或者如果你选择交换灯 $i$ 和 $i+1$,则打印索引 $i$($1\le i<n$)。 如果有多个答案,请输出任何一个。

Output

**名人堂**

**题意翻译**
Thalia 是一位国际象棋的传奇大师。她有n个奖杯,排成一排,编号从 $1$ 到 $n$(从左到右),每个奖杯旁边都有一盏灯(灯的编号与奖杯的编号一样)。

一盏灯可以指向左边或右边,它照亮那个方向的所有奖杯(但不照亮它旁边的那个)。更正式地说,Thalia 有一个仅由字符 `L` 和 `R` 组成的字符串 $s$,代表灯的当前方向。

- 如果 $s_i$ 是 `L`,那么这盏灯照亮的奖杯的编号为 $1$,$2$,$\cdots$,$i-1$。
- 如果 $s_i$ 是 `R`,那么这盏灯照亮的奖杯的编号为 $i+1$,$i+2$,$\cdots$,$n$。

她最多可以进行一次以下操作:

- 选择一个索引 $i$($1\le i<n$)。
- 调换灯 $i$ 和 $i+1$(不改变其照明的方向)。也就是说,将 $s_i$ 与 $s_{i+1}$ 互换。

Thalia 要求你照亮她所有的奖杯(使每个奖杯至少被一盏灯照亮),或者告诉她不可能这样做。

如果有可能,你可以选择执行操作或什么都不做。
**注意,灯不能改变方向,只允许调换相邻的灯。**

**输入输出格式**

**输入格式**
每个测试包含多个测试案例。第一行包含测试用例的数量 $t$($1\le t\le10000$)。

每个测试用例的第一行包含一个正整数 $n$ ($2\le n\le100000$),代表奖杯的数量。

每个测试案例的第二行包含一个长度为 $n$ 的字符串 $s$,仅由字符 `L` 和 `R` 组成。第 $i$ 个字符描述第 $i$ 个灯的方向。

保证所有测试案例的 $n$ 之和不超过 $100000$。

**输出格式**
对于每个测试案例,如果不可能通过一个操作(或什么都不做)照亮所有奖杯,则打印 $-1$。否则,如果你选择不执行该操作,则打印 $0$(即通过灯的初始位置照亮奖杯),或者如果你选择交换灯 $i$ 和 $i+1$,则打印索引 $i$($1\le i<n$)。

如果有多个答案,请输出任何一个。

**输入输出样例**

**输入样例 #1**
```
6
2
LL
2
LR
2
RL
2
RR
7
LLRLLLR
7
RRLRRRL
```
**输出样例 #1**
```
-1
1
0
-1
3
6
```

**说明**
在第一个例子中,可以交换灯 $ 1 $ 和 $ 2 $,或者什么都不做。无论如何,得到的字符串都是 "LL"。由于奖杯 $ 2 $ 没有被任何灯照亮——灯 $ 1 $ 没有照亮任何奖杯,灯 $ 2 $ 只照亮了奖杯 $ 1 $,所以并不是所有的奖杯都被照亮了。

在第二个例子中,需要交换灯 $ 1 $ 和 $ 2 $。字符串变为 "RL"。奖杯 $ 1 $ 被灯 $ 2 $ 照亮,奖杯 $ 2 $ 被灯 $ 1 $ 照亮,因此可以照亮所有的奖杯。

在第三个例子中,所有的奖杯都是最初被照亮的——因此,不执行任何操作是一个有效的解决方案。

在最后两个例子中,执行交换并不是必须的,因为所有的奖杯最初都是被照亮的。但是,给出的解决方案也是有效的。**名人堂** **题意翻译** Thalia 是一位国际象棋的传奇大师。她有n个奖杯,排成一排,编号从 $1$ 到 $n$(从左到右),每个奖杯旁边都有一盏灯(灯的编号与奖杯的编号一样)。 一盏灯可以指向左边或右边,它照亮那个方向的所有奖杯(但不照亮它旁边的那个)。更正式地说,Thalia 有一个仅由字符 `L` 和 `R` 组成的字符串 $s$,代表灯的当前方向。 - 如果 $s_i$ 是 `L`,那么这盏灯照亮的奖杯的编号为 $1$,$2$,$\cdots$,$i-1$。 - 如果 $s_i$ 是 `R`,那么这盏灯照亮的奖杯的编号为 $i+1$,$i+2$,$\cdots$,$n$。 她最多可以进行一次以下操作: - 选择一个索引 $i$($1\le i<n$)。 - 调换灯 $i$ 和 $i+1$(不改变其照明的方向)。也就是说,将 $s_i$ 与 $s_{i+1}$ 互换。 Thalia 要求你照亮她所有的奖杯(使每个奖杯至少被一盏灯照亮),或者告诉她不可能这样做。 如果有可能,你可以选择执行操作或什么都不做。 **注意,灯不能改变方向,只允许调换相邻的灯。** **输入输出格式** **输入格式** 每个测试包含多个测试案例。第一行包含测试用例的数量 $t$($1\le t\le10000$)。 每个测试用例的第一行包含一个正整数 $n$ ($2\le n\le100000$),代表奖杯的数量。 每个测试案例的第二行包含一个长度为 $n$ 的字符串 $s$,仅由字符 `L` 和 `R` 组成。第 $i$ 个字符描述第 $i$ 个灯的方向。 保证所有测试案例的 $n$ 之和不超过 $100000$。 **输出格式** 对于每个测试案例,如果不可能通过一个操作(或什么都不做)照亮所有奖杯,则打印 $-1$。否则,如果你选择不执行该操作,则打印 $0$(即通过灯的初始位置照亮奖杯),或者如果你选择交换灯 $i$ 和 $i+1$,则打印索引 $i$($1\le i<n$)。 如果有多个答案,请输出任何一个。 **输入输出样例** **输入样例 #1** ``` 6 2 LL 2 LR 2 RL 2 RR 7 LLRLLLR 7 RRLRRRL ``` **输出样例 #1** ``` -1 1 0 -1 3 6 ``` **说明** 在第一个例子中,可以交换灯 $ 1 $ 和 $ 2 $,或者什么都不做。无论如何,得到的字符串都是 "LL"。由于奖杯 $ 2 $ 没有被任何灯照亮——灯 $ 1 $ 没有照亮任何奖杯,灯 $ 2 $ 只照亮了奖杯 $ 1 $,所以并不是所有的奖杯都被照亮了。 在第二个例子中,需要交换灯 $ 1 $ 和 $ 2 $。字符串变为 "RL"。奖杯 $ 1 $ 被灯 $ 2 $ 照亮,奖杯 $ 2 $ 被灯 $ 1 $ 照亮,因此可以照亮所有的奖杯。 在第三个例子中,所有的奖杯都是最初被照亮的——因此,不执行任何操作是一个有效的解决方案。 在最后两个例子中,执行交换并不是必须的,因为所有的奖杯最初都是被照亮的。但是,给出的解决方案也是有效的。

加入题单

上一题 下一题 算法标签: