TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN CÂU LẠC BỘ LẬP TRÌNH CPT | CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc |
|
TPHCM, ngày 20 tháng 03 năm 2015 |
Cuộc Thi Lập Trình Olympia IT
Đề Chính Thức Tuần 1
Câu 1. (6đ)
Trong kho hàng có n hộp rỗng, mỗi hộp có chiều dài chiều rộng, chiều cao xác định và số thứ tự xác định. Một hộp A có thể bỏ vào hộp B nếu hộp B là rỗng và hộp A có thể quay sao cho các chiều của hộp A nhỏ hơn hộp B. Người công nhân làm gọn số hộp bằng cách với mỗi hộp từ hộp đầu tiên, anh ta sẽ tìm hộp rỗng gần nó nhất và có số thứ tự sau nó và bỏ vào nó. Nếu không có hộp nào thỏa mãn anh ta tiêp tục làm thế với hộp thứ 2, thứ 3…
Input : cho n hộp và chỉ số các hộp (n<=300)
Output: số hộp còn lại sau khi anh công nhân dừng lại
Ví Dụ:
Input:
21
1 4 2
6 5 2
6 3 7
8 8 2
6 3 3
4 4 9
9 5 6
4 1 6
4 19 8
13 1 8
8 17 7
13 18 16
11 10 8
11 14 4
18 25 28
26 2 19
23 21 22
15 8 15
14 27 13
26 14 17
23 28 6
Output:
6
#include<iostream>
using namespace std;
void sapxep(int a[][3],int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<2;j++)
for(int k=j+1;k<3;k++)
if(a[i][j]>a[i][k]) swap(a[i][j],a[i][k]);
}
}
void xoa(int a[][3],int &n,int x)
{
for(int i=x;i<n-1;i++)
{
a[i][0]=a[i+1][0];
a[i][1]=a[i+1][1];
a[i][2]=a[i+1][2];
}
n--;
}
int XepHopRong(int a[][3],int n)
{
int kq=0,i,j,k,m;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
if(a[i][0]<a[j][0] && a[i][1]<a[j][1] && a[i][2]<a[j][2])
{
a[i][0]=a[j][0];
a[i][1]=a[j][1];
a[i][2]=a[j][2];
xoa(a,n,j);
j--;
}
kq++;
}
return kq;
}
void main()
{
int a[300][3],n,ketqua,i=0;
FILE *f1=fopen("bai1.inp","r");//file chua du lieu vao
FILE *f2=fopen("bai1.out","w");//fle chua du lieu ra
if(f1==NULL || f2==NULL)
{
cout<<"file du lieu khong co! hay tao file !\n";
system("pause");
exit(1);
}
fscanf(f1,"%d",&n);
while(!feof(f1))
{
fscanf(f1,"%d",&a[i][0]);
fscanf(f1,"%d",&a[i][1]);
fscanf(f1,"%d",&a[i][2]);
i++;
}
sapxep(a,n);
ketqua=XepHopRong(a,n);
fprintf(f2,"%d",ketqua);
cout<<"\nda xong!!\n";
fcloseall();
system("pause");
}
Câu 2. (7đ)
Cho một dãy số a gồm n số và một số tự nhiên k. Hãy tìm trong dãy số đã cho tất cả những số chính phương chia hết cho k. Với số chính phương được định nghĩa là bình phương (lũy thừa bậc 2) của một số tự nhiên khác.
Input
Dòng đầu gồm hai số n và k (n<=1000, k<=106)
Dòng tiếp theo chứa n số tự nhiên a[1],a[2]…a[n] (a[i]<=106)
Output
Dãy các số chính phương thỏa mãn yêu cầu đề (yêu cầu giữ nguyên thứ tự so với input)
Ví Dụ:
Input:
6 4
1 3 16 7 9 256
Output:
16 256
#include<iostream>
using namespace std;
int SoChinhPhuong(float n)
{
if((float)sqrt(n)-(int)sqrt(n)==0) return 1;
return 0;
}
void main()
{
FILE *f1=fopen("bai2.inp","r");
FILE *f2=fopen("bai2.out","w");
if(f1==NULL || f2==NULL)
{
cout<<"\nfile du lieu khong co!\n";
system("pause");
exit(1);
}
unsigned long *a=new unsigned long[1000],k,m;
int n,i=0;
fscanf(f1,"%d",&n);
fscanf(f1,"%lu",&k);
while(!feof(f1))
{
fscanf(f1,"%lu",&m);
a[i++]=m;
}
for(i=0;i<n;i++)
if(SoChinhPhuong(a[i]) && a[i]%k==0) fprintf(f2,"%lu ",a[i]);
cout<<"\nda xong!\n";
fcloseall();
system("pause");
}
Câu 3.(7đ)
Một hòn đảo có 1000000 dân, từ khi sinh ra đời họ đã tự nhiên được đánh dấu thứ tự từ 1 đến 1000000. vị thần của hòn đảo phù hộ cho một người dân nếu anh ta/ cô ta có số thứ tự có thể được viết thành a^b với a là số nguyên tố và b là số nguyên dương bất kì (b>1). Thậm chí ông ta sẽ phong thánh nếu b%a=0 . Tất cả người dân được phù hộ đều được ban cho 1 khả năng đặc biệt, còn người được phong thánh sẽ được ban a khả năng đặc biệt. Để không bỏ sót bất kì người nào, thần chia hòn đảo này gồm nhiều khu vực, mỗi khu vực đều bao gồm người dân từ số thứ tự X đến số thứ tự Y. Và bạn được giao nhiệm vụ tìm kiếm số lượng khả năng đặc biệt của từng khu vực ấy
Input:
Dòng đầu là n chỉ số khu vực (n<100)
Cho n dòng, mỗi dòng gồm hai số nguyên dương x, y (1<=x<=106; 1<=y<=106), số thứ tự người dân mỗi khu vực sẽ x<= và <=y
Output:
N dòng, mỗi dòng là số lượng khả năng đặc biệt của mỗi khu vực
Ví Dụ:
Input:
6
545168 707907
774380 899267
291786 519538
992275 996865
769714 916113
78337 328492
Output:
19
17
35
1
19
61
#include<iostream> using namespace std; int snt(int n) { if(n<2) return 0; if(n==2) return 1; for(int i=2;i<n;i++) if(n%i==0) return 0; return 1; } unsigned long kiemtra(float a[],unsigned long m,float b[],float n) { unsigned long e=0,f=0; float q,g; while(e<m && a[e]<n) { b[e]=0; g=log(n)/log(a[e]); q=float(g)-unsigned long(g); if(q==0) { b[e]=g; f++; } e++; } if(f==0) return 0; g=0; for(e=0;e<=f;e++) if(b[e]!=0) if(unsigned long(b[e])%unsigned long(a[e])==0) return a[e]; return 1; } void main() { FILE *f1=fopen("bai3.inp","r"); FILE *f2=fopen("bai3.out","w"); if(f1==NULL || f2==NULL) { cout<<"\nfile du lieu khong co!\n"; system("pause"); exit(1); } int n; unsigned long x=0,y,k,i,m; fscanf(f1,"%d",&n); cout<<"\ndang chay! vui long doi!..."; float *a=new float[1000000]; float *b=new float[1000000]; fscanf(f1,"%lu",&y); while(!feof(f1)) { fscanf(f1,"%lu",&x); if(y<x) y=x; } x=0; for(i=2;i<=y;i++) if(snt(i)) a[x++]=i; m=x; rewind(f1); fscanf(f1,"%d",&n); int dem=1; while(!feof(f1)) { cout<<"\nDang Kiem Tra Khu Vuc "<<dem++; k=0; fscanf(f1,"%lu",&x); fscanf(f1,"%lu",&y); for(i=x;i<=y;i++) k=k+kiemtra(a,m,b,i); fprintf(f2,"%lu\n",k); } delete a; delete b; cout<<"\nda xong!!\n"; fcloseall(); system("pause"); }
Lưu ý: Tất cả các bài đều nhập xuất từ file. Các file nhập xuất đặt tên theo định dạng sau: bai1.inp, bai1.out; bai2.inp, bai2.out; bai3.inp,bai3.out.
