题目背景 小青蛙在打破监狱后,注重身体的锻炼。
他成为了一只运动健将。
他的故事还在继续……
题目描述 这是一道提交答案题。
你的大脑需要被锻炼。
你是一个 bot。你有一个大小为 300 300 的内存条(下标为 1 ∼ 300 1∼300),初始时全为 0 0。每个内存条中存储着一个 32 32 位整数(即 C++ 中的 int)。
你需要构造一个网格图,某些网格上的节点有一个指令,机器人根据指令进行操作和移动。
下文把有指令的节点称作特殊节点。
节点上的指令有如下几种:
增减:将内存条某个位置上的整数增、减 1 1,并向指定的方向移动一步; 比较:比较内存条中下标为 ? , ? i,j 的数的大小,并根据大小向指定方向移动一步; 输入:机器人将从这里出发,并向指定方向移动一步,该节点不应被重复经过; 输出:机器人到达该节点时结束行动并输出指定位置的值。 其中输入、输出节点必须存在且唯一。
任务:
30 , ? 1 , ? 1 … , ? ? − 1 , ? ? − 1 n=30,u 1 ,v 1 …,u n−1 ,v n−1 ,表示由 ? n 个节点, ? − 1 n−1 条边 ? ? , ? ? u i ,v i 组成的树,要求输出给定树的直径长度(定义为树上最长的简单路径所包含的边数),保证 1 ≤ ? ? , ? ? ≤ ? 1≤u i ,v i ≤n。 你需要保证机器人从输入节点出发能到达输出节点,并且中途不会访问到非特殊节点,且移动次数 ≤ 5 × 1 0 7 ≤5×10 7 。
输入格式 无
输出格式 本题使用 Special Judge 判定答案正误。
针对题目给定的 6 6 个任务,你需要分别提交你的输出文件 robot1.out~robot6.out。
对于每个文件,你的输出应为以下格式:
第一行输出两个正整数 ? , ? n,m 表示网格大小为 ? n 行 ? m 列。你需要保证 ? × ? ≤ 1 0 7 n×m≤10 7 。
第二行输出一个正整数 ? k 表示特殊节点数量。其中 1 ≤ ? ≤ ? × ? 1≤k≤n×m。
接下来 ? k 行每行格式如下:
前两个输出的整数 ? , ? x,y 表示特殊节点所在位置为第 ? x 行第 ? y 列,其中 1 ≤ ? ≤ ? , 1 ≤ ? ≤ ? 1≤x≤n,1≤y≤m,且所有 ( ? , ? ) (x,y) 互不相同,接下来按照节点类型输出不同内容:
若为自增节点,则输出 +,自减节点输出 -,并输出一个整数表示自增/自减的内存下标 ? i,其中 1 ≤ ? ≤ 300 1≤i≤300,最后输出一个 LRUD 中的字符表示移动方向(分别对应左右上下,下同)。 若为比较节点,则输出 c,接下来两个整数 ? , ? i,j 表示比较的下标,你需要保证 1 ≤ ? , ? ≤ 300 1≤i,j≤300。最后输出两个 LRUD 中的字符分别表示 ? i 下标中的数大于 ? j 下标中的数时的移动方向和 ? i 下标中的数小于等于 ? j 下标中的数时的移动方向。 若为输入节点则输出 i,并输出一个 LRUD 中的字符表示移动方向。 若为输出节点则输出 o,并输出一个整数 ? p 表示输出大小,接下来 ? p 个 互不相同的整数 ? 1 ∼ ? ? a 1 ∼a p 表示你要输出的内存条中的下标,你需要保证 1 ≤ ? , ? ? ≤ 300 1≤p,a i ≤300。 你需要保证给出的特殊节点中输入、输出节点必须存在且唯一。
输入输出样例 输入 #1复制 输出 #1复制 2 3 4 1 1 i R 1 2 c 1 2 R D 1 3 + 2 L 2 2 o 1 2 说明/提示 上述样例给出了一个读入 ? , ? a,b,输出 max ( ? , ? ) max(a,b) 的程序。
评分方式:若你的输出格式错误或给出结果错误,则获得 0 0 分。否则对于每个测试点,你的得分与 ? × ? n×m 的大小有关。每个测试点有 2 2 个评分参数 ? 1 , ? 2 c 1 ,c 2 ,若你的 ? × ? ≤ ? 1 n×m≤c 1 则获得该测试点满分,否则若 ? 1 < ? × ? ≤ ? 2 c 1 <n×m≤c 2 则获得该测试点 60 % 60% 分数,否则获得 40 % 40% 的分数。
c 2 = pts 1 6 6 9 9 10 10 2 9 9 12 12 15 15 3 9 9 10 10 15 15 4 35 35 48 48 20 20 5 499 499 999 999 20 20 6 3 × 1 0 3 3×10 3
3 × 1 0 5 3×10 5
20 20