侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【算法竞赛】2021 RoboCom 世界机器人开发者大赛-高职组(决赛)

GabrielxD
2022-08-04 / 0 评论 / 0 点赞 / 60 阅读 / 5,765 字 / 正在检测是否收录...

7-1 小偷踩点

s.jpg

俗话说不怕贼偷,就怕贼惦记。

小偷在作案前有时会在居民家的门、墙上做一些标记,每一种记号代表一个含义,一般人看不懂,但同行一看便知道这个家庭的情况。不过派出所干警也不是吃素的,很快破译了这些记号的含义(如上图),并且在辖区内广为张贴,告知居民。

随后小偷们又改变了方法,将这些记号从 1 到 N 编号,然后将这些编号按照某种规则重新打乱再做标记,标记变成了一串数字。不过这种新的编号方法又被破译了!干警们发现这些数字的规律可以用一个二维矩阵来表示:矩阵有 10 列,顺序对应数字 0 到 9;矩阵一般不超过 10 行,每行对应一个 0 到 9 之间的数字,这些数字保证不重复。小偷的新标记由若干个两位数组成,每个数字的十位对应行、个位对应列,而对应位置上的数字就是原始标记的编号。

如上图 40 种标记从上到下、从左到右顺序编号后,按下图所示的规律打乱,则如果我们看到标记“71”,就是行标记为 7,列标记为 1 的单元格对应的数字 11,对应原始标记中第 11 个,即“很有钱”。那么标记“71 78 57”就表示原始标记的第 11、8、7 号,意思是“很有钱”、“没有防范”、“计划行动”。

table.JPG

本题就请你编写程序,自动破译小偷的新标记。

输入格式:

输入第一行给出 2 个正整数:N(≤100)为小偷的原始标记个数,M(≤10)为新标记对照矩阵的行数。

随后 N 行,第 i 行给出第 i 个标记的解释,由不超过 100 个英文字母和空格组成。

接下来一行给出 M 个数字,为 0 到 9 之间的数字,保证不重复,其中第 i 个数对应矩阵第 i 行。

接下来 M 行,每行给出 10 个数字,或者是 1 到 N 之间的一个编号,或者是 −1 表示没有对应的编号。

最后一行给出小偷留在墙上的数字标记,格式为:

k t[1] ... t[k]

其中 k 是数字个数(不超过 N),后面跟着 k 个数字。

输出格式:

对小偷留下的每个数字,在一行中输出其对应的意义,顺序与输入顺序相同。如果没有对应的意义,则在对应行中输出 ?

输入样例:

10 2
jia li you ren
kong fang zi
jia you e gou
dan shen
hen you qian
xiao xin lin ju
you bao jing qi
jin kuai dong shou
xia ci zai lai
bu bi jin ru
6 2
-1 6 5 1 -1 10 3 4 -1 9
2 4 7 -1 3 -1 5 -1 8 2
5 20 64 61 22 13

输出样例:

kong fang zi
?
xiao xin lin ju
you bao jing qi
?

解题:模拟 哈希表

思路

把对应数据输入数组和二维数组中后通过哈希表建立关系然后查找。注意如果二维数组开的比较大,要把所有元素初始化为 0,然后在最后做判断哪些是没有数据的。

代码
#include <iostream>
#include <limits>

using namespace std;

int main() {
    int N, M, mat[10][10] = {0};
    scanf("%d%d", &N, &M);
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    string marks[N + 1];
    for (int i = 1; i <= N; ++i) getline(cin, marks[i]);
    int row_nums[M];
    for (int i = 0; i < M; ++i) scanf("%d", &row_nums[i]);
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < 10; ++j) {
            scanf("%d", &mat[row_nums[i]][j]);
        }
    }
    int k;
    scanf("%d", &k);
    int num, idx;
    while (k--) {
        scanf("%d", &num);
        idx = mat[num / 10][num % 10];
        if (idx <= 0) printf("?\n");
        else printf("%s\n", marks[idx].c_str());
    }

    return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(Reader.next());
        int M = Integer.parseInt(Reader.next());
        String[] marks = new String[N + 1];
        for (int i = 1; i <= N; i++) marks[i] = Reader.nextLine();
        int[] rows = new int[M];
        for (int i = 0; i < M; i++) rows[i] = Integer.parseInt(Reader.next());
        int[][] map = new int[10][10];
        for (int row : rows) {
            for (int i = 0; i < 10; i++) {
                map[row][i] = Integer.parseInt(Reader.next());
            }
        }
        int k = Integer.parseInt(Reader.next());
        while (k-- > 0) {
            // 取字符的方式会出错
//            String numStr = Reader.next();
//            int r = numStr.charAt(0) - '0';
//            int c = numStr.charAt(1) - '0';
            int num = Integer.parseInt(Reader.next());
            int r = num / 10, c = num % 10;
            int idx = map[r][c];
            System.out.println(idx < 1 ? '?' : marks[idx]);
        }
    }

    static class Reader {
        static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer st = new StringTokenizer("");

        static String next() throws IOException {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(BR.readLine());
            }
            return st.nextToken();
        }

        static String nextLine() throws IOException {
            return BR.readLine();
        }
    }
}

7-2 盲盒包装流水线

众所周知,PAT 有 9 枚徽章,分别对应青铜、白银、黄金、白金、钻石、大师、王者、大圣、天神这 9 个段位,只有成绩非常优秀的考生才有资格获得刻有自己名字的徽章。现在,PAT 制作了徽章的小型纪念版,要制成盲盒给大家玩了!

下图是一条盲盒包装流水线的示意图。首先徽章通过进货口被压入货栈里,空盒在履带上从左向右传送。每次从货栈里弹出一枚徽章,进入打包机,装入一只空盒,打包后继续向右边传送。当货栈为空时,打包机会暂停,等待下一批徽章压入货栈。

lsx.png

每只盒子都有一个编号,小拼姐姐手里有进入流水线的空盒编号顺序表,也有每一批送往货栈的徽章顺序表,这样她其实可以知道每只盒子里装了哪种徽章。有些小朋友收到了盲盒,就想在拆封前问无所不知的小拼姐姐,盒子里的徽章是哪一种。但是因为盲盒总量有 105 这么多,小拼姐姐可记不住每只盒子里装的是什么,于是你就被请来写个程序帮小拼姐姐回复这种信息。

输入格式:

输入第一行给出 2 个正整数,分别为盲盒总量 N(≤105)和货栈容量 S(≤100)。接下来一行给出 N 只盒子的编号,编号由 5 位数字组成,给出的顺序是空盒进入传送带的顺序。随后 N/S(保证是整数)行,每行给出一批 S 枚徽章的类型,为 1-9 的数字,给出的顺序是从进货口入栈的顺序。

再下面给出一个正整数 K(≤104),为查询次数。随后 K 行,每行给出一个 5 位编号。

输出格式:

对每个查询编号,在一行中输出该盒子中装的徽章类型。如果编号是错误的,则在一行中输出 Wrong Number

输入样例:

10 5
00132 10093 92001 23333 66666 88888 09009 34658 82750 69251
1 2 3 4 5
9 8 7 6 1
5
66666
88888
69251
55555
10093

输出样例:

1
1
9
Wrong Number
4

解题:模拟 哈希表

思路

S 个勋章要倒序放入对应的盒子,所以可以从第 S 个盒子放到第 1 个 盒子,从第 2*S 个盒子放到第 S+1 个盒子…依此类推维护一个哈希表,然后从哈希表中查出来输出。

代码
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int N, S;
    scanf("%d%d", &N, &S);
    int boxes[N];
    for (int i = 0; i < N; ++i) scanf("%d", &boxes[i]);
    unordered_map<int, int> mp;
    int rows = N / S;
    for (int i = 0; i < rows; i++) {
        for (int j = (i + 1) * S - 1; j >= i * S; --j) {
            scanf("%d", &mp[boxes[j]]);
        }
    }
    int K, k;
    scanf("%d", &K);
    while (K--) {
        scanf("%d", &k);
        if (mp.count(k)) printf("%d\n", mp[k]);
        else printf("Wrong Number\n");
    }

    return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(Reader.next());
        int S = Integer.parseInt(Reader.next());
        String[] nums = new String[N];
        for (int i = 0; i < N; i++) nums[i] = Reader.next();
        int idx = S - 1;
        Map<String, String> map = new HashMap<>();
        for (int i = 0; i < N / S; i++) {
            for (int j = idx; j >= i * S; j--) {
                map.put(nums[j], Reader.next());
            }
            idx += S;
        }
        int K = Integer.parseInt(Reader.next());
        while (K-- > 0) {
            System.out.println(map.getOrDefault(Reader.next(), "Wrong Number"));
        }
    }

    static class Reader {
        static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer st = new StringTokenizer("");

        static String next() throws IOException {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(BR.readLine());
            }
            return st.nextToken();
        }

        static String nextLine() throws IOException {
            return BR.readLine();
        }
    }
}

7-3 到底爱不爱我

love.JPG

古代少女有了心上人时,会悄悄折一条树枝,揪那枝上的叶子,揪一片叶子念一句“爱我”,再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候,看看是停在“爱”还是“不爱”。

但聪明的慧娘一眼洞穿,只要数一下叶子有多少片,根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始,就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫,理科生杀死浪漫。

于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”:

  • “专情枝”:是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候,这根枝条的根部才传出“爱”;否则树枝根部传出的是“不爱”。
  • “博爱枝”:也是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候,这根枝条的根部才传出“不爱”;否则树枝根部传出的都是“爱”。
  • “情变枝”:是没有分岔的一根直枝,如果一端接到“爱”,另一端必须传出“不爱”;反之如果一端接到“不爱”,另一端则会传出“爱”。

慧娘将这些树枝摆放在院子里,布了一个“情阵”,先选一根特殊的枝条作为初试一枝,从这枝条的根部开始,扩散开去,令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来,在初始一枝的根部,她能得到“爱”还是“不爱”?

输入格式:

输入在第一行中给出正整数 N(≤30),是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行,第 i 行给出第 i 枝的描述,格式为

类型 左分枝连接的编号 右分枝连接的编号

其中 类型 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝,则后面跟的是其唯一末端连接的情枝编号,并没有两个分枝的信息。如果一个分枝是末梢,并没有连接其它枝条,则对应编号为 0。

接下来一行中给出正整数 K(≤30),是慧娘询问的次数。以下 K 行,每行给出一个由 01 组成的字符串,其中 0 表示“不爱”,1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。(注意:“从左到右”的意思是,我们从初试一枝出发去遍历所有枝条的末梢时,总是遵循先遍历左边情阵、再遍历右边情阵的顺序)

输出格式:

对慧娘的每个询问,如果她在初始一枝的根部能得到“爱”,就输出 Ai;否则输出 BuAi

输入样例:

6
2 6 4
1 0 0
3 1
2 0 0
3 0
1 5 2
5
11111
00000
11100
10011
01100

输出样例:

BuAi
Ai
Ai
BuAi
BuAi

样例说明:

样例对应的情阵以及慧娘第 3 问的情势如图所示,其中完整的心对应 1,裂开的心对应 0

sample.jpg

解题:二叉树 DFS 队列

思路

见 Java 代码注释。第 1、7 个测试点没过。

image-20220804061412210

代码
#include <iostream>
#include <limits>
#include <queue>

using namespace std;

struct LoveNode {
    int type = 0;
    LoveNode* left;
    LoveNode* right;

    friend ostream& operator<<(ostream& os, const LoveNode& node) {
        os << "type: " << node.type << " left: " << node.left << " right: " << node.right;
        return os;
    }
};

queue<bool> que;

bool dfs(LoveNode* node) {
    if (!node) {
        bool front = que.front();
        que.pop();
        return front;
    }
    switch (node->type) {
        case 3: return !dfs(node->left);
        case 2: return dfs(node->left) | dfs(node->right);
        case 1: return dfs(node->left) & dfs(node->right);
    }
    return false;
}

int main() {
    int N;
    scanf("%d", &N);
    LoveNode nodes[N];
    LoveNode* root = nullptr;
    int type, left, right;
    LoveNode* node;
    for (int i = 0; i < N; ++i) {
        scanf("%d", &type);
        node = &(nodes[i].type ? nodes[i] : (nodes[i] = LoveNode()));
        node-> type = type;
        scanf("%d", &left);
        --left;
        if (type == 3) right = -1;
        else {
            scanf("%d", &right);
            --right;
        }
        if (left != -1) {
            node->left = &(nodes[left].type ?
                    nodes[left] : (nodes[left] = LoveNode()));
        }
        if (right != -1) {
            node->right = &(nodes[right].type ?
                    nodes[right] : (nodes[right] = LoveNode()));
        }
        if (!i || (node->left && node->left == root ||
            node->right && node->right == root)) root = node;
    }
    int K;
    scanf("%d", &K);
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    string line;
    while (K--) {
        getline(cin, line);
        for (const char& ch : line) que.push(ch != '0');
        printf(dfs(root) ? "Ai\n" : "BuAi\n");
    }

    return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    // 队列用于存在末梢写下的 "爱" 或 "不爱" (正序入队)
    static Queue<Boolean> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(Reader.next());
        // 数组当成哈希表用: *索引*代表题目中的`编号-1`, *元素*存树的节点
        LoveNode[] nodes = new LoveNode[N];
        LoveNode root = null;
        for (int i = 0; i < N; i++) {
            int type = Integer.parseInt(Reader.next());
            // 如果当前索引对应的节点在数组中不为 null 说明已经在之前已经遍历到了该节点的父节点
            // 父节点已经为其创建好节点对象了 直接取就行, 否则创建一个新节点并存入数组对应位置
            LoveNode node = nodes[i] == null ? (nodes[i] = new LoveNode()) : nodes[i];
            // 修改当前节点的类型: 1: 专情(与), 2: 博爱(或), 3: 情变(非)
            node.type = type;
            // 左子节点索引 = 左子节点编号-1
            int left = Integer.parseInt(Reader.next()) - 1;
            // 右子节点索引 = 右子节点编号-1
            // 这里表示: 如果该节点是*情变*节点那么它只有左节点(输入获取不到右节点) 否则正常赋值
            int right = type == 3 ? -1 : Integer.parseInt(Reader.next()) - 1;
            // left 或 right 为 -1 表示左子节点或右子节点不存在
            if (left != -1) {
                // 和之前一样, 如果左子节点在数组中已经有了就直接取, 否则新建并放入数组
                node.left = nodes[left] == null ?
                        (nodes[left] = new LoveNode()) : nodes[left];
            }
            if (right != -1) {
                // 同上
                node.right = nodes[right] == null ?
                        (nodes[right] = new LoveNode()) : nodes[right];
            }
            // 维护一个根节点, 如果左子节点或者右子节点是当前根节点, 那么当前节点成为新的根节点
            if (i == 0 || (node.left != null && node.left == root ||
                    node.right != null && node.right == root)) root = node;
        }
        int K = Integer.parseInt(Reader.next());
        // 处理慧娘的 K 次查询
        while (K-- > 0) {
            // 这里清空队列可要可不要, 因为如果数据严格符合要求的话, 每一次查询都会正好把队列中的元素全取出来
//            queue.clear();
            // 把从左到右写下的 "爱" 或 "不爱" 依次入队
            for (char ch : Reader.nextLine().toCharArray()) {
                // 放入 true 表示写下 "爱", 放入 false 表示写下 "不爱"
                // 输入 '0': ch != '0' => false => "不爱"
                // 输入 '1': ch == '0' => true => "爱"
                queue.offer(ch != '0');
            }
            // 布尔值表示的意思同上
            System.out.println(dfs(root) ? "Ai" : "BuAi");
        }

    }

    static boolean dfs(LoveNode node) {
        // 如果当前节点为空说明递归到了 “末梢的枝杈” 应该 “在旁随意写下‘爱’或‘不爱’”
        // 也就把队列中队头元素出队然后返回
        // 返回值可以换成 Boolean.TRUE.equals(queue.poll()) 更为保险, 但如果测试数据足够严格是不需要的
        // 因为如果测试数据少了的话, 某次递归到这里会发现队列为空, 然后返回了个 null, 于是出错
        if (node == null) return queue.poll();
        switch (node.type) {
            // 如果连接当前节点的为情变枝, 对唯一的子节点取反并返回
            case 3: return !dfs(node.left);
            // 如果连接当前节点的为博爱枝, 对其左右子节点进行按位或并返回
            // 注意: 一定要先递归左子节点再递归右子节点, 虽然递推出去计算爱的时候没有顺序
            // 但递归进去的时候需要 “从左到右” (类似前序遍历)
            // 注意2: 一定要用按位或(|)而非短路或(||), 如果短路了的话会直接少一次递归, 从队列中取出的顺序就全乱了
            case 2: return dfs(node.left) | dfs(node.right);
            // 如果连接当前节点的为专情枝, 对其左右子节点进行按位与并返回
            case 1: return dfs(node.left) & dfs(node.right);
        }
        return false; // 忽略掉
    }

    static class LoveNode {
        int type;
        LoveNode left, right;
    }

    static class Reader {
        static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer st = new StringTokenizer("");

        static String next() throws IOException {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(BR.readLine());
            }
            return st.nextToken();
        }

        static String nextLine() throws IOException {
            return BR.readLine();
        }
    }
}

7-4 皆大欢喜

miao.JPG

喵星人素以有个性著称,铲屎官很难用一种玩具让家里所有的喵主子都高兴起来。于是铲屎官调研了一下各种玩具,记录下每种玩具能让哪些喵高兴、同时让哪些喵生气、另外还有哪些喵无感。现在铲屎官来向你求助,请你告诉他如何用最少的玩具,让所有的喵都高兴起来。

注意:如果一只喵处于高兴的状态,那么它会一直高兴着,直到见到让它生气的玩具;同样地,如果喵不高兴,它会一直不高兴,直到见到让它高兴的玩具。如果一样玩具令喵无感,则不会改变它原来的状态。

输入格式:

输入第一行给出两个正整数,分别是 N (≤10),为喵的个数;以及 M(≤10),为玩具的个数(假设玩具从 1 到 M 编号)。随后 M 行,每行对应一种玩具,顺序给出 N 只喵的状态:1 表示高兴,-1 表示生气,0 表示无感。

输出格式:

假设初始状态下没有玩具,所有喵都不高兴。在一行中给出逗喵玩具的编号顺序,使得按这个顺序把玩具给喵,能令所有的喵都高兴起来。要求输出最少玩具的解。当这种解不唯一时,输出最小编号序列。题目保证存在解。一行中的数字以 1 个空格分隔,行首尾不得有多余空格。

序列 { a1,a2,…,an } 小于序列 { b1,b2,…,b**n } 的定义是:存在 1≤k<n 使得对所有 i<kai=bi,并且 ak<bk

输入样例:

3 4
-1 1 0
1 1 -1
0 -1 1
1 0 0

输出样例:

3 1 4

解题:DFS

思路

爆搜 + 剪枝。

代码
#include<iostream>

using namespace std;
int N, M;
const int MAX_N = 11;
int used[MAX_N];
int states[MAX_N];
int toys[MAX_N][MAX_N];
int serials[MAX_N], cnt;
int ans[MAX_N], mn = 0x3f3f3f3f;

bool check() {
    for (int i = 0; i < N; ++i)
        if (states[i] != 1) return false;
    return true;
}

void update(int idx) {
    for (int i = 0; i < N; ++i) {
        const int& state = toys[idx][i];
        if (!state) continue;
        states[i] = state;
    }
}

bool dfs(int toy) {
    int backtrace[MAX_N];
    copy(begin(states), end(states), begin(backtrace));
    update(toy);
    used[toy] = true;
    serials[cnt++] = toy;
    if (check()) {
        if (cnt < mn) {
            mn = cnt;
            copy(begin(serials), end(serials), begin(ans));
        }
    }
    for (int i = 0; i < M; ++i) {
        if (!used[i]) {
            used[i] = 1;
            if (dfs(i)) return true;
            used[i] = 0;
        }
    }
    used[toy] = 0;
    copy(begin(backtrace), end(backtrace), begin(states));
    --cnt;
    return false;
}

int main() {
    fill(states, states + N, -1);
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &toys[i][j]);
        }
    }
    for (int i = 0; i < M; ++i) dfs(i);
    for (int i = 0; i < mn; ++i) {
        if (i) printf(" ");
        printf("%d", ans[i] + 1);
    }
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static int N, M;
    static int[][] toys;
    static int[] states;
    static boolean[] used;
    static List<Integer> serials, ans;

    public static void main(String[] args) throws IOException {
        N = Reader.nextInt();
        M = Reader.nextInt();
        states = new int[N];
        toys = new int[M][N];
        used = new boolean[M];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                toys[i][j] = Reader.nextInt();
            }
        }
        Arrays.fill(states, -1);
        serials = new ArrayList<>();
        for (int i = 0; i < M; i++) dfs(i);
        StringBuilder sb = new StringBuilder();
        for (int i : ans) sb.append(' ').append(i + 1);
        System.out.println(sb.substring(1));
    }

    static void dfs(int toy) {
        if (ans != null && serials.size() == ans.size()) return;
        int[] backtrace = new int[N];
        System.arraycopy(states, 0, backtrace, 0, N);
        update(toy);
        serials.add(toy);
        used[toy] = true;
        if (check()) {
            if (ans == null || serials.size() < ans.size()) {
                ans = new ArrayList<>(serials);
            }
        }
        for (int i = 0; i < M; i++) {
            if (!used[i]) dfs(i);
        }
        used[toy] = false;
        System.arraycopy(backtrace, 0, states, 0, N);
        serials.remove(serials.size() - 1);
    }

    static boolean check() {
        for (int state : states) {
            if (state != 1) return false;
        }
        return true;
    }

    static void update(int idx) {
        for (int i = 0; i < N; i++) {
            int state = toys[idx][i];
            if (state == 0) continue;
            states[i] = state;
        }
    }

    static class Reader {
        static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        static final StreamTokenizer ST = new StreamTokenizer(BR);

        static String next() throws IOException {
            ST.nextToken();
            return ST.sval;
        }

        static double nextDouble() throws IOException {
            ST.nextToken();
            return ST.nval;
        }

        static int nextInt() throws IOException {
            return (int) nextDouble();
        }
    }
}
0

评论区