Tuyển tập 1 số đề thi và code các kỳ thi OLP tin học sinh viên toàn quốc

 
{ 
 int OLP=0,nn=n; 
 while (nn) 
 { 
 if(l->ci >= 0 && c[l->ci].count>0 ) 
 c[l->ci].ed=true; 
 int k=0; 
 while (!c[k].ed) k++; 
 //cout << k<<endl; 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
37 
 l->ci=k; 
 l=l->next; 
 if (k<n) 
 { 
 c[k].count--; 
 if (!c[k].count) 
 nn--; 
 c[k].ed=false; 
 } 
 OLP++; 
 } 
 return OLP; 
} 
int main() 
{ 
 ifstream infile("el.txt"); 
 infile >> n >>m; 
 nodemang *c; 
 c=new nodemang[n+1]; 
 for(int i=0; i<n; i++) 
 infile>>c[i].count; 
 // sap xep 
 for (i=0; i<n-1; i++) 
 for (int j=i+1; j<n;j++) 
 if (c[i].count<c[j].count) 
 { 
 nodemang t=c[i]; 
 c[i]=c[j]; 
 c[j]=t; 
 } 
 nodevong* l=NULL; 
 tao_vong(l,m); 
 cout << tinhthoigian(l,c)<<endl; 
 return 0; 
} 
Bài: Dãy số (Ko chuyên 2009) 
Cho dãy số gồm n số nguyên a1, a2, , an. Tìm giá trị lớn nhất của hàm 
f (i,j,k)= ai +2× aj +3× ak với 1 ≤ i < j < k ≤ n. 
Ví dụ: với dãy gồm 5 số -1, 2, -2, -3, 5 thì f (1,2,5)=-1+2×2+3×5=18 là lớn nhất. 
Dữ liệu: Vào từ file văn bản SEQUENCE.INP: 
• Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 10^5), 
• Dòng thứ i trong n dòng tiếp theo chứa số nguyên ai (|ai| ≤ 10^9). 
Kết quả: Đưa ra file văn bản SEQUENCE.OUT một số nguyên – giá trị lớn nhất của 
hàm f (i,j,k)tìm được. 
Ví dụ: 
SEQUENCE.INP 
5 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
38 
-1 
2 
-2 
-3 
5 
SEQUENCE.OUT 
18 
// Code của @Sounj 
// Dùng : Quy Hoạch Động 
#include 
#include 
#define MAX 100000 
using namespace std; 
int max_f(int a[], int N) 
{ 
 if(N<3) return 0; 
 int f[MAX]; 
 int luu, tg; 
 int i; 
 // vòng lặp đầu tiên: f = ai 
 f[0] = a[0]; 
 for(i=1; i<N; i++) 
 if(f[i-1]<a[i]) f[i]=a[i]; else f[i] = f[i-1]; 
 // vòng lặp thứ 2: f = ai + 2* a[j] 
 luu = f[1]; f[1] = f[0] + a[1]*2; 
 for(i=2; i<N; i++) 
 { 
 tg = f[i]; 
 if(f[i-1]<luu+a[i]*2) f[i] = luu+a[i]*2; else f[i] = f[i-1]; 
 luu = tg; 
 } 
 // vòng lặp thứ 3: f = ai + 2* a[j] + 3*a[k] 
 luu = f[2]; f[2] = f[1] + a[2]*3; 
 for(i=3; i<N; i++) 
 { 
 tg = f[i]; 
 if(f[i-1]<luu+a[i]*3) f[i] = luu+a[i]*3; else f[i] = f[i-1]; 
 luu = tg; 
 } 
 return f[N-1]; 
} 
void main() 
{ 
 int a[] = {-1, 2, -2, -3, 5}; 
 int N = 5; 
 cout<<"Ket qua: "<< max_f(a, N); 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
39 
 getch(); 
} 
// Code của @hunterphu 
// Dùng : Quy Hoạch Động 
#include 
#define k -1000000000 
using namespace std; 
long long a[100001]; 
int n; 
long long x=k,y=k,z=k; 
int main() 
{ 
 scanf ("%d",&n); 
 for (int i=1;i<=n;i++) 
 { 
 scanf ("%I64d",&a[i]); 
 x=max(x,y+3*a[i]); 
 y=max(y,z+2*a[i]); 
 z=max(z,a[i]); 
 } 
 printf ("%I64d",x); 
 system("pause"); 
 return 0; 
} 
Bài :Kết bạn (Ko chuyên 2009) 
 Theo quan niệm của người Á Đông cổ, mỗi cá nhân khi sinh ra đều ứng với một ngôi sao, 
được gọi là sao chiếu mệnh. Các hoạt động của cá nhân đều bị chi phối bởi ngôi sao này, kể cả 
quá trình kết bạn – hẹn hò. Theo thuyết Âm dương – Ngũ hành, hai người chỉ có thể tạo lập mối 
quan hệ bền vững khi các sao chiếu mệnh của họ không có các thuộc tính tương khắc. Qua hàng 
nghìn năm quan sát và chiêm nghiệm, các chiêm tinh gia đã ghi nhận được n sao và hầu hết các 
tính chất tương sinh – tương khắc giữa chúng. Để có thể nhanh chóng đáp ứng nhu cầu kiểm tra 
độ tương hợp của các sao, hiệp hội ABS (Association of Broker for Single) tạo lập cơ sở dữ liệu 
ghi nhận tính chất của tất cả các sao đã khảo sát được. Trong cơ sở dữ liệu này, các sao được 
đánh số từ 1 tới n; sao thứ i có một giá trị si thể hiện khả năng thích nghi của sao gọi là độ thích 
nghi. Hai sao khác nhau có thể có cùng độ thích nghi. Thông qua độ thích nghi của các sao, 
người ta xác định khả năng tương hợp của chúng. Khả năng tương hợp của 2 sao được tính bằng 
tổng 2 độ thích nghi của chúng. 
Bài toán: Cho số nguyên dương n, dãy s1, s2, , sn là độ thích nghi của các sao và số nguyên 
B. Hãy xác định số lượng các cặp sao (i, j) mà si + sj = B, với 1 ≤ i < j ≤ n. 
Ví dụ: trong 5 sao với độ thích nghi 3, 5, 6, 5, 3 có 4 cặp có khả năng tương hợp bằng 8. 
Dữ liệu: Vào từ file văn bản FRIEND.INP: 
• Dòng đầu tiên ghi 2 số nguyên n, B (2 ≤ n ≤ 10^5, |B| ≤ 10^9), 
• Mỗi dòng trong n dòng tiếp theo ghi một số nguyên là độ thích nghi của một 
sao, độ thích nghi có trị tuyệt đối bé hơn 2^15 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
40 
. 
Hai số trên cùng dòng cách nhau ít nhất một dấu cách. 
Kết quả: Đưa ra file văn bản FRIEND.OUT một số nguyên – số lượng cặp sao có 
độ tương hợp B tìm được. 
Ví dụ 
FRIEND.INP 
5 8 
3 
5 
6 
5 
3 
FRIEND.OUT 
4 
// Code của @hienclubvn 
#include 
#include 
#define IN "FRIEND.INP" 
#define OUT "FRIEND.OUT" 
long *A; 
int n,B,count=0; 
void Read() 
{ 
 FILE *fin; 
 fin=fopen(IN,"r"); 
 fscanf(fin,"%d %d",&n,&B); 
 // Cap Phat bo nho dong 
 A=(long*)malloc(n*sizeof(long)); 
 int i; 
 for(i=0;i<n;i++) 
 fscanf(fin,"%d",&A[i]); 
 fclose(fin); 
} 
void Write() 
{ 
 FILE *fout; 
 fout=fopen(OUT,"w"); 
 fprintf(fout,"%d\n",count); 
 fclose(fout); 
} 
void Process() 
{ 
 int i,j; 
 for(i=0;i<n-1;i++) 
 for(j=i+1;j<n;j++) 
 if(A[i]+A[j]==B) count++; 
} 
int main() 
{ 
 Read(); 
 Process(); 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
41 
 Write(); 
 return 0; 
} 
// Code của @Vibzz90 
#include 
#include 
using namespace std; 
const char in[]="bai1in.txt"; 
const char out[]="bai1out.txt"; 
int *a; 
long n,B; 
int sosanh(void const *a1, void const *a2) 
{ 
 return (*(int*)a1-*(int*)a2); 
} 
int process() 
{ 
 int dem=0; 
 long buf; 
 qsort(a,n,sizeof(int),sosanh); 
 for(int i=0;i<n;i++){ 
 for(int j=i+1;j<n;j++) 
 { 
 buf=a[i]+a[j]; 
 if(buf==B) dem++; 
 if(buf>B) break; 
 } 
 } 
 return dem; 
} 
void input() 
{ 
 ifstream f(in); 
 f>>n>>B; 
 a=new int[n]; 
 for(int i=0;i>a[i]; 
 f.close(); 
} 
void gentest() 
{ 
 cout<<"Nhap n,B: "; 
 cin>>n>>B; 
 ofstream f(in); 
 f<<n<<" "<<B<<endl; 
 srand(time(NULL)); 
 for(int i=0;i<n;i++) 
 f<<(rand()+rand()-32768)<<endl; 
 f.close(); 
} 
int main() 
{ 
 cout<<"gentest?"; 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
42 
 int choice;cin>>choice; 
 if(choice) gentest(); 
 input(); 
 cout<<process()<<endl; 
 system("pause"); 
 return 0; 
} 
Bài: Hiệu chỉnh ảnh đơn sắc (Ko chuyên 2009) 
Ảnh đơn sắc là ảnh chỉ gồm một màu nhưng các vùng trên ảnh khác nhau về mức sáng 
– ví dụ ảnh xám (grayscale image). Để biểu diễn một ảnh đơn sắc hình chữ nhật trên máy tính, 
người ta thường dùng một ma trận P, giá trị tại dòng i cột j của P chính là mức sáng của điểm 
ảnh tại vị trí tương ứng trên ảnh. 
Việc chụp và đưa ảnh vào máy tính thỉnh thoảng có sai sót tạo nên nhiễu. Nhiễu là các điểm ảnh 
có độ sáng khác hẳn vùng ảnh xung quanh. Có nhiều cách làm giảm sự khác biệt này. Một trong 
những cách đó là dùng một cửa sổ hình vuông 3x3 có cạnh song song với cạnh của ảnh và hiệu 
chỉnh các điểm ảnh trong vùng ảnh bị nhiễu. Mỗi điểm ảnh ở dòng i cột j sẽ được thay thế bằng 
trung vị của các giá trị ảnh đang có trong cửa sổ có tâm tại vị trí (i, j) ở ảnh gốc ban đầu. Trong 
các trường hợp điểm ảnh ở biên, chỉ xét trung vị của các giá trị nằm trong ảnh. 
Nhắc lại rằng, trung vị của k số a1, a2,  ak là số ở vị trí t khi sắp xếp k số này theo trật tự tăng 
dần, trong đó t là phần nguyên của số (k+1)/2 
Dưới đây là ví dụ mô tả việc hiệu chỉnh ảnh bằng cách nêu trên. 
Bài toán: Cho ma trận số nguyên P cấp m× n biểu diễn một vùng ảnh đơn sắc có nhiễu. 
Hãy dùng cách đã nêu ở trên để hiệu chỉnh các điểm ảnh trong vùng ảnh bị nhiễu. 
Dữ liệu: Vào từ file văn bản ADJUST.INP gồm: 
• Dòng đầu tiên chứa 2 số nguyên m, n (1 ≤m, n ≤ 100), 
• m dòng tiếp theo mỗi dòng ghi n số nguyên không âm là mức sáng các điểm 
ảnh. Giá trị mức sáng không vượt quá 255. 
Kết quả: Đưa ra file văn bản ADJUST.OUT gồm m dòng, mỗi dòng gồm n số là các 
mức sáng trong vùng ảnh sau khi đã hiệu chỉnh. 
Hai số trên cùng dòng cách nhau ít nhất một dấu cách. 
Ví dụ: 
ADJUST.INP 
4 5 
10 11 12 13 14 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
43 
15 0 16 17 11 
4 5 6 7 8 
2 10 6 7 5 
ADJUST.OUT 
10 11 12 13 13 
5 10 11 12 11 
4 6 7 7 7 
4 5 6 6 7 
// Code của @hienclubvn 
#include 
#include 
#define IN "ADJUST.INP" 
#define OUT "ADJUST.OUT" 
int **A,**T,m,n; 
void Input() 
{ 
 FILE *fin; 
 fin=fopen(IN,"r"); 
 int i,j; 
 fscanf(fin,"%d %d",&m,&n); 
 // Cap phat dong 
 A=(int**)malloc(m*sizeof(int)); 
 for(i=0;i<m;i++) A[i]=(int*)malloc(n*sizeof(int)); 
 T=(int**)malloc(m*sizeof(int)); 
 for(i=0;i<m;i++) T[i]=(int*)malloc(n*sizeof(int)); 
 // read File 
 for(i=0;i<m;i++) 
 for(j=0;j<n;j++) fscanf(fin,"%d",&A[i][j]); 
 fclose(fin); 
} 
void Sort(int *B,int n) 
{ 
 int i,j; 
 for(i=0;i<n-1;i++) 
 for(j=i+1;j<n;j++) 
 if(B[i]>B[j]) 
 { 
 int temp=B[i]; 
 B[i]=B[j]; 
 B[j]=temp; 
 } 
} 
int FindPoint(int i,int j) 
{ 
 int B[10]; 
 int k,l,m1,n1,t=0; 
 int di[3]={-1,0,1}; 
 int dj[3]={-1,0,1}; 
 for(k=0;k<3;k++) 
 { 
 m1=i+di[k]; 
Ngoâ Ñaêng Hieàn – Hoïc Vieän Haûi Quaân 2011 
44 
 for(l=0;l<3;l++) 
 { 
 n1=j+dj[l]; 
 if(m1>=0&&m1=0&&n1<n) 
 B[t++]=A[m1][n1]; 
 } 
 } 
 Sort(B,t); 
 int p=(t+1)/2-1; 
 int x=B[p]; 
 return x; 
} 
void Process() 
{ 
 int i,j; 
 for(i=0;i<m;i++) 
 for(j=0;j<n;j++) 
 { 
 T[i][j]=FindPoint(i,j); 
 } 
} 
void Output() 
{ 
 FILE *fout; 
 fout=fopen(OUT,"w"); 
 int i,j; 
 for(i=0;i<m;i++) 
 { 
 for(j=0;j<n;j++) 
 if (j!=n-1)fprintf(fout,"%d ",T[i][j]); 
 else fprintf(fout,"%d\n",T[i][j]); 
 } 
 fclose(fout); 
} 
int main() 
{ 
 Input(); 
 Process(); 
 Output(); 
 free(A); 
 free(T); 
 return 0; 
}