Đề học sinh giỏi Nam Định 2008 - 2009

[luongha83p2]

<div style="text-align: center">Đề thi học sinh giỏi tỉnh Nam Định năm học 2008 – 2009​

</div> Bài 1: (6 điểm) Nhân 2 phân số
Cho hai phân số
Hãy xác định 2 số nguyên dương E và F thoả mãn 2 điều kiện sau:
+ Điều kiện 1:
+ Điều kiện 2: là phân số tối giản.
Dữ liệu vào: từ tệp văn bản NHAN.INP, có cấu trúc
+ Dòng 1 chứa 2 số A và B
+ Dòng 2 chứa 2 số C và D

<div style="text-align: center">( A, B, C, D là các số nguyên dương và không lớn hơn 10000 )​

</div> Dữ liệu ra: kết qurb đưa ra tệp văn bản NHAN.OUT
Có một dòng chứa hai số E và F tìm được thoả mãn hai điều kiện trên.
( Trong tệp dữ liệu vào hoặc ra các số trên cùng một dòng cách nhau ít nhất một dấu cách)
Ví dụ về dữ liệu vào/ra:

<div style="text-align: center">NHAN.INP​

</div>

<div style="text-align: center">NHAN.OUT​

</div> 2 5
3 6
1 5

Bài 2: (7 điểm) Tìm dãy con chung
Dãy C gọi là dãy con chung của dãy A và dãy B nếu C là dãy gồm các phần tử nằm liên tiếp cả trong A và B.
Cho hai dãy số A và B, mỗi dãy đều có N phần tử (các phần tử đều nguyên dương và không quá 1000). Yêu cầu tìm dãy C là dãy con chung của A và B mà có nhiều phần tử nhất.
Dữ liệu vào: từ tệp văn bản DAYCON.INP có cấu trúc:
- Dòng 1 chứa số N (N nguyên dương và không quá 500)
- Dòng 2: chứa N số thuộc dãy số A.
- Dòng 3: chứa N số thuộc dãy số B.
Dữ liệu ra: đưa ra tệp văn bản DAYCON.OUT
Chứa duy nhất một số là số phẩn tử của dãy C thoả mãn yêu cầu.
( Trong tệp dữ liệu vào hoạc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách).
Ví dụ về dữ liệu vào/ra:

<div style="text-align: center">DAYCON.INP​

</div>

<div style="text-align: center">DAYCON.OUT​

</div> 6
2 1 7 10 6 3
8 5 1 7 9 10
2

Bài 3[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]7 điểm) Công ty kinh doanh xăng dầu
Công ty kinh doanh xăng dầu BX hiện có N lít xăng. Công ty nhân được M yêu cầu mua xăng của khách hàng (khách hàng được đánh số từ 1 đến M, mỗi yêu cầu cần mua một lượng xăng nhất định. Nếu công ty BX không đáp ứng đủ lượng xăng cần thiết thì sẽ bị mất lòng khách hàng. Vì lượng xăng có thể không đủ cho tất cả các yêu cầu của khách hang nên phải từ chối một số khách hàng nào đó.
Công ty BX nhờ em tìm cách bán xăng cho các khách hàng chỉ làm mất lòng khách hàng ít nhất.
Dữ liệu vào: từ tệp văn bản BX.INP có cấu trúc
- Dòng 1 chứa 2 số N và M.( N và M nguyên dương, N<1 000 000, M<2000)
- Dòng 2 chứa M số nguyên dương, số thứ I trong M số là số lít xăng mà khách hàng thứ I yêu cầu mua (mỗi yêu cầu của khách đều nguyên dương và không quá 10 000 lít).
Dữ liệu ra: kết quả đưa ra tệp văn bản BX.OUT, theo cấu trúc
- Dòng 1: chứa số S là số lượng các khách hàng mất lòng ít nhất.
- Nếu S> 0 thì dòng 2 chứa số S theo thứ tự tăng, số thứ j trong S số thể hiện khách hàng j mất lòng. Nếu có nhiều trường hợp thoả mãn S thì chỉ cần đưa ra một trường hợp.
( Trong tệp dữ liệu vào hoặc ra, các số trên cùng một dòng cách nhau ít nhất một dấu cách).
Ví dụ về dữ liệu vào/ra:

<div style="text-align: center">BX.INP​

</div>

<div style="text-align: center">BX.OUT​

</div> 100 5
50 20 60 40 30
2
3 4

Chú ý: tệp chương trình của bài 1 đặt tên là CHIA.PAS.
của bài 2 đặt tên là DAYCON.PAS
của bài 3 đặt tên là BX.PAS

[sevenup024]

Bài 1 tối giản 2 tử và mẫu của phân số này với mẫu và tử của phân số kia rồi nhân với nhau, kq tiếp tục tối giản tiếp để thu được out.
bài 2 vì giới hạn nhỏ nên vét cạn là tốt rồi, O(N^2)
Bài 3: thuật toán tham lam: sx mảng lượng xăng tăng dần, sau đó lấy dần từ đầu mảng tới khi hết lượng xăng hiện có, những phần tử không được lấy là những khách hàng làm mất lòng. Thuật toán O(N log N).

[Sông Hồng]

Bạn có thể viết code cho từng bài được không?thank

[hlong001]

code bài 1 đây bạn

Var f1,f2:text;
A,B,C,D,m,n:integer;
Function UCLN(x,y:integer):integer;
Var r:integer;
Begin
   while y <>0 do
  Begin
       r:=x mod y;
       x:=y;
       y:=r;
  End;
UCLN:=x;
End;

Begin
assign(f1,'Vao.inp');
Reset(f1);
assign(f2,'Ra.out');
Rewrite(f2);
readln(f1,A,B);
readln(f1,C,D);
A:=A div UCLN(A,B);
B:=B div UCLN(A,B);
C:=C div UCLN(C,D);
D:=D div UCLN(C,D);
m:=A*C;
n:=b*D;
m:=m div UCLN(m,n);
n:=n div UCLN(m,n);
write(f2, m,' ', n);
close(f1);
close(f2);
End.