KHỐI THI TẬP THỂ

Bài 1: Triangle

Đây là bài tương đối dễ, chỉ cần kiểm tra một trong các khả năng a*a=b*b+c*c

b*b=a*a+c*c

c*c=a*a+b*b

Kiểu dữ liệu dùng để khai báo 3 số a,b,c là int. Không có lưu ý gì đặc biệt trong bài này.

Bài 2: Number

Đây cũng là một bài khá đơn giản. Tuy nhiên cần phải lưu ý đến điều kiện N<=10^200. Với các kiểu dữ liệu số nguyên trên C/C++ chúng ta không thể lưu trữ được số lớn đến 10^200. Để biểu diễn số N, trong bài này cần sử dụng xâu ký tự. Việc tiếp theo là cần kiểm tra xem xâu ký tự đó có đối xứng hay không. Chương trình chỉ đơn giản như sau:

int ktra(char* s){

int l=strlen(s);

for(int i=0;i<=l/2;i++)

if(s[i]!=s[l-1-i]) return 0;

return 1;

}

void main(){

char s[300];

scanf("%s",s);

printf("%d",ktra(s));

}

Với bài này, có thể không cần dùng hàm phụ trợ, việc kiểm tra tính đối xứng có thể đưa luôn vào hàm main()

Bài 3: Conflict

Bài này chúng ta cần phải giải quyết hai bài toán con: tìm các chữ số của một số nguyên và tìm ước số chung lớn nhất của hai số nguyên. Hai bài toán này là những bài toán cơ bản và không có gì khó

Để giải bài toán con thứ nhất, ta dùng mảng số nguyên để lưu trữ các chữ số. Chương trình như sau:

int uscln(int a, int b){

if (a==0) return b;

if(b==0) return a;

if (a>b) return uscln(a%b,b);

else return uscln(a, b%a);

}

void main(){

int N,temp,i,so_chu_so=0;

int a[10];

scanf("%d",&N);

//Tìm các chữ số của N:

temp=N;

while(temp>0){

a[so_chu_so]=temp%10;

temp=temp/10;

so_chu_so++;

}

//Tính số đảo ngược của N và lưu vào temp:

temp=0;

for(i=0;i<so_chu_so;i++)

temp=temp*10+a[i];

//Đưa ra kết quả

printf("%d",(uscln(N,temp)==1));

}

Lưu ý: Khi tìm USCLN cần giảm tham số bằng cách a=a%b hoặc b=b%a. Nếu giảm tham số bằng cách a=a-b hoặc b=b-a thì sẽ gây tràn stack khi N lớn do số lần đệ quy quá nhiều.

Bài 4: SUBARR

Để giải bài này đầu tiên có thể sử dụng 2 vòng lặp lồng nhau, vòng bên trong tìm tổng lớn nhất các phần tử liên tiếp bắt đầu từ chỉ số i, vòng bên ngoài tìm tổng lớn nhất trong các tổng tìm được. Theo cách này độ phức tạp sẽ là O(n^3).

Cách khác:

Gọi mảng b là mảng như sau:

b[i]=a[0]+a[1]+…+a[i], 0<=i<=n-1;

Việc tiếp theo là cần tìm giá trị lớn nhất trong b[0], b[1],…,b[n-1], b[j]-b[i] (với mọi n-1>=j>i>=0). 

Độ phức tạp theo cách này O(n^2).

Bài 5: PERMUTATION

Đây cũng là bài toán cơ bản. Chỉ cần biết thuật toán liệt kê các hoán vị.

Gọi (a1,a2,a3...an) là hoán vị được cho

Nếu hoán vị được cho là (n,n-1,…,1) thì đưa ra 0. Kiểm tra điều này rất đơn giản: duyệt xem tất cả ai có bằng n+1-i hay không (i=1,2,..,n)

Nếu a=(a1,a2,a3...an) là môt hoán vị chưa phải là hoàn vị cuối cùng thì hoán vị kế tiếp của a được xác định như sau:

-Tìm từ phải qua trái trong hoán vị đang có chỉ số k đầu tiên thỏa mãn ak<ak+1.

-Trong các phần tử ở bên phải của ak và lớn hơn ak tìm phần tử nhỏ nhất ai.

-Đổi chỗ hai phần tử ak và ai.

-Lật ngược đoạn các phần tử từ ak+1 đến an.

VD với n=6 và hoán vị đang xét là a=(3,6,2,5,4,1) thì chỉ số k cần tìm là k=3 (vì a3=2<a4=5).Chỉ số i=5 (vì a5=4).Đổi chỗ a3 và a5 ta được hoán vị (3,6,4,5,2,1)và lật ngược đoạn từ ak+1 tức là đoạn từ a4 đến a6 (Đoạn 5,2,1) ta được hoán vị kế tiếp cần tìm là(3,6,4,1,2,5).

Ngoài cách tự viết chương trình theo thuật toán trên, có thể sử dụng hàm next_permutation() trong thư viện <algorithm> của STL.

Bài 6: Func

Ý tưởng giải bài này dựa trên phương pháp quy hoạch động. Giả sử đối với dãy a1,a2,…,a[n-1] đã tìm được 3 chỉ số 1<=i’<j’<k’<=n-1 để f(i’,j’,k’)=a[i’]+3a[j’]+5a[k’] đạt giá trị lớn nhất. Với dãy a1,a2,…,a[n-1],a[n] thì bộ ba số 1<=i<j<k<n phải tìm để f(i,j,k) đạt giá trị lớn nhất sẽ là bộ trong các bộ ba số (i’,j’,k’),(i’,j’,n),(j’,k’,n),(i’,k’,n) đem lại giá trị lớn nhất cho f(i,j,k).

Để cài đặt, trong chương trình ta khai báo 3 biến toàn cục int i,j,k;

Ban đầu với dãy a1,a2,a3: hiển nhiên i=1, j=2, k=3. 

Sau đó lần lượt tính i,j,k cho các dãy tiếp theo:

for(s=4;s<=n;s++){

f1=a[i]+3*a[j]+5*a[k];

f2=a[i]+3*a[j]+5*a[s];

f3=a[j]+3*a[k]+5*a[s];

f4=a[i]+3*a[k]+5*a[s];

tính fm=max(f1,f2,f3,f4);

nếu fm==f1 continue;

nếu fm==f2 {k=s;continue;}

nếu fm==f3 {i=j;j=k;k=s;continue;}

nếu fm==f4 {j=k;k=s;continue;}

}

Đưa ra tổng a[i]+3*a[j]+5*a[k];

Độ phức tạp O(n-3). Nếu sử dụng duyệt vét cạn thì độ phức tạp là O(n^3).

KHỐI CÁ NHÂN CHUYÊN TIN

Bài 1: Squared

Bài này tương đối đơn giản, chỉ cần sử dụng một vòng for

void main(){

for(int i=0;i<100;i++)

if (i*i==N) {cout<<"YES";return;}

cout<<"NO";

}

Lưu ý: Không nên dùng hàm sqrt(x) để tính căn bậc 2 vì hàm này sử dụng chuỗi để tính (tốc độ kém hơn).

Bài 2: Max_Div

int uscln(int a, int b){

if (a==0) return b;

if(b==0) return a;

if (a>b) return uscln(a%b,b);

else return uscln(a, b%a);

}

Bài 3: Stairs

Đây là bài quy hoạch động điển hình. Cần tìm số cách biểu diễn số nguyên dương n thành tổng một số số nguyên dương n=a[1]+a[2]+…+a[t] với 1<=t<=n và 1<=a[1]<a[2]<…<a[t]

Gọi F(n,k) là hàm tính số lượng cách biểu diễn n thành tổng các số như trên với a[t]<=k (1<=k<=n). Khi đó a[t] chỉ có thể có hai khả năng a[t]=k và a[t]<k.

Với a[t]=k thì a[1]+a[2]+…+a[t-1]=n-a[t]=n-k. (1)

Vì a[t-1]<a[t] nên a[t-1]<=k-1. (2)

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]<k thì suy ra a[t]<=k-1 và số cách biểu diễn n thành tổng trong trường hợp này là F(n,k-1). (4)

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<N;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