CSP-J/S 2021 第二轮认证 入门级

红太阳幼儿园的小朋友们开始分糖果啦！

红太阳幼儿园有 $n$ 个小朋友，你是其中之一。保证 $n \ge 2$。

有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。

由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 $R$ 块糖回去。

但是拿的太少不够分的，所以你至少要拿 $L$ 块糖回去。保证 $n \le L \le R$。

也就是说，如果你拿了 $k$ 块糖，那么你需要保证 $L \le k \le R$。

如果你拿了 $k$ 块糖，你将把这 $k$ 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 $n$ 块糖果，幼儿园的所有 $n$ 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 $n$ 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。

作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 $n, L, R$，并输出你最多能获得多少作为你搬糖果的奖励的糖果数量。

7 16 23

6

10 14 18

8

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal O(1)$，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

for (int i = 1; i <= n; i++)
    for (int j = i; j >= 2; j--)
        if ( a[j] < a[j-1] ){
            int t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }

这下面是 Pascal 的示范代码：

for i:=1 to n do
    for j:=i downto 2 do
        if a[j]<a[j-1] then
            begin
                t:=a[j];
                a[j]:=a[j-1];
                a[j-1]:=t;
            end;

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 $n$ 的数组 $a$，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1~x~v$：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$。保证 $1 \le x \le n$，$1 \le v \le 10^9$。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

$2~x$：这是第二种操作，假设 H 老师按照上面的伪代码对 $a$ 数组进行排序，你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素，也就是 $a_x$，在排序后的新数组所处的位置。保证 $1 \le x \le n$。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

3 4
3 2 1
2 3
1 3 2
2 2
2 3

1
1
2

TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。

在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机负责加入连接。

需要进行网络连接的计算机共有 $n$ 台，编号为 $1 \sim n$，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。

每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。

一个符合规范的地址串应当具有以下特征：

1. 必须形如 a.b.c.d:e 的格式，其中 $a, b, c, d, e$ 均为非负整数；
2. $0 \le a, b, c, d \le 255$，$0 \le e \le 65535$；
3. $a, b, c, d, e$ 均不能含有多余的前导 $0$。

相应地，不符合规范的地址串可能具有以下特征：

1. 不是形如 a.b.c.d:e 格式的字符串，例如含有多于 $3$ 个字符 . 或多于 $1$ 个字符 : 等情况；
2. 整数 $a, b, c, d, e$ 中某一个或多个超出上述范围；
3. 整数 $a, b, c, d, e$ 中某一个或多个含有多余的前导 $0$。

例如，地址串 192.168.0.255:80 是符合规范的，但 192.168.0.999:80、192.168.00.1:10、192.168.0.1:088、192:168:0:1.233 均是不符合规范的。

如果服务机或客户机在发起操作时提供的地址串不符合规范，这条操作将被直接忽略。

在本问题中，我们假定凡是符合上述规范的地址串均可参与正常的连接，你无需考虑每个地址串的实际意义。

由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生，后一台尝试建立连接的服务机将会无法成功建立连接；除此之外，凡是提供符合规范的地址串的服务机均可成功建立连接。

如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这台服务机；如果找不到这样的服务机，则认为这台客户机无法成功加入连接。

请注意，尽管不允许两台不同的服务机使用相同的地址串，但多台客户机使用同样的地址串，以及同一台服务机同时被多台客户机连接的情况是被允许的。

你的任务很简单：在给出每台计算机的类型以及地址串之后，判断这台计算机的连接情况。

5
Server 192.168.1.1:8080
Server 192.168.1.1:8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.1:99999

OK
FAIL
1
FAIL
ERR

10
Server 192.168.1.1:80
Client 192.168.1.1:80
Client 192.168.1.1:8080
Server 192.168.1.1:80
Server 192.168.1.1:8080
Server 192.168.1.999:0
Client 192.168.1.1:8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.999:0

OK
1
FAIL
FAIL
OK
ERR
ERR
5
1
ERR

小熊的水果店里摆放着一排 $n$ 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 $1, 2, \ldots, n$ 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

12
1 1 0 0 1 1 1 0 1 1 0 0

1 3 5 8 9 11
2 4 6 12
7
10

20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0

1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20