:i P1193 - 100% 弱点击破! - 铁一启智tyqzOJ

1193: 100% 弱点击破!

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:137 解决:10

题目描述

【题目背景】

《崩坏:星穹铁道》是一款优秀的回合制游戏。在战斗中,每位敌人都拥有一个弱点值,只有使用对应元素攻击敌人弱点值才会削减。当敌人的弱点值被削减为 $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.