1193: 100% 弱点击破!
题目描述
【题目背景】
《崩坏:星穹铁道》是一款优秀的回合制游戏。在战斗中,每位敌人都拥有一个弱点值,只有使用对应元素攻击敌人弱点值才会削减。当敌人的弱点值被削减为 $0$ 时,我们就称该敌人的弱点被击破了。
弱点击破是一种很实用但很麻烦的战斗技巧!幸亏本题的出题人小 R 拥有一个强力的角色——星核猎手「银狼」,可以无视元素的弱点值将敌方的弱点直接击破。
她真好看(不是
【题目描述】
战斗开始了!有 $n$ 个敌人呈一行排列,现在是小 R 的回合。
他可以使用银狼的战技,将对方 $m$ 个连续的敌人击破弱点。由于他是重氪玩家(大雾),他可以无限制地使用此技能。
但是,如果一个敌人在弱点击破状态下再被银狼的战技击中,该敌人的弱点将直接回复到未击破状态。且银狼必须选择连续的 $m$ 个目标施放战技。举个例子,如果 $m = 3$,那么银狼不能只对敌方最右边的 $2$ 个敌人施放战技,但是可以对敌方最右边的连续 $3$ 个敌人施放战技。
小 R 想利用银狼的战技获得最大对局优势,同时为了让她的银狼不那么辛苦,尽量少使用银狼的战技。所以给定 $n$ 和 $m$,小 R 想知道:
- 最多可以击破几个敌方的弱点?
- 在击破敌方弱点数尽量多的条件下,银狼最少只需使用几次战技?
输入
输入一行两个正整数 $n$ 和 $m$。
输出
输出共 $2$ 行,每行一个正整数,分别为上述两问的结果:
- 最多可以击破几个敌方的弱点;
- 在击破敌方弱点数尽量多的条件下,银狼最少只需使用几次战技。
样例输入 复制
5 3
样例输出 复制
4
2
提示
【样例解释】
共 $5$ 个敌人,银狼可以一次击破 $3$ 个敌人的弱点。
首先,她对第 $1$、第 $2$、第 $3$ 个敌人使用了一次战技,此时她击破了 $3$ 个敌人的弱点,使用了 $1$ 次战技;
然后,她对第 $3$、第 $4$、第 $5$ 个敌人使用了一次战技,此时第 $3$ 个敌人因为受到了两次战技,弱点恢复了;同时第 $4$ 、第 $5$ 个敌人的弱点被击破。此时她击破了 $4$ 个敌人的弱点,使用了 $2$ 次战技。
可以证明她最多只能击破 $4$ 个敌人的弱点。
【数据范围】
$30%$ 的数据满足特殊性质 $n=m$。
对于前 $20%$ 的数据,$n,m\le100$;
对于前 $60%$ 的数据,$n,m\le10^6$;
对于 $100%$ 的数据,$1\le m\le n\le10^{18}$。
柳州铁一中学(初中部)第二届程序设计竞赛 F。
By Running_a_way.