Thầy Nguyễn Văn Nhiệm
Sinh nhật: 14-02
Cô Lê Thị Thanh
Sinh nhật: 05-02
Thầy Đỗ Xuân Phong
Sinh nhật: 09-02
Thầy Nguyễn Văn Dũng
Sinh nhật: 10-02
Cô Vũ Thị Thu Hiền
Sinh nhật: 06-02
Cô Nguyễn Thị Thu Hiền
Sinh nhật: 09-02
Thầy Nguyễn Thị Thu Huyền
Sinh nhật: 27-01
Thầy Nguyễn Văn Nhiệm
Sinh nhật: 14-02
Cô Lê Thị Thanh
Sinh nhật: 05-02
Thầy Đỗ Xuân Phong
Sinh nhật: 09-02
Thầy Nguyễn Văn Dũng
Sinh nhật: 10-02
Cô Vũ Thị Thu Hiền
Sinh nhật: 06-02
Cô Nguyễn Thị Thu Hiền
Sinh nhật: 09-02
Thầy Nguyễn Thị Thu Huyền
Sinh nhật: 27-01
Thầy Nguyễn Văn Nhiệm
Sinh nhật: 14-02
Thầy Đỗ Xuân Phong
Sinh nhật: 09-02
Thầy Nguyễn Văn Dũng
Sinh nhật: 10-02
Cô Vũ Thị Thu Hiền
Sinh nhật: 06-02
Cô Nguyễn Thị Thu Hiền
Sinh nhật: 09-02
Thầy Nguyễn Văn Dũng
Sinh nhật: 10-02
Cô Nguyễn Thị Thu Hiền
Sinh nhật: 09-02
Cô Vũ Thị Thu Hiền
Sinh nhật: 06-02
Thầy Nguyễn Văn Nhiệm
Sinh nhật: 14-02
Thầy Đỗ Xuân Phong
Sinh nhật: 09-02

Truy cập

Hôm nay:
135
Hôm qua:
714
Tuần này:
2387
Tháng này:
6394
Tất cả:
1844588

Đề thi chọn đội tuyển cấp trường năm học 2013 - 2014

SỞ GD & ĐT THANH HÓA

Trường THPT chuyên Lam Sơn

====&====

KÌ THI CHỌN ĐỘI TUYỂN HSG CẤP TRƯỜNG

Môn thi: Tin học

Ngày thi: 18/09/2013

 

Thời gian làm bài : 180 phút (không kể thời gian phát đề)

Đề thi gồm: 02 trang

Tổng quan bài thi:

Bài

Tên bài

File chương trình

File dữ liệu vào

File kết quả

1

Nông trại

FARM.PAS

FARM.INP

FARM.OUT

2

Biến đổi dãy số

CSEQ.PAS

CSEQ.INP

CSEQ.OUT

3

Đồ thị thông suốt

DAG.PAS

DAG.INP

DAG.OUT

Lưu ý: - Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên.

              - Các file dữ liệu trong bài nếu có nhiều giá trị trên một dòng thì các giá trị đó luôn cách nhau bằng 1 khoảng trắng.

Hãy lập trình giải các bài toán sau:

Bài 1: Nông trại (7 điểm)

Trên cách đồng XYZ có n nông trại khác nhau. Nông trại thứ i có ai con bò (không có 2 nông trại nào có số lượng con bò bằng nhau). Nông dân John muốn đến thăm tất cả n nông trại, để tặng các bó cỏ cho các nông trại với quy tắc sau:

-         Nông trại mà Ông đến thăm đầu tiên sẽ được tặng số bó cỏ bằng số lượng con bò có trong nông trại.

-         Ông đi từ nông trại i (có ai con bò) đến nông trại j (có aj con bò) thì nông trại j sẽ được tặng số bó cỏ là |aj-ai|.

n! cách đi khác nhau để đến thăm n nông trại vì Ông ta có thể đến thăm các nông trại theo thứ tự mà mình muốn, miễn là Ông ta đến tất cả các nông trại và mỗi nông trại chỉ đến 1 lần. Với mỗi cách đi như vậy thì Ông ta dễ dàng tính được tổng số bó cỏ đã tặng.  

Yêu cầu: Tính trung bình cộng tổng các bó cỏ của tất cả các cách mà Ông ta đã tặng.

Dữ liệu vào: File văn bản FARM.INP gồm:

- Dòng 1: Số nguyên n (2<= n<= 105) 

- Dòng 2: n số nguyên khác nhau a1, a2,…, an lần lượt là số con bò của các nông trại (1<= ai<= 107).

Dữ liệu ra: Ghi ra file FARM.OUT gồm tử số và mẫu số của phân số tối giản là kết quả của bài toán

FARM.INP

FARM.OUT

3
2  3  5
22  3

Giải thích: Có 3 nông trại: nông trại 1 có 2 con bò, nông trại 2 có 3 con bò, nông trại 3 có 5 con bò. Có 6 cách để đến thăm 3 nông trại:

·         [2, 3, 5]: tổng các bó cỏ nông dân John tặng: 2 + |3 - 2| + |5 - 3| = 5;

  • [2, 5, 3]: 2 + |5 - 2| + |3 - 5| = 7;
  • [3, 2, 5]: 3 + |2 - 3| + |5 - 2| = 7;
  • [3, 5, 2]: 3 + |5 - 3| + |2 - 5| = 8;
  • [5, 2, 3]: 5 + |2 - 5| + |3 - 2| = 9;
  • [5, 3, 2]: 5 + |3 - 5| + |2 - 3| = 8.

Trung bình cộng tổng các bó cỏ của tất cả các cách:  = =  

Bài 2: Biến đổi dãy số (7 điểm)

            Xét dãy số nguyên a1, a2,.., an và các phép biến đổi có dạng C(i,j) trên dãy số với ý nghĩa: đổi dấu tất cả các phần tử từ vị trí thứ i đến vị trí thứ j (1<= i<= j<= n).

            Ví dụ, với dãy 1, 2, -3, 4, 5, -6 nếu biến đổi C(2,4) ta nhận được dãy 1, -2, 3, -4, 5, -6.

            Dễ thấy, có tất cả (n.(n+1))/2 phép biến đổi trên dãy gồm n phần tử. Một phép biến đổi được gọi là tối ưu nếu sau khi thực hiện phép biến đổi ta nhận được dãy có tổng các phần tử là lớn nhất trong tất cả các phép biến đổi.

Yêu cầu: Cho dãy số nguyên a1, a2,.., an, hãy tìm phép biến đổi tối ưu  

Dữ liệu vào: Vào từ file văn bản CSEQ.INP gồm:

-         Dòng đầu chứa số nguyên dương n (n<= 3.105);

-         Dòng thứ hai chứa n số nguyên a1, a2,.., an (|ai|<= 109).

Dữ liệu ra: Ghi ra file văn bản CSEQ.OUT gồm một số nguyên duy nhất là tổng các phần tử của dãy sau khi thực hiện phép biến đổi tối ưu.

Ví dụ:

CSEQ.INP

CSEQ.OUT

6

1  2  -3  4  5  -6

15

 

Bài 3. Đồ thị thông suốt (6 điểm)

            Cho đồ th vô hướng N đỉnh khác nhau và M cnh. Một đồ thị được gọi là thông suốt nếu như từ 1 đỉnh ta có thể đi đến tất cả các đỉnh khác theo các cạnh của đồ thị.

Yêu cầu: Đếm số lượng cạnh ít nhất cần thêm vào để đồ thị đã cho là đồ thị thông suốt.

Dữ liệu vào: File văn bản DAG.INP gồm:

- Ḍòng 1: chứa 2 số nguyên dương N, M tương ứng là số đỉnh và số cạnh của đồ thị (N,M<=105).

- Ḍòng 2 đến dòng M+1: Mỗi ḍòng gồm 2 số nguyên dương u v, là 1 cạnh của đồ thị (1<=u,v<=N);

Dữ liệu ra: Ghi ra file DAG.OUT gồm: 1 số duy nhất là số lượng cạnh ít nhất cần thêm vào, nếu không cần phải thêm thì in ra -1

Ví dụ

DAG.INP

DAG.OUT

6 5

1 2

2 3

1 3

4 5

5 6

1

 

 

Họ và tên: .............................................

Số báo danh: ..................

 

(Cán bộ coi thi không giải thích gì thêm)

----------------------------------------- HẾT -----------------------------------------

Tham khảo code: Tasks.rar 

Nguồn tin: Nguyễn Đặng  Phú