Skip to content

1402: 小V的难题

题目

题目描述

小V的老师今天向小V留了这样一个难题

小V手上有一个长度为n的数列,第i个数为xi。

他现在想知道,对于给定的a,b,c,他要找到一个i,使得a * (i+1) * xi^2+(b+1) * i * xi+(c+i)=0成立。

如果有多个i满足,小V想要最小的那个i。

小V有很多很多组询问需要你回答,多到他自己也不确定有多少组。所以在输入数据中a=b=c=0标志着小V的提问的结束。

此外,小V的老师怕小V抄袭,于是决定对数据进行加密以防止离线算法的出现。

假设你在输入文件中读到的三个数为a0,b0,c0,那么小V真正要询问的a=a0+lastans,b=b0+lastans,c=c0+lastans.

lastans的值是你对小V的前一个询问的回答。

如果这是第一个询问,那么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

样例输出

5

4

3

3

数据范围

对于60%的数据,满足N<=1000,需要作出回答的询问个数不超过1000.

对于100%的数据,满足N<=50000,需要作出回答的询问个数不超过500000,

xi的绝对值不超过30000,解密后的a的绝对值不超过50000,

解密后的b的绝对值不超过10^8,解密后的c的绝对值不超过10^18.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!