下载文档原格式
第一题题库NOIP20071．统计数字(count.pas/c/cpp)【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。
已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
【输入】输入文件count.in包含n+1行：第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。
每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
【输入输出样例】【限制】40%的数据满足：1<=n <=100080%的数据满足：1<=n <=50000100%的数据满足：1<=n <=200000，每个数均不超过1 500 000 000（1.5*109）NOIP20081. 笨小猴(wird.pas/c/cpp)【问题描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。
但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn 是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn 是一个质数，那么笨小猴就认为这是个Lucky Word ，这样的单词很可能就是正确的答案。
【输入】输入文件word.in 只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
【输出】输出文件word.out 共两行，第一行是一个字符串，假设输入的的单词是Lucky Word ，那么输出“Lucky Word ”，否则输出“No Answer ”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn 的值，否则输出0。
CCF 全国信息学奥林匹克联赛（NOIP2017）复赛提高组 day1（请选手务必仔细阅读本页内容）1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存 4G，上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、提交的程序代码文件的放置位置请参照各省的具体要求。
6、特别提醒：评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。
1．小凯的疑惑(math.cpp/c/pas)小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。
每种金币小凯都有无数个。
在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。
现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。
【输入格式】输入文件名为math.in。
输入数据仅一行，包含两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯手中金币的面值。
【输出格式】输出文件名为math.out。
输出文件仅一行，一个正整数 N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。
【输入输出样例 1】math/math1.in math/math1.ans【输入输出样例 1 说明】小凯手中有面值为3 和7 的金币无数个，在不找零的前提下无法准确支付价值为1、2、4、5、8、11 的物品，其中最贵的物品价值为 11，比 11 贵的物品都能买到，比如：12 = 3 * 4 + 7 * 013 = 3 * 2 + 7 * 114 = 3 * 0 + 7 * 215 = 3 * 5 + 7 * 0……【输入输出样例 2】见选手目录下的math/math2.in 和math/math2.ans。
第十二届全国信息学奥林匹克分区联赛（NOIP2006）复赛试题（提高组竞赛用时：3小时）关于竞赛中不同语言使用限制的说明一．关于使用Pascal语言与编译结果的说明1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。
2．允许使用数学库(uses math子句)，以及ansistring。
但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
二．关于C++语言中模板使用的限制说明1．允许使用的部分：标准容器中的布尔集合，迭代器，串，流。
相关的头文件：<bitset > <iterator > <string > <iostream >2．禁止使用的部分：序列：vector，list，deque序列适配器：stack, queue, priority_queue 关联容器：map, multimap, set, multiset 拟容器：valarray 散列容器：hash_map, hash_set, hash_multimap, hash_multiset 所有的标准库算法相关头文件：<vector > <list > <deque > <stack > <map > <set > <algorithm >1．能量项链(energy.pas/c/cpp)【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。
在项链上有N颗能量珠。
能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。
并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。
因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。
贵州贵州第二十二届全国青少年信息学奥林匹克联赛初赛提高组C++语言试题竞赛时间：2016年10月22日14:30~16:30选手注意：● 试题纸共有13页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上的一律无效。
● 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）1. 以下不是微软公司出品的软件是（ ）。
A. Powerpoint B. Word C. Excel D. Acrobat Reader2. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock 、字母键A 、字母键S 和字母键D 的顺序来回按键，即CapsLock 、A 、S 、D 、S 、A 、CapsLock 、A 、S 、D 、S 、A 、CapsLock 、A 、S 、D 、S 、A 、……，屏幕上输出的第81个字符是字母（ ）。
A. A B. S C. D D. a3. 二进制数00101100和01010101异或的结果是（ ）。
A. 00101000 B. 01111001 C. 01000100 D. 001110004. 与二进制小数0.1相等的八进进制数是（ ）。
A. 0.8 B. 0.4 C. 0.2 D. 0.15. 以比较作为基本运算，在N 个数中找最小数的最少运算次数为（ ）。
A. N B. N-1 C. N 2 D. log N6. 表达式a*(b+c)-d 的后缀表达形式为（ ）。
A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd7. 一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。
如果没有左孩子或者右孩子，则对应的为空指针。
那么该链表中空指针的数目为（ ）。
A. 6 B. 7 C. 12 D.14贵州贵州8. G 是一个非连通简单无向图，共有28条边，则该图至少有（ ）个顶点。
Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。
一共有n 张地毯，编号从1 到n。
现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。
注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】输入文件名为 carpet.in。
输入共 n+2 行。
第一行，一个整数 n，表示总共有n 张地毯。
接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。
第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。
【输出】输出文件名为 carpet.out。
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。
【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。
【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。
【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。
【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。
置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。
注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。
CCF 全国信息学奥林匹克联赛（NOIP2015）复赛提高组day2（请选手务必仔细阅读本页内容）一．题目概况二．提交源程序文件名三．编译命令（不包含任何优化开关）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，内存 4G，上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、特别提醒：评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。
1．跳石头(stone.cpp/c/pas)【问题描述】一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。
组委会已经选择好了两块岩石作为比赛起点和终点。
在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。
在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。
由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
【输入格式】输入文件名为 stone.in。
输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数 Di（0 < Di < L）表示第 i 块岩石与起点的距离。
这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
【输出格式】输出文件名为 stone.out。
输出文件只包含一个整数，即最短跳跃距离的最大值。
【输入输出样例 1 说明】将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点）。
第22届全国青少年信息学奥林匹克联赛2016提高组（复赛）第一试竞赛时间：2016年11月19日8:30 〜12:00提交源程序文件名1. 文件名（程序名和输入输出文件名）必须使用英文小写。
2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。
3. 中函数（）的返回值类型必须是，程序正常结束时的返回值必须是0。
4. 全国统一评测时采用的机器配置为：（）x2 240 , 2.8 ,内存4G,上述时限以此配置为准。
5. 只提供格式附加样例文件。
6. 评测在下进行。
7. 编译时不打开任何优化选项。
玩具谜题（）【问题描述】小南有一套可爱的玩具小人，它们各有不同的职业。
有一天，这些玩具小人把小南的眼镜藏了起来。
小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。
如下图：这时告诉小南一个谜题：“眼镜藏在我左数第3个玩具小人的右数第1个玩具小人的左数第2个玩具小人那里。
”小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。
小南一边艰难地辨认着玩具小人，一边数着：“朝内，左数第3个是。
“朝外，右数第1个是。
“朝外，左数第2个是。
“所以眼镜藏在这里！”虽然成功找回了眼镜，但小南并没有放心。
如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。
所以小南希望你写程序帮他解决类似的谜题。
这样的谜题具体可以描述为：有n个玩具小人围成一圈，己知它们的职业和朝向。
现在第1个玩具小人告诉小南一个包含m条指令的谜题，其中第i条指令形如“左数/ 右数第个玩具小人”。
你需要输出依次数完这些指令后，到达的玩具小人的职业。
【输入格式】从文件中读入数据。
输入的第一行包含两个正整数，表示玩具小人的个数和指令的条数。
接下来n行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。
NOIP 2016 Day 1 题解Sengxian＇s Blog先声明一下，如果你是初学者，你可能会看不懂其中的一些东西，原因是你的知识点以及技巧没有跟上，我会尽量写得详细一点，如果还有不懂，欢迎留言。
玩具谜题toy知识点模拟分析可以发现，本题就是根据要求在环上顺时针或者逆时针走动，那么假设当前的位置是ppp，那么逆时针走xxx 个到达的位置是(p?1 x)modn 1(p - 1 x) \bmod n 1(p?1 x)modn 1，顺时针走xxx 个到达的位置是(p?1?x)modn 1(p - 1 - x) \bmod n 1(p?1?x)modn 1。
模拟每一次的指令，判断每次是走顺时针还是逆时针即可。
实现上要注意，C 中对于模运算的定义与数学中的模运算是不同的，我们知道在数学上amodb=a?b??ab?a \bmod b = a - b\cdot\lfloor \frac a b\rflooramodb=a?b???b??a???，问题就在于?ab?\lfloor\frac a b\rfloor??b??a??? 的计算上。
在大部分编译器中，两个int 相除，是直接丢弃小数位得到答案的，这就导致了在C 中两个int 相除并非总是得到?ab?\lfloor\frac a b\rfloor??b??a???（例如?32=?1\frac {-3} 2 = -1?2???3??=?1），所以aaa 为负数的情况下，取模会存在问题，amodba \bmod bamodb 不一定能够得到一个非负整数，但是我们可以保证这个数在(?∣b∣,∣b∣)(-\vert b\vert,\vert b\vert)(?∣b∣,∣b∣) 内，在所以实际需要取模的时候，采用((amodb) b)modb((a \bmod b) b) \bmod b((amodb)b)modb 来得到非负整数。
代码#includeusing namespace std;const int MAX_N = 100000 3, MAX_LEN = 10 3;int n, m, dir[MAX_N];char str[MAX_N][MAX_LEN];int main() {scanf('%d%d', &n, &m);for (int i = 0; i n; i)scanf('%d%s', dir i, str[i]);int pos = 0;for (int i = 0, d, a; i m; i) {scanf('%d%d', &d, &a);int dd = d ^ dir[pos];if (dd == 1) (pos = a) %= n;else (pos -= a) %= n;pos = (pos % n n) % n;}printf('%s\n', str[pos]);return 0;}天天爱跑步running考点DFS，LCA（最近公共祖先），差分标记，前缀和分析对于NOIP 初学者来说，这个题在考场上是比较没有办法A 掉的，但是这并不妨碍我们拿到暴力分。
第22 届全国青少年信息学奥林匹克联赛2016提高组（复赛）第一试竞赛时间：2016 年11 月19 日 8:30 ∼ 12:00提交源程序文件名编译选项注意事项：1. 文件名（程序名和输入输出文件名）必须使用英文小写。
2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的全文比较。
3. 中函数()的返回值类型必须是，程序正常结束时的返回值必须是0。
4. 全国统一评测时采用的机器配置为： () x2 240 ，2.8，内存4G，上述时限以此配置为准。
5. 只提供格式附加样例文件。
6. 评测在下进行。
7. 编译时不打开任何优化选项。
玩具谜题（)【问题描述】小南有一套可爱的玩具小人，它们各有不同的职业。
有一天，这些玩具小人把小南的眼镜藏了起来。
小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。
如下图：这时告诉小南一个谜题：“眼镜藏在我左数第3 个玩具小人的右数第1 个玩具小人的左数第2 个玩具小人那里。
”小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。
小南一边艰难地辨认着玩具小人，一边数着：“朝内，左数第3 个是。
“朝外，右数第1 个是。
“朝外，左数第2 个是。
“所以眼镜藏在这里！”虽然成功找回了眼镜，但小南并没有放心。
如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。
所以小南希望你写程序帮他解决类似的谜题。
这样的谜题具体可以描述为：有n 个玩具小人围成一圈，己知它们的职业和朝向。
现在第 1 个玩具小人告诉小南一个包含m 条指令的谜题，其中第i 条指令形如“左数/右数第个玩具小人”。
你需要输出依次数完这些指令后，到达的玩具小人的职业。
【输入格式】从文件中读入数据。
输入的第一行包含两个正整数，表示玩具小人的个数和指令的条数。
接下来n 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。
其中0 表示朝向圈内，1 表示朝向圈外。
保证不会出现其他的数。
字符串长度不超过10 且仅由小写字母构成，字符串不为空，并且字符串两两不同。
整数和字符串之间用一个空格隔开。
接下来m 行，其中第i 行包含两个整数 , ，表示第i 条指令。
若= 0 ，表示向左数个人；若= 1 ，表示向右数个人。
保证不会出现其他的数，1 ≤< n。
【输出格式】输出到文件中。
输出一个字符串，表示从第一个读入的小人开始，依次数完m条指令后到达的小人的职业。
【样例 1 输入】7 31110 31 10 2【样例 1 输出】【样例 1 说明】这组数据就是【题目描述】中提到的例子。
【样例 2 输入】10 101 c0 r0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【样例 2 输出】y【子任务】子任务会给出部分测试数据的特点。
如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。
每个测试点的数据规模及特点如下表：其中一些简写的列意义如下：●全朝内：若为“√”，表示该测试点保证所有的玩具小人都朝向圈内；●全左数：若为“√”，表示该测试点保证所有的指令都向左数，即对任意的1 ≤ i ≤ m， = 0 ；● = 1 ：若为“√”，表示该测试点保证所有的指令都只数1个，即对任意的1 ≤ i ≤ m，= 1 ；●职业长度为1：若为“√”，表示该测试点保证所有玩具小人的职业一定是一个长度为 1 的字符串。
天天爱跑步（)【问题描述】小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。
《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含n 个结点和n − 1 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。
树上结点编号为从1 到n 的连续正整数。
现在有m 个玩家，第i 个玩家的起点为，终点为。
每天打卡任务开始时，所有玩家在第 0 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。
（由于地图是一棵树，所以每个人的路径是唯一的）小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。
在结点j 的观察员会选择在第秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第秒也正好到达了结点j 。
小C 想知道每个观察员会观察到多少人？注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。
即对于把结点j 作为终点的玩家：若他在第秒前到达终点，则在结点j 的观察员不能观察到该玩家；若他正好在第秒到达终点，则在结点j 的观察员可以观察到这个玩家。
【输入格式】从文件中读入数据。
第一行有两个整数n 和m 。
其中n 代表树的结点数量，同时也是观察员的数量，m 代表玩家的数量。
接下来n − 1 行每行两个整数u 和v ，表示结点u 到结点v 有一条边。
接下来一行n 个整数，其中第j 个整数为，表示结点j 出现观察员的时间。
接下来m 行，每行两个整数和，表示一个玩家的起点和终点。
对于所有的数据，保证1 ≤ , ≤ n ，0 ≤ ≤ n。
【输出格式】输出到文件中。
输出1 行n 个整数，第j 个整数表示结点j 的观察员可以观察到多少人。
【样例 1 输入】6 32 31 21 44 54 60 2 5 1 2 31 51 32 6【样例 1 输出】2 0 0 1 1 1【样例 1 说明】= 0 ，故只有起点为1 号点的玩家才会被观察对于1 号点，W1到，所以玩家1 和玩家2 被观察到，共2 人被观察到。
对于 2 号点，没有玩家在第 2 秒时在此结点，共 0 人被观察到。
对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。
对于 4 号点，玩家 1 被观察到，共 1 人被观察到。
对于 5 号点，玩家 1 被观察到，共 1 人被观察到。
对于 6 号点，玩家 3 被观察到，共 1 人被观察到。
【样例 2 输入】5 31 22 32 41 50 1 0 3 03 11 45 5【样例 2 输出】1 2 1 0 1【子任务】每个测试点的数据规模及特点如下表所示。
提示：数据范围的个位上的数字可以帮助判断是哪一种数据类型。
【提示】如果你的程序需要用到较大的栈空间（这通常意味着需要较深层数的递归），请务必仔细阅读选手目录下的文档，以了解在最终评测时栈空间的限制与在当前工作环境下调整栈空间限制的方法。
换教室（)【问题描述】对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中，有 2n节课程安排在n个时间段上。
在第i ( 1 ≤i ≤ n )个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室上课，而另一节课程在教室进行。
在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的n 节安排好的课程。
如果学生想更换第i 节课程的教室，则需要提出申请。
若申请通过，学生就可以在第i 个时间段去教室上课，否则仍然在教室上课。
由于更换教室的需求太多，申请不一定能获得通过。
通过计算，牛牛发现申请更换第i节课程的教室时，申请被通过的概率是一个己知的实数，并且对于不同课程的申请，被通过的概率是互相独立的。
学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 m 节课程进行申请。
这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的m 门课程，也可以不用完这m 个申请的机会，甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有v 个教室，有e 条道路。
每条道路连接两间教室，并且是可以双向通行的。
由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。
当第i （ 1 ≤i ≤n − 1 ）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。
现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。
【输入格式】从文件中读入数据。
第一行四个整数n, m, v, e 。
n 表示这个学期内的时间段的数量；m 表示牛牛最多可以申请更换多少节课程的教室；v 表示牛牛学校里教室的数量；e 表示牛牛的学校里道路的数量。
第二行n 个正整数，第i（1 ≤i ≤n ）个正整数表示，即第i个时间段牛牛被安排上课的教室；保证1 ≤≤v 。
第三行n 个正整数，第i （ 1 ≤i ≤n ）个正整数表示，即第i 个时间段另一间上同样课程的教室；保证1 ≤≤v 。
第四行n 个实数，第i （1 ≤i ≤n ）个实数表示，即牛牛申请在第i 个时间段更换教室获得通过的概率。
保证0 ≤≤1 。
接下来e 行，每行三个正整数，，，表示有一条双向道路连接教室, ，通过这条道路需要耗费的体力值是；保证1 ≤ , ≤v ，1 ≤≤ 100 。
保证1 ≤n ≤ 2000 ，0 ≤m ≤ 2000，1 ≤v ≤ 300 ，0 ≤e ≤ 90000 。
保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。
保证输入的实数最多包含3 位小数。
【输出格式】输出到文件中。
输出一行，包含一个实数，四舍五入精确到小数点后恰好 2 位，表示答案。
你的输出必须和标准输出完全一样才算正确。
测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于4×10-3 。
（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）【样例 1 输入】3 2 3 32 1 21 2 10.8 0.2 0.51 2 51 3 32 3 1【样例 1 输出】2.80【样例 1 说明】所有可行的申请方案和期望收益如下表：【样例 2】见选手目录下的2 与2。
【提示】1. 道路中可能会有多条双向道路连接相同的两间教室。
也有可能有道路两端连接的是同一间教室。
2. 请注意区分n, m, v, e 的意义，n 不是教室的数量，m 不是道路的数量。
【子任务】特殊性质1：图上任意两点，，≠间，存在一条耗费体力最少的路径只包含一条道路。
