De thi Toan Tin hoc trong nha truong Bai 84
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (75.74 KB, 2 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
<b>Bài 84/2001 - Cùng một tích</b>
(Dành cho học sinh THCS và THPT)
<i>Thuật toán: Gọi số lượng số xi =1 là a, số lượng số xi=-1 là b, số lượng số xi = 0 là c. Ta</i>
có: a+b+c=N.
Với mỗi giá trị c khác nhau ta có tương ứng một nghiệm. Nên số nghiệm bằng số giá trị
mà c có thể nhận được. Nếu duyệt theo biến c thì có rất nhiều khả năng nên thay vì duyệt
theo biến c ta duyệt theo a và b. Vai trò của các số bằng 1 và các số bằng -1 là như nhau
nên ta có thể giả sử số lượng số bằng 1 lớn hơn số lượng bằng -1 (a>=b).
Vậy xi = a-b và xi2<sub> = a+b (i = 1,..,N)</sub>
xixj = P (i =1, ..., N; j =1, ..., N; i<>j) suy ra P =2*xixj (i =1, ..., N -1; j =1, ..., N; i<j)
Ta có phương trình: (a+b)+p=(a-b)2
suy ra 0 <= (a-b) <= sqrt(a+b+p) <= sqrt(N+p)<[sqrt(2*1010<sub>)] = 44721. </sub>
Vậy ứng với mỗi giá trị (a-b) ta có một giá trị (a+b) và một giá trị c. Lần lượt thử với
từng giá trị của (a-b) rồi kiểm tra xem a, b và c thoả mãn các tính chất khơng?
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
uses crt;
const fi ='input.txt';
fo ='output.txt';
var n,p, h :longint;
dem :longint;
t :real;
procedure docf;
var f :text;
begin
assign(f,fi);
reset(f);
read(f,n,p);
close(f);
dem:=0;
end;
procedure lam;
var can :longint;
begin
can:=trunc(sqrt(2*n));
for h:=0 to can do
begin
t:=h;
t:=sqr(t)-p;
if (t>=h)and(t<=n) then inc(dem);
end;
end;
procedure ghif;
var f :text;
begin
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
rewrite(f);
writeln(f,dem);
close(f);
end;
BEGIN
docf;
if p mod 2=0 then lam;
ghif;
END.
</div>
<!--links-->
