网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[Citric S2]一道防AK好题
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | hard.in | 输出文件 | hard.out |
【题目背景】
第二届『Citric杯』NOIP提高组模拟赛第一题【题目描述】
Lemon认为在第一届『Citric』杯模拟赛中出的题目太简单了,于是他决定,这次要给参赛选手们一个下马威! ^_^Lemon手上有一个长度为n的数列,第i个数为xi。
他现在想知道,对于给定的a,b,c,他要找到一个i,使得a*(i+1)*xi^2+(b+1)*i*xi+(c+i)=0成立。
如果有多个i满足,Lemon想要最小的那个i。
Lemon有很多很多组询问需要你回答,多到他自己也不确定有多少组。所以在输入数据中a=b=c=0标志着Lemon的提问的结束。
更加糟糕的是,Lemon为了加大难度,决定对数据进行加密以防止离线算法的出现。
假设你在输入文件中读到的三个数为a0,b0,c0,那么Lemon真正要询问的a=a0+lastans,b=b0+lastans,c=c0+lastans.
lastans的值是你对Lemon的前一个询问的回答。如果这是第一个询问,那么lastans=0
所有的询问都将会按上述方式进行加密,包括标志着询问的结束的那个询问也是这样。
【输入格式】
输入文件第一行包含一个正整数n,表示数列的长度。输入文件第二行包含n个整数,第i个数表示xi的值。
接下来若干行,每行三个数,表示加密后的a,b,c值(也就是上文所述的a0,b0,c0)
【输出格式】
包含若干行,第i行的值是输入文件中第i个询问的答案。注意,你不需要对标志着询问结束的那个询问作答。同时,标志着询问结束的询问一定是输入文件的最后一行。也就是,输入文件不会有多余的内容。
【输入样例】
5-2 3 1 -5 2
-5 -4 145
-1 -6 -509
-9 -14 40
-3 -13 21
-3 -3 -3
【输出样例】
54
3
3
【样例解释】
第一个询问中,真实的a=-5+0=-5,b=-4+0=-4,c=145+0=145(第一个询问中lastans=0)带入发现,i=5时,-5*(5+1)*2^2+(-4+1)*5*2+145+5=0,而其他的i均不符合条件。所以答案是5.
第二个询问中,真实的a=-1+5=4,b=-6+5=-1,c=-509+5=-504(lastans是上一个询问的答案的值,也就是5)
经带入发现,i=4时,4*(4+1)*(-5)^2+(-1+1)*4*(-5)+(-504)+4=0,满足条件,而其他的i均不满足条件,所以答案是4.
同理,第三个询问中真实的a=-5,b=-10,c=44.答案i=3
第四个询问中真实的a=0,b=-10,c=24,答案i=3
第五个询问中真实的a=0,b=0,c=0,此时我们发现这是一个标志着结束的询问,这个询问我们无需作出回答。
【数据规模】
时间限制3s对于40%的数据,满足N<=1000,需要作出回答的询问个数不超过1000.
对于100%的数据,满足N<=50000,需要作出回答的询问个数不超过500000,xi的绝对值不超过30000,解密后的a的绝对值不超过50000,解密后的b的绝对值不超过10^8,解密后的c的绝对值不超过10^18.