168. TOPC 2017 PA. Similarity Computation

0 Judge

Code: 0


Similarity Computation

英文題目敘述

The Jaccard similarity coefficient is usually used for measuring the similarity of two sets. Give two sets $A$ and $B$, the Jaccard similarity coefficient, $J(A,B)$, is defined as the size of the intersection divided by the size of the union of the two sets. That is, $J(A,B)= \frac{|A\cap B|}{|A\cup B|}$. For example, if $A=\{1, 3, 7, 8\}$ and $B=\{1, 7, 9\}$, then $J(A, B)=\frac{|\{1,7\}|}{|\{1, 3, 7, 8, 9\}|}=\frac{2}{5}$.

Assume the element $i$ in the set is an integer between $0$ to $9$ ($0\le i\le9$) and the size of the set is no larger than $10$. Please write a program to compute the Jaccard similarity coefficient of two sets $A$ and $B$. And output $1$ if $J(A,B)>0.5$ and $0$ if $J(A,B)\le0.5$.

英文輸入說明

The first line of the input file contains an integer $T$ ($T\le25$) indicating the number of test cases to follow.

Each test case will consist of three lines. The first line contains two integers $m$ and $n$ ($0 < m, n \leq 10$), indicating the number of elements of sets $A$ and $B$, respectively. The second line contains $m$ integers (the elements of set $A$) and the third line contains $n$ integers (the elements of set $B$).

You may assume:

  • $1 \le T \le 25$
  • $m \le 10$ and $n \le 10$

英文輸出說明

For each test case, output $1$ if $J(A,B)>0.5$ and $0$ if $J(A,B)\le0.5$.

範例輸入

3
5 6
0 2 3 5 6
1 2 4 6 7 9
3 2
1 4 6
4 6
7 7
0 1 3 4 6 8 9
0 1 2 3 4 6 7

範例輸出

0
1
1

中文題目敘述

Jaccard similarity coefficient是一種常用於度量集合相似度的指標,給定$A$、$B$兩個集合,其Jaccard similarity coefficient度量方法如下: $$J(A, B)=\frac{|A\cap B|}{|A\cup B|}$$

其中分子代表的是兩個集合的交集元素個數,分母則是兩個集合聯集元素個數。例如$A=\{1, 3, 7, 8\}$、$B=\{1, 7, 9\}$,則$J(A, B)=\frac{|\{1, 7\}|}{|\{1, 3, 7, 8, 9\}|}=\frac{2}{5}$。假設集合的元素只會是整數數字0至9,請寫一個程式判斷兩個集合(集合大小皆不大於10)的Jaccard similarity coefficient是否大於0.5,當大於0.5時輸出1,反之輸出0。

中文輸入說明

測試輸入的第一行為一個整數$T$,代表有多少組測試資料。每組測試資料有三行,其中第一行為兩個正整數$m$跟$n$,分別代表$A$集合與$B$集合的元素個數。接下來的兩行為一系列$0$到$9$的整數,代表集合$A$與$B$內的元素,每一行的數字間用單一空格區隔。

可假設:

  • $1 \le T \le 25$
  • $m \le 10$ 且 $n \le 10$

中文輸出說明

針對每一組測試資料,當$J(A, B)>0.5$時輸出$1$,反之輸出$0$。


Judge Setting

run-time limit: 1000 ms
memory limit: 65536000 byte
測資數量: 0