1906: 命运之桥
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:35
解决:15
题目描述
有一座名为“命运之桥”的独木桥,它横跨在一条深不见底的峡谷之上,连接着王国的两个重要领地。你,作为一位智慧而勇敢的探险家,正带领着一群旅人,踏上了一段寻找古老宝藏的冒险之旅。旅途漫长而艰辛,旅人们站在桥上欣赏四周壮丽的风光。然而,这座桥异常狭窄,每次只能允许一个人通过,且一旦有两人迎面相遇,他们则无法绕行,只能有一个人退回到起点,让另一个人先行。但是,可以有多个人同时呆在同一个位置。
这时来了一群强盗,你们需要赶紧离开桥,桥的长度为 L,旅人们只能呆在坐标为整数的地方。所有旅人的速度都为 1,但一个旅人某一时刻来到了坐标为 0或 L+1 的位置,他就离开了桥。但问题在于,你对每位旅人的初始行进方向一无所知,他们有的可能正向桥的另一端前进,有的可能正打算返回。但是旅人都有一个初始方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个旅人面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。
你急需计算出,你们全部撤离这座独木桥需要的最大时间,以及最小时间。
输入
第一行共一个整数 L,表示桥的长度。桥上的坐标为 L1,L2,......,L。
第二行共一个整数 N,表示初始时留在桥上的旅人数目。
第三行共有 N 个整数,分别表示每个旅人的初始坐标。
输出
共一行,输出 2 个整数,分别表示旅人撤离独木桥的最大时间和最小时间。2个整数由一个空格符分开。
样例输入 复制
4
2
1 3
样例输出 复制
4 2
提示
对于 的数据,满足初始时,没有两个旅人同在一个坐标,,,且数据保证 。