Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Saturday, March 28, 2015


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.

0 comments:

Post a Comment

Popular Posts