7897 - 试题H:愤怒的FlappyBird 20'

FlappyBird是一款简单又困难的手机游戏,游戏中玩家必须控制一只胖乎乎的FlappyBird,跨越由各种不同长度水管所组成的障碍。如下图所示:

15850562431919.pngFlappyBird

由于被大家称为胖乎乎的小鸟,所以这FlappyBird很愤怒,决定横冲直撞,撞掉一条直线上的所有柱子。

为了简化问题,增加问题的趣味性。把场景设定为长度为N,高度为H的一条通道。每一个单位长度有一个柱子,且奇数位置的柱子是从下往上长的,偶数位置的柱子是从上往下长的(如下图所示)。FlappyBird会撞坏一条直线上的所有柱子。作为一个游戏安全评估师,JM想知道FlappyBird有多少种飞行高度,会撞坏最少柱子数量。

15850562657661.png游戏通道图

 

15850568048194.png在飞行高度位4的位置,撞坏的柱子数为8

注意:FlappyBird飞行时只会选择某一高度的中间飞行,如上图所示。不会飞行在相邻两个高度的交界处。即:如果通道高度为5,从上往下长度为2的柱子和从下往上长度为3的柱子是永远不可能同时被撞坏的。

输入

输入第一行包含两个整数N,H,分别表示柱子的数量以及通道的高度。

接下来下来输入N行,每行一个整数A_i,表示柱子的长度。

奇数行根柱子表示柱子从下往上,长度为A_i;偶数行表示柱子从上往下场地为A_i.

输出

输出两个整数,分别表示最少撞坏柱子数以及可能的高度数量。

样例

输入

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3 

输出

7 2

输入

6 7
1
5
3
3
5
1 

输出

2 3

提示

样例1解释

15850568048194.png在飞行高度位4的位置,撞坏的柱子数为8

如上图所示

在高度1处飞行,会撞坏7根柱子;

在高度2处飞行,会撞坏8根柱子;

在高度3处飞行,会撞坏10根柱子;

在高度4处飞行,会撞坏8根柱子;

在高度5处飞行,会撞坏7根柱子;

所以最少会撞坏柱子数位7,共有2种飞行高度。

数据规模

对于30\%的数据,2 \le N \cdot H \le 10^6

对于100\%的数据,2 \le N \le 2\cdot 10^5, 2 \le H \le 5 \cdot 10^5,0 \le A_i \le H.

来源

竞码编程-蓝桥杯模拟赛6(大学生组&青少年组)
时间限制 2 秒
内存限制 512 MB
讨论 统计
上一题 下一题