夺宝大赛
夺宝大赛的地图是一个由 n×m 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。
假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。
时间限制：5000
内存限制：65535
输入
输入首先在第一行给出两个正整数 m 和 n（2 < m,n ≤ 100），随后 m 行，每行给出 n 个数字，表示地图上对应方格的状态：1 表示方格可通过；0 表示该方格有障碍物，不可通行；2 表示该方格是大本营。题目保证只有 1 个大本营。 接下来是参赛队伍信息。首先在一行中给出正整数 k（0 < k < m×n/2），随后 k 行，第 i（1 ≤ i ≤ k）行给出编号为 i 的参赛队的初始落脚点的坐标，格式为 x y。这里规定地图左上角坐标为 1 1，右下角坐标为 n m，其中 n 为列数，m 为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。
输出
在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以 1 个空格分隔，行首尾不得有多余空格。若没有队伍能获胜，则在一行中输出 No winner.
样例输入
样例1：
5 7 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 2 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 7 1 5 7 1 1 1 5 5 3 1 3 5 1 4
样例2：
5 7 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 2 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 7 7 5 1 3 7 1 1 1 5 5 3 1 3 5
样例输出
样例1：
7 6
样例2：
No winner.
提示
样例 1 说明： 七支队伍到达大本营的时间顺次为：7、不可能、5、3、3、5、6，其中队伍 4 和 5 火拼了，队伍 3 和 6 火拼了，队伍 7 比队伍 1 早到，所以获胜。
相似题推荐
传话对象
题目描述
在一个公司里，有 n 名员工，编号 1 到 n。每名员工都有一个“传话对象”，即第 ii 名员工只会把消息告诉第 ti 名员工（允许告诉自己）。现在，从每名员工出发，依次沿着传话对象传递消息，可以证明经过有限步后，消息一定会回到一个已经传过的员工。
请你分别计算：从第 i 名员工开始，需要传递多少步后，才会第一次遇到一个已经传过消息的员工。
输入格式
第一行，一个整数 n。
第二行，n 个整数 t1,t2,…,tn，表示第 i 名员工的传话对象。
输出格式
输出 n 行，第 i 行一个整数，表示从第 i 名员工出发的答案。
输入样例
4 2 1 1 4
输出样例
2 2 3 1
说明提示
1≤n≤5×105
能量护盾
题目描述
在一处被宇宙射线笼罩的星域中，你驾驶着一艘小型探索飞船，需要从坐标 (xs,ys) 航行到坐标 (xt,yt)。
飞船可以以速度 1 向任意方向移动，自身视为一个点。
星域中分布着 N 个圆形能量护盾，第 i 个护盾的圆心为 (xi,yi)，半径为 ri。护盾之间可能相互重叠，也可能存在包含关系。
飞船一旦进入某个护盾的内部，就能免受宇宙射线的伤害。若一个点不在任何护盾内部，则飞船会持续受到宇宙射线的照射。
你的目标是：在从起点到终点的航行过程中，尽可能减少受到宇宙射线照射的总时间。
请你计算这个最小照射时间。
输入格式
第一行，四个整数 xs,ys,xt,yt，分别表示起点和终点的坐标。
第二行，一个整数 N，表示圆形护盾的数量。
接下来 N 行，每行三个整数 xi,yi,ri，描述第 i 个护盾的圆心坐标和半径。
输出格式
输出一个实数，表示受到宇宙射线照射的最小时间，保留 10 位小数。
输入样例#1
-2 -2 2 2 1 0 0 1
输出样例#1
3.6568542495
输入样例#2
-2 0 2 0 2 -1 0 2 1 0 2
输出样例#2
0.0000000000
输入样例#3
4 -2 -2 4 3 0 0 2 4 0 1 0 4 1
输出样例#3
4.0000000000
说明提示
−109≤xs,ys,xt,yt≤109
(xs,ys)≠(xt,yt)
1≤N≤1000
−109≤xi,yi≤109
1≤ri≤109
图书馆
题目描述
某城市有 n 条东西向街道和 n 条南北向街道，构成一个 n×n 的街区网格。每个交叉路口处恰好建有一座图书馆，且每一行、每一列的交叉路口都恰好有一座图书馆。已知第 i 座图书馆的坐标 (xi,yi) 表示它位于第 xi 条东西向街道与第 yi 条南北向街道的交汇处。
城市规划师想要知道：有多少个 正方形区域（由连续的若干条东西向街道和连续的若干条南北向街道围成），使得该区域内每一行、每一列也恰好各有一座图书馆？
输入格式
第一行，一个整数 n。
第二行，n 个整数 x1,x2,…,xn，表示第 i 座图书馆的东西向街道编号。
第三行，n 个整数 y1,y2,…,yn，表示第 i 座图书馆的南北向街道编号。
输入保证：1≤xi,yi≤n，且每行每列恰好只有一座图书馆。
输出格式
输出一个整数，表示满足条件的正方形区域个数。
输入样例
7 1 2 3 4 5 6 7 4 3 1 6 2 5 7
输出样例
10
说明提示
1≤n≤105
1≤xi,yi≤n
输入保证每行每列恰好有一座图书馆。
产品研发
题目描述
一家公司正在研发一款新产品。该产品共有 K 项关键性能指标，初始时所有指标均为 0。公司的最终目标是让 每一项指标都不低于 P。
研发团队提出了 N 个独立的改进方案。第 i 个方案一旦实施，会同时为第 j 项指标（1≤j≤K）带来 Ai,j 的提升，但实施该方案需要投入 Ci 的研发成本。每个方案最多只能执行一次。
你需要判断：是否存在一系列方案的选择，使得所有指标均达到或超过 P？如果存在，请给出 最小的总研发成本；如果不存在，输出 −1。
输入格式
第一行，三个整数 N,K,P，分别表示方案数量、指标数量和目标阈值。
接下来 N 行，每行 K+1 个整数 Ci,Ai,1,Ai,2,…,Ai,K，分别表示第 i 个方案的成本，以及执行后各指标的提升值。
输出格式
输出一个整数，表示达成目标所需的最小总成本。若无法达成，输出 −1。
输入样例#1
4 3 5 5 3 0 2 3 1 2 3 3 2 4 0 1 0 1 4
输出样例#1
9
输入样例#2
7 3 5 85 1 0 1 37 1 1 0 38 2 0 0 45 0 2 2 67 1 1 0 12 2 2 0 94 2 2 1
输出样例#2
-1
说明提示
1≤N≤100
1≤K,P≤5
0≤Ai,j≤P（1≤i≤N, 1≤j≤K）
1≤Ci≤109（1≤i≤N）
最短工期
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。
时间限制：1000
内存限制：65536
输入
首先第一行给出两个正整数：项目里程碑的数量 N（≤ 100）和任务总数 M。这里的里程碑从 0 到 N-1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。
输出
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。
样例输入
样例#1：
9 12 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 5 4 0 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4
样例#2：
4 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5
样例输出
样例#1：
18
样例#2：
Impossible
