题目名称 1048. [Citric S2] 一道防AK好题
输入输出 hard.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 6
题目来源 GravatarMakazeu 于2012-08-26加入
开放分组 全部用户
提交状态
分类标签
数学
分享题解
通过:25, 提交:102, 通过率:24.51%
Gravatar不知云 100 0.512 s 16.05 MiB C++
Gravatardigital-T 100 0.714 s 15.93 MiB C++
GravatarSky_miner 100 0.720 s 12.14 MiB C++
Gravatardevil 100 0.731 s 15.95 MiB C++
GravatarEzio 100 0.734 s 12.14 MiB C++
Gravatarc3705 100 0.734 s 15.95 MiB C++
GravatarEzio 100 0.738 s 12.14 MiB C++
Gravatarwoca 100 0.750 s 15.95 MiB C++
GravatarEzoi_XY 100 0.762 s 15.93 MiB C++
Gravatarcstdio 100 0.766 s 12.14 MiB C++
关于 一道防AK好题 的近10条评论(全部评论)
这题的描述简直是残虐我这种弱菜
数据之大,模拟不能。
╮(╯▽╰)╭这世道(╯‵□′)╯︵┻━┻智商是硬伤
GravatarEzio
2014-08-24 21:43 6楼
Pascal同学请注意,当进行乘法运算时,得出的积会暂时存储在第一个出现的变量当中!所以有可能会爆215(值溢出)!所以先用一个能存的下的数做第一个是十分重要的- -
GravatarFoolMike
2014-08-22 11:39 5楼
回复 @舍得 :
把倒数第四行的“n-1”改成“l-1“,把y数组的范围开到1..500000,把c改成int64,应该就会好了
GravatarFoolMike
2014-08-22 10:14 4楼
天哪,少个+1 居然过了4个点 错误代码139 136的飞……
PS:我是蓝字菌
Gravatardigital-T
2014-02-15 15:19 3楼
脑筋急转弯……
WC 2014发来贺电
Gravatarcstdio
2014-02-08 22:12 2楼
可否边读入边处理输出
此代码提交后显示 运行时错误
program hard(input,output);
var
a,b,c,i,ans,n,l:longint;
x,y:array[1..50000] of longint;
begin
assign(input,'hard.in');
reset(input);
assign(output,'hard.out');
rewrite(output);
readln(n);
for i:=1 to n do
read(x[i]);
ans:=0;
l:=0;
repeat
inc(l);
read(a);inc(a,ans);
read(b);inc(b,ans);
read(c);inc(c,ans);
for i:=1 to n do
if (a*(i+1)*x[i]*x[i]+(b+1)*i*x[i]+(c+i))=0 then
begin
ans:=i;
y[l]:=ans;
break;
end;
until (a=0)and(b=0)and(c=0);
for i:=1 to n-1 do writeln(y[i]);
close(input);
close(output);
end.
Gravatar舍得
2012-09-26 14:00 1楼

1048. [Citric S2] 一道防AK好题

★   输入文件:hard.in   输出文件:hard.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目背景】

第二届『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


【输出样例】

5
4
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.