Suy ra số cách biểu diễn n thành tổng các số với số cuối cùng bằng k sẽ là F(n-k,k-1) (theo (1) và (2)). (3)
Với a[t]
Từ (3) và (4) nhận được F(n,k)=F(n,k-1)+F(n-k,k-1)
Dễ dàng nhận thấy
F(0,k) = 1
F(0,0)=1
F(n,0) =0 với n>0.
Kết quả cần tìm là F(n,n).
Bài 4: BEE
Bài này liên quan đến hình học vector. Ta quy định ô lục giác xuất phát là gốc tọa độ O trong hệ tọa độ OXYZ. Ký hiệu nx,ny,nz là 3 vector đơn vị theo hướng 3 trục X,Y,Z. Theo công thức cộng vector và tính chất của 3 trục X,Y,Z có thể thấy rằng
nx+nz=ny (1)
Đường đi của con ong từ gốc tọa độ đến ô lục giác có mật có thể biểu diễn dưới dạng
A*nx+B*ny+C*nz (2)
Với ví dụ cho trong bài thì để đi đến ô có mật con ong cần đi theo đường
-2*nz+3*ny+3*nz-nz=-nx+3*ny+nz, nghĩa là với ví dụ đã cho thì A=-1,B=3,C=1.
Để tìm 3 hệ số A,B,C ta đọc từ file BEE.IN, giả sử f là biến file:
char c;
int d,A,B,C;
A=B=C=0;
fscanf(f,”%d”,&N);//Đọc số lần dịch chuyển
for (int i=0;i
fscanf(f,”%c%d”, &c,&d);//đọc hướng và độ dịch theo hướng
if (c==’X’) A=A+d;
if (c==’Y’) B=B+d;
if (c==’Z’) C=C+d;
}
fclose(f);
Sau khi đã tìm được 3 số A,B,C thì có thể thấy rằng muốn đi về ô xuất phát (gốc tọa độ) thì con ong có thể đi theo đường là –A*nx-B*ny-C*nz. Tuy nhiên 3 vector nx,ny,nz theo (1) không độc lập tuyến tính nên để đi về gốc tọa độ, con ong chỉ cần di chuyển theo 2 phương là đủ.
Theo (1) thì
A*nx+B*ny+C*nz=(A+B)*nx+(B+C)*nz=(A-C)*nx+(B+C)*ny
=(B+A)*ny+(C-A)*nz.
Và con đường ngắn nhất cần phải tìm là
min(|A+B|+|B+C|,|A-C|+|B+C|,|B+A|+|C-A|)
Trong ví dụ đã cho (A=-1,B=3,C=1) con đường ngắn nhất là
min(2+4,2+4,2+2)=4.
KHỐI CÁ NHÂN KHÔNG CHUYÊN TIN
Bài 1: Circle
Bài này khá đơn giản, chỉ cần so sánh (xm-x)*(xm-x)+(ym-y)*(ym-y) và r*r.
Nếu (xm-x)*(xm-x)+(ym-y)*(ym-y)> r*r thì M nằm ngoài đường tròn
Nếu (xm-x)*(xm-x)+(ym-y)*(ym-y) = = r*r thì M nằm trên đường tròn
Nếu (xm-x)*(xm-x)+(ym-y)*(ym-y)< r*r thì M nằm trong đường tròn
Tuy nhiên cần lưu ý sử dụng kiểu dữ liệu để biểu diễn các tham số đầu vào xm,ym,x,y,r. Nếu sử dụng kiểu int thì (xm-x)^2+(ym-y)^2 hay r^2 có thể vượt ra ngoài khoảng cho phép của số int và đem lại kết quả thực tế là số âm, hệ quả là đưa ra kết quả sai (ví dụ x=-999999, y=-999999, r=999999, xm=999999, ym=999999). Vì vậy kiểu dữ liệu cần dùng để khai báo xm,ym,x,y,r phải là float hoặc double.
Nếu vẫn khai báo các tham số có kiểu int thì phải sử dụng hàm sqrt để tính khoảng cách từ (xm,ym) đến (x,y). Khi đó cần so sánh
sqrt((float) (xm-x)*(xm-x)+(ym-y)*(ym-y)) và r
Tuy nhiên theo cách này thì sẽ phải tính đến độ chính xác 10^-6, sẽ rắc rối hơn.
Bài 2: Squared
Xem ở trên
Bài 3: Max_Div
Xem ở trên
Bài 4: BEE
Xem ở trên
Người viết
Phan Nguyên Hải
Chia sẻ với bạn bè của bạn: