tham khảo đề thi olympic đại học duy tân (vào giải thử và bàn luận nha)

[kid_191]

Bài 1: MA TRẬN
Một ma trận mxn được chứa trong một file văn bản có tên MATRAN.INP gồm: dòng đầu chứa hai số nguyên dương m, n. m dòng tiếp theo mỗi dòng chứa n phần tử của từng hàng của ma trận. Hãy viết chương trình đọc dữ liệu từ file MT.INP, tính tổng từng hàng của ma trận và ghi vào file văn bản có tên MATRAN.OUT trong đó, dòng đầu chứa số nguyên m, dòng thứ hai chứa tổng từng hàng của ma trận (0<m,n<=20).
Ví dụ:
MATRAN.INP MATRAN.OUT
5 4
3 8 –1 5
5 7 –8 0
4 –3 1 6
2 4 –1 7
3 6 8 -5 5
15 4 8 12 12

Bài 2: DỊCH SARS
Một cơ quan có N nhân viên được đánh số thứ tự từ 1 đến N. Mỗi người có một phòng làm việc riêng của mình. Do nhu cầu công việc, hàng ngày mỗi nhân viên có thể phải tiếp xúc với một số nhân viên khác. Vào một ngày làm việc bình thường, có một nhân viên bị nhiễm bệnh SARS, nhưng do không biết nên người này vẫn đi làm. Đến cuối ngày làm việc người ta mới phát hiện ra người nhiễm bệnh SARS đầu tiên, Khả năng lây lan của SARS rất nhanh chóng: một người nhiễm bệnh nếu tiếp xúc với một người khác có thể sẽ truyền bệnh cho người này.
Yêu cầu
Hãy giúp các bác sỹ kiểm tra xem cuối ngày hôm đó, có tối đa bao nhiêu người có thể sẽ nhiễm bệnh và đó là những người nào để còn cách ly. Người có tiếp xúc với người nhiễm bệnh được coi là người nhiễm bệnh.
Dữ liệu:
Dữ liệu vào từ file văn bản SARS.INP.
 Dòng đầu tiên ghi 2 số tự nhiên N và K (1< N  250, 1 K  N) tương ứng là số lượng người làm việc trong toà nhà và số hiệu của nhân viên đã nhiễm SARS đầu tiên.
 Dòng thứ I trong N dòng tiếp theo ghi danh sách những người có tiếp xúc với người thứ I theo cách sau: số đầu tiên J của dòng là tổng số nhân viên đã gặp người thứ I, tiếp theo là J số tự nhiên lần lượt là số hiệu của các nhân viên đó. Nếu J = 0 có nghĩa rằng không ai đã tiếp xúc với người thứ I.
Kết quả
Kết quả ghi ra file văn bản SARS.OUT như sau:
 Dòng đầu tiên ghi số S là tổng số người có thể bị lây nhiễm SARS.
 Dòng thứ 2 liệt kê tất cả các người có thể bị lây nhiễm SARS cần cách ly, danh sách cần được sắp theo thứ tự tăng dần của số hiệu nhân viên.
Trong file dữ liệu vào và file kết quả, các số trên một dòng cách nhau ít nhất một dấu cách.
Ví dụ:
SARS.INP SARS.OUT
5 1
2 2 3
2 1 3
1 2
1 5
1 4 3
1 2 3

Bài 3: Cấp số cộng
Cho một dãy gồm N số nguyên a1, a2, a3,..,an với |ai|  30000 (i = 1, 2,...,N). Hãy tìm trong dãy đó một dãy con dài nhất lập thành một cấp số cộng có công sai là d (0 < d  100).
Dữ liệu vào: đọc từ file văn bản CSCONG. INP, trong đó
- Dòng đầu ghi số N
- Dòng tiếp theo chứa N phần tử của dãy.
Dữ liệu ra: ghi ra file văn bản CSCONG.OUT, gồm
- Dòng đầu ghi số M là số phần tử và công sai d của dãy cấp số cộng tìm được.
- Dòng tiếp theo ghi dãy cấp số cộng từ dãy ban đầu.
Ví dụ:
CSCONG.INP CSCONG.OUT
10
1 2 3 -6 3 8 5 4 7 9 4 2
1 3 7 9

Bài 4: XẾP HÀNG MUA VÉ
Có N người xếp hàng mua vé. Ta đánh số những người xếp hàng từ 1 đến N theo thứ tự đúng trong hàng. Thời gian phục vụ bán vé cho người thứ i là ti. Mỗi người cần mua một vé nhưng được quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ. Người thứ i nhận mua vé cho người thứ i+1 thì thời gian mua vé cho 2 người là ri. Tìm phương án sao cho N người đều có vé với thời gian ít nhất.
Dữ liệu vào từ file văn bản TICK.INP có cấu trúc:
- Dòng thứ nhất ghi số N (1 < N ≤ 2000);
- Dòng thứ hai ghi N số nguyên dương t1, t2, …, tN
- Dòng thứ ba ghi N – 1 số r1, r2, …, rN-1
Kết quả ghi ra file văn bản TICK.OUT gồm:
- Dòng thứ nhất ghi tổng thời gian phục vụ bán vé
- Dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng (nếu không có ai thì quy ước ghi số 0).
Ví dụ:
TICK.INP TICK.OUT
5
2 5 7 8 4
3 9 10 10 17
1 0 3 0 5


------------------------------------ Hết --------------------------------------

[kidteam]

bài 2 là đề thi olp
dùng đồ thị và giải thuật tìm kiếm trên đồ thị
bài 4 là đề thi olp
dùng quy hoạch động
bài 3 không có giới hạn của N
bài 1 chắc không khó

[kid_191]

bạn có thể giải cụ thể hơn ko ^^ mới vào nên chưa bik gì

[kidteam]

ví dụ bài 2 nha
lâu rồi mình cũng không làm mấy bài kiểu này
quên rồi (từ hồi ôn thi olp cũng có làm)
thông cảm nha
dạo này bận làm việc khác rồi (công việc "mệt" lắm :-) )

#include <stdio.h>
#include <CONIO.H>
#include <STRING.h>
// Ngô Hùng Cường
// kidteam@gmail.com
// 0989696971
// congdongcviet
int n,k;
char nhiem[252];
char a[252][252];
int kq;

void nhap(void);
void xuly(void);
void xuat(void);

int main(void)
{
	nhap();
	xuly();
	xuat();
	return 0;
}
void nhap(void)
{
	FILE *f;
	f=fopen("sars.inp","rt");
	int i,j;
	fscanf(f,"%d%d",&n,&k);
	memset(a,0,sizeof(a));
	for(i=1;i<=n;++i)
	{
		int tg,t;
		fscanf(f,"%d",&tg);
		for(j=1;j<=tg;++j)
		{
			fscanf(f,"%d",&t);
			a[i][t]=a[t][i]=1;
		}
	}
	fclose(f);
	kq=1;
	memset(nhiem,0,sizeof(nhiem));
	nhiem[k]=1;
}
void xuly(void)
{
	char st[252];
	int m;
	m=1;
	st[1]=k;
	int tg,i;
	while(1)
	{
		if(!m)
			break;
		tg=st[m];
		--m;
		for(i=1;i<=n;++i)
		{
			if(a[tg][i]&&(!nhiem[i]))
			{
				++m;
				st[m]=i;
				nhiem[i]=1;
				++kq;
			}
		}
	}
}
void xuat(void)
{
	FILE *f;
	f=fopen("sars.out","wt");
	int i;
	int d;
	d=0;
	fprintf(f,"%d\n",kq);
	for(i=1;i<=n;++i)
		if(nhiem[i])
		{
			++d;
			if(d==kq)
				fprintf(f,"%d",i);
			else
				fprintf(f,"%d ",i);
		}
	fclose(f);
}

[hunterphu]

Bài 3 mình nghĩ N tầm 5000 trở xuống để có thể cài n^2*d
Bài tập tương tự với n=10^5 và |a[i]|<=10^9 time 5s

[tancntt]

#include<conio.h>
#include<stdio.h>
#define max 100
int m,n,a[max][max];
FILE *fin,*fout;
int main()
{
int i,j,b[max],s=0;
fin=fopen("MATRAN.INP","r");
fscanf(fin,"%d%d",&m,&n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
fscanf(fin,"%d",&a[i][j]);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
s+=a[i][j];
}
b[i]=s;
s=0;
}
fout=fopen("MATRAN.OUT","w");
fprintf(fout,"%d\n",m);
for(i=0;i<m;i++)
fprintf(fout,"%3d",b[i]);


}

các pro cho ý kiến nhé. chưa test dc nhiều.