b418.
八成真物
內容
「偽物比真物更有價值」—貝木泥舟
「真物和偽物一樣有價值」—忍野咩咩
「偽娘比真娘更有價值」—精英島民
任兩個物品的相似度 $sim(A, B) = \frac{|A \cap B|}{|A \cup B|}$，換句話說把 $A$ 具有的特徵和 $B$ 具有的特徵類型取交集、聯集個數，相除就能得到其相似度。例如有 5 個特徵，若 A 表示成 11001、B 表示成 01100，$sim(A, B) = \frac{|{2}|}{|{1, 2, 3, 5}|} = 0.25$。
現在盤面上有 N 個物品、M 種特徵，請問相似度大於等於 0.8 的相似對數 $S$ 有多少種。為了讓這一題更有趣味，算法允許偽物，輸出 $\frac{S}{N(N-1)/2} \times 100 \text{%}$。
輸入說明
每組測資，第一行會有兩個整數 $N, M$，表示有 $N$ 個物品、$M$ 種特徵。
接下來會有 $N$ 行，每一行上會有 $M$ 個 01 字符，第 $i$ 行上的第 $j$ 個字元，表示第 $i$ 個物品，是否擁有特徵 $j$。
- $1 < N \le 1024, 0 < M \le 512$
輸出說明
對於每一組輸出一行，輸出一個小數點兩位，相似度高於 0.8 的對數 / 總對數的百分比。
範例輸入
#1
8 10 0111101101 0111101100 0111101100 0111101101 1100101010 0111101100 0111101100 0011101111 8 10 1111101100 1011101100 1010101100 1010111010 0100110100 1011101100 1110110000 1011111100
範例輸出
#1
53.57 25.00
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 3.0s , <10M
公開 測資點#3 (20%): 5.0s , <10M
公開 測資點#4 (20%): 5.0s , <10M
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 3.0s , <10M
公開 測資點#3 (20%): 5.0s , <10M
公開 測資點#4 (20%): 5.0s , <10M
提示 ：
注意浮點數誤差，感謝 liouzhou_101 提醒。
出處:
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||