#Algo1005. Barracuda

    ID: 191 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>算法基础枚举暴力数学高斯消元luogu

Barracuda

题目背景

小正方形的冒险旅途,并不顺利。

一路上,小正方形看到了壮美秀丽的小岛被污染,看到了雄伟壮观的火山,还碰到了许许多多的敌人。

眼下,小正方形正在对付一个巨大的三角形。

题目描述

大三角形给小正方形讲起自己的过去:过去的它是一个挖宝工,后来被黑暗之主污染才会落到此番境地。

它也希望小正方形去战胜黑暗之主,不过限于黑暗之主的眼线密布,因此必须给小正方形设置障碍才能骗过那些“眼线”。

他给小正方形的问题是:它有 nn 个小三角形,每个小三角形有一定的质量,它对这些三角形进行了 n+1n + 1 次称量,然而由于托盘天平(?)的问题,有一次称量的结果是有误的。

现在,大三角形想要知道最重的小三角形的 编号。

一组输入是合法的,当且仅当输入满足以下条件:

不存在一组 ii,jj,使得当我们假定ii 条称量数据有误时能求出一种合法方案且我们假定jj 条称量数据有误时也能求出一种合法方案。

合法方案定义如下:

1、最重的三角形只有一个。

2、不存在重量不确定的三角形。

3、所有三角形的重量均为正整数。

输入格式

输入的第一行为一个正整数 nn,表示小三角形的数目。

接下来 n+1n + 1 行,每行按照以下格式输入:

首先是一个正整数 mm,表示这次称量抓了几个小三角形。

接下来 mm 个整数,表示称量的小三角形的编号。

最后一个整数 weightweight ,表示这次称量的结果。

输出格式

若合法,输出最重小三角形的编号,否则输出 "illegal"(不含引号)。

2
1 1 2
2 1 2 5
2 1 2 1
2
2
1 1 2
2 1 2 4
2 1 2 5
2
2
1 1 2
2 1 2 6
2 1 2 5
illegal

提示

样例一:

若第一次称量结果错误,则无法得出正确解。

若第二次称量结果错误,则第二个小三角形重量为负,显然不对。

若第三次称量结果错误,我们得出 11 号小三角形重量为 2222号小三角形重量为 3322号小三角形最重。

本题采用捆绑测试,共有三个 subtasksubtask,描述如下:

subtask030Ptssubtask 0 - 30Pts 保证小三角形的重量 <= 20且 n<=5n <= 5,在这个 subtasksubtask 中,你每通过一个点可获得 1010 分。

subtask130Ptssubtask 1 - 30Pts 保证小三角形的重量 <= 100 并且 n<=100n <= 100,数据为随机生成。

subtask240Ptssubtask 2 - 40Pts 保证小三角形的重量 <= 100 并且 n<=100n <= 100

在后两个 subtasksubtask 中,你必须通过所有数据才能得分。

对于 100%100\% 的数据, 1<=m<=n1 <= m <= n