开始: 2024-06-02 14:30:00

20240602

结束: 2024-06-02 17:30:00
当前: 2025-0505-3131 11:35:17  类型:单人排位赛 状态:已经结束 
P5 : 集合  
描述

超能侠是一位数学爱好者,最近他对集合非常感兴趣。两个集合之间可能有很大差异,也有可能很相似,为了知道它们有多么大的差异,他定义了一个指标来判定集合的差异度。

用x来表示两个集合中都存在的不相等的整数的个数,y来表示两个集合中所有不相等的整数的个数,那么x/y就是超能侠定义的最终指标。现在超能侠向你寻求帮助,希望你能够帮忙计算这个指标。

注意,超能侠是个大忙人,他给你的集合可能没有去重,需要你自己维护集合的互异性(即集合中没有重复的元素)。

输入

输入文件有若干行:

第一行是一个正整数N,表示集合的个数;

接下来N行,每行描述一个集合。首先是一个正整数M,表示集合中数的个数,然后是M个整数,表示集合中的元素;

之后一行一个正整数K,表示需要计算的集合对的数量;

接下来K行,每行包含两个整数,表示需要计算该指标的集合对的两个编号。

输出

输出文件有K行,对每一对需要计算的集合,在一行中输出计算出的差异指标,保留两位小数。

样例

输入

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

输出

0.50
0.33
提示

【输入输出样例1说明】

首先计算集合1和集合2的差异指标:两个集合中都存在的不相等的整数有87、101,故x=2;两个集合中所有不相等的整数有99、87、101、5,故y=4;最终计算出指标x/y=0.50。

计算集合1和集合3同理:两个集合中都存在的不相等的整数有99、101,故x=2;两个集合中所有不相等的整数有99、87、101、18、5、135,故y=6;最终计算出指标x/y=0.33。

 

对于30%的数据,K=1;

对于另30%的数据,1≤集合中的元素≤100;

对于100%的数据,2≤N≤50,1≤M≤5000,1≤集合中的元素≤10^9,1≤K≤2000。