题目名称 306. [SGOI] 糊涂的记者
输入输出 sign.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarBYVoid 于2009-03-23加入
开放分组 全部用户
提交状态
分类标签
二分图 数学
分享题解
通过:17, 提交:42, 通过率:40.48%
Gravatar沧澜 100 0.019 s 2.30 MiB C++
Gravatar→震世逆空波→ 100 0.063 s 0.72 MiB C++
GravatarLink 100 0.064 s 7.96 MiB C++
GravatarLink 100 0.064 s 7.96 MiB C++
Gravatar怡红公子 100 0.067 s 3.56 MiB C++
GravatarFoolMike 100 0.068 s 3.28 MiB C++
Gravatar怡红公子 100 0.070 s 3.56 MiB C++
GravatarBYVoid 100 0.080 s 5.92 MiB C++
Gravatar我想 100 0.113 s 0.44 MiB Pascal
GravatarLink 100 0.137 s 11.33 MiB C++
关于 糊涂的记者 的近10条评论(全部评论)
exp和ln精度不错嘛
GravatarFoolMike
2017-06-01 20:24 2楼
到底保留几位有效数啊?
表示现在理解了,保留有效数和保留小数点后几位是不一样的。
Gravatar怡红公子
2012-10-28 17:11 1楼

306. [SGOI] 糊涂的记者

★★★   输入文件:sign.in   输出文件:sign.out   评测插件
时间限制:1 s   内存限制:128 MiB

【问题描述】

   在如今的信息社会中,时间 - 就是生命,对于记者们来说,如何以最快的速度传递消息就显得十分重要了,而为了尽快记录消息内容,速记也是必不可少的。速记就是用一些简单且特殊的符号表示一定的含义,具体如何对应依个人习惯而定,没有一种固定的表示方法。
Tom 是一名报社的新闻记者,常常马不停蹄的跟着新闻跑,有时只能随手记下采访的内容,让人送回报社,而自己又奔赴下一个现场。不过 Tom 是一个糊涂的记者,有时忙中出错,把用自己的速记符号写的内容直接传回报社。因为一时联系不上 Tom ,但这条新闻又十分重要,要赶着在当天的报纸排版前整理出来,于是 Tom 的同事们只好来猜测 Tom 的速记符号的意思。幸运的是 Tom 的同事们与他共事的时间也不短了,对于 Tom 的一些用词情况有一定的了解,经过讨论,他们列出了一张可能性表来表示每一个速记符号可能与哪些单词相对应,并列出了对应的可能性有多大。
你的任务是:根据 Tom 的同事们提供的可能性表,找出一种可能性最大的速记符号与单词的对应方法(可能性应该相乘来计算)。
  注意 每一个速记符号有且只有一个单词与其对应,每一个单词有不超过一个速记符号与其对应(可能没有速记符号与之对应)。

【输入格式】

   文件的第一行有两个整数,分别为速记符号的个数 n(1<=n<=100) 和单词总 m (1<=m<=500) 。
从第 1 行到第 n+1 行为每个速记符号可能对应的单词及其可能性。
第 i+1(1<=i<=n) 行的第一个数 Ci 表示第 i 个速记符号可能与 Ci 个单词相对应,后面有 Ci 个数对 (Nik , Rik)(1<=k<=Ci) ,表示第 i 个速记符号与第 Nik 个单词相对应的可能性为 Rik ( Rik 为大于 0 小于 1 的实数)。

【输出格式】

   输出文件仅包含一行,若有解则输出一个实数即最大的可能性,保留四位有效数字(四舍五入),若无解则输出 "NO ANSWER" 。
(当可能性大于 1e-12 时才被视为有解)

【输入输出样例】

输入文件

3 3

2 1 0.4 3 0.2

1 3 0.8

3 1 0.1 2 0.9 3 0.2


输出文件

0.2880