#PQJ2726x15593. QOJ 2726_15593

    ID: 2856 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SHTSC 2015枚举

QOJ 2726_15593

第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。