P4343 [SHOI2015] 自动刷题机
题目背景
曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明:自动刷题机——一种可以自动 AC 题目的神秘装置。
题目描述
自动刷题机刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序。每秒,自动刷题机的代码生成模块会有两种可能的结果:
1.写了 $x$ 行代码
2.心情不好,删掉了之前写的 $y$ 行代码。(如果 $y$ 大于当前代码长度则相当于全部删除。)
对于一个 OJ,存在某个固定的正整数长度 $n$,一旦自动刷题机在某秒结束时积累了大于等于 $n$ 行的代码,它就会自动提交并 AC 此题,然后新建一个文件(即弃置之前的所有代码)并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 $k$ 道题,希望你计算 $n$ 可能的最小值和最大值。
输入格式
无
输出格式
无
说明/提示
#### 数据规模与约定
- 对于 $20\%$ 的数据,保证 $l \le 10$;
- 对于 $40\%$ 的数据,保证 $l \le 100$ ;
- 对于 $60\%$ 的数据,保证$l \le 2 \times 10^3$;
- 对于 $100\%$ 的数据,保证 $1 \leq l \le 10^5$,$-10^9 \le x_i \le 10^9$。