#2306. 自动刷题机
自动刷题机
自动刷题机
题目描述
第2页
题一: 自动刷题机(程序文件名:autoac. pas / c / cpp )
【问题描述】曾经发明了信号增幅仪的发明家SHTSC 又公开了他的新发明:自动刷题
机——一种可以自动AC 题目的神秘装置。
自动刷题机刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序,
每秒,自动刷题机的代码生成模块会有两种可能的结果:
A.写了x 行代码。
B.心情不好,删掉了之前写的y 行代码。
(如果y 大于当前代码长度则相当于全部删除。)
对于每个OJ 所有题目,存在某个固定的长度n>0。一旦自动刷题机在某秒结束时积累
了大于等于n 行的代码,它就会自动提交并AC 此题,然后新建一个文件开始写下一题。
SHTSC 在某个OJ 上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他
突然发现自己没有记录这个OJ 的n 究竟是多少。所幸他通过自己在OJ 上的Rank 知道了机
一共切了k 道题。希望你计算n 可能的最小值和最大值。
【输入文件】第一行两个整数l,k,表示刷题机的日志一共有l 行,一共了切了k 题。
第二行l 个整数,x1…xl。xi>=0 表示写了xi 行代码。xi<0 表示删除了这道题的-xi 行代
码。
【输出文件】输出两个数a,b。分别代表n 可能的最小值和最大值。如果不存在这样的n
则输出-1。
【输入输出样例】
autoac1.in
autoac1.out
4 2
2
5
-3
9
3 7
autoac2.in
autoac2.out
5 5
1
2
3
4
5
1 1
autoac3.in
autoac3.out
1 10
-1
-1
【样例说明】样例1:如果n=2 那么刷题机就会切掉3 题。但如果n>7 刷题机最多只能切1
题。考虑n=4 发生了什么。
第一秒:刷题机写了2 行。
第二秒:刷题机又写了5 行,共有7 行,提交,自信AC。
第三秒:刷题机删掉了3 行,共有0 行。
第四秒:刷题机写了9 行,共有9 行,提交,自信AC。一共AC 了两题。
样例2:刷题机5 秒一共AC 了5 题,于是只能每秒AC 一题。n 只能=1。
样例3:刷题机1 秒AC 了10 题。这是不可能做到的。输出-1。
【数据规模】对于20%的数据:Sum(|xi|)<=2000。对于60%的数据:l<=2000,k<=100。
第3页 对于100%的数据:1<=l,k<=100000,|xi|<=10^9。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 2
2
5
-3
9
3 7
样例 2
5 5
1
2
3
4
5
1 1