Thứ Ba, 31 tháng 3, 2015

[đệ quy] viết hàm để duyệt mảng, xuất các phần tử của mảng

[đệ quy] viết hàm để duyệt mảng, xuất các phần tử của mảng ra màn hình theo thứ tự nhập.

//bai 2
#include <iostream>
using namespace std;
void xuat(int a[],int left,int right)
{
if(left>right) return;
cout<<a[left++]<<" ";// a[left++] == a[left]; va sau do left++;(viet gon)
xuat(a,left,right);// cout<<a[left++]<<" "; == printf("%d ",a[left]);left++;
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10},n=10;
xuat(a,0,n-1);
system("pause");
}

theo thứ tự ngược lại so với lúc nhập

//bai 3
#include <iostream>
using namespace std;
void xuat(int a[],int n)
{
if(n==0) return;
cout<<a[n-1]<<" ";
n--;
xuat(a,n);
}
void main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10},n=10;
xuat(a,n);
system("pause");
}

Thứ Hai, 30 tháng 3, 2015

đề thi lập trình olympia IT tuần 2


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  28 tháng 03 năm 2015

Cuộc Thi Lập Trình Olympia IT
Đề Chính Thức Tuần 2
Câu 1. (6đ)
Xâu biểu thức.
Cho biểu thức có các phần tử x, các số nguyên, các dấu +, -, *, / (chia lấy phần nguyên), và (), Hãy tính giá trị của biểu thức đã cho với từng giá trị của x cho trước.
Các số trong biểu thức cũng như giá trị của x luôn < 106
Input : biểu thức và các giá trị của x (40%test sẽ không có dấu ())
Output: các giá trị của biểu thức tương ứng với x
Ví Dụ:
Input:
5x+2      // biểu thức (<255 kí tự)
3            // số giá trị của x (<100)
1 2 3      // các giá trị của x (x<1000000)
Output:
7 12 17  // các giá trị của biểu thức tương ứng với các giá trị của x
Câu 2. (7đ)
Robot đang đứng ở vị trí 0 0 trong bản đồ. Robot có thể nhận các lệnh L: về phía bên trái, R: về bên phải, U: tiến về phía trước, D: lùi ra sau, B: quay lại vị trí trước đó (lưu ý, nếu robot đã thực hiện lênh U, R, sau đó nhận lệnh B, B thì robot sẽ thực hiện lệnh L, D, còn nếu robot chưa thực hiện lệnh nào thì lệnh B sẽ không có tác dụng) và lệnh T (turn around, lệnh này sẽ đọc thêm lệnh tiếp theo và khiến robot quay 180 độ về phía sau nếu lệnh tiếp theo là D, quay 90 độ theo kim đồng hồ nếu lệnh tiếp theo là R, quay 90 độ ngược kim đồng hồ nếu lệnh tiếp theo là L, khiến robot đứng yên không di chuyển nếu lệnh tiếp theo là B hay U.)
Ban đầu robot đang quay lên trên
Hãy tìm tọa độ của robot sau khi thực hiện xong n chuỗi lệnh. (robot sẽ vẫn giữ nguyên vị trí và hướng quay sau khi thực hiện xong 1 chuỗi lệnh)
Input
N (N<100)
N dòng, mỗi dòng là 1 chuỗi lệnh cho robot (mỗi dòng <255 kí tự)
(40% test sẽ không có lệnh T)
Output
N dòng, mỗi dòng là tọa độ robot sau khi thực hiện chuỗi lệnh của dòng tương ứng
Ví Dụ:
Input:
4
UDLRTBBBBTUTRTLTDU
UUUU
TLUUUU
BBBB
Output:
0 0
0 -4
4 -4
0 -4


Câu 3.(7đ)
Một con robot đang ở trong một ma trận. bản đồ được vẽ bởi các kí tự 0, 1, 2, 3 trong đó, 0 là đường mà robot có thể đi được, 1 là tường, robot không thể vượt qua, 2 là vị trí của robot còn 3 là đích. Ngoài ra trong ma trận còn có thể có các cổng dịch chuyển được đánh số từ 4 đến 9, với cổng thứ i, robot sẽ tốn i đơn vị thời gian để dịch chuyển đến cổng tương tự, robot tốn 1 đơn vị thời gian để di chuyển từ ô hiện tại sang ô bên cạnh. Hãy tính thời gian nhanh nhất robot có thể đến được đích
Input: (40% test sẽ không có cổng dịch chuyển)
M, N : số hàng và số cột của ma trận (M,N < 250)
M dòng, mỗi dòng là 1 chuỗi biểu thị ma trận đó
Output:
Thời gian cần thiết để robot đến được đích
Ví Dụ:
Input:
10 10
1110000001
0002011101
0111010001
0400010111
0111110011
1400111011
1110000011
1110111001
1113111101
1111111101
Output:
15

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.

Thứ Bảy, 28 tháng 3, 2015

đề thi và code giải Olympia IT tuần 1 CPT


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.