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:
157
Hôm qua:
714
Tuần này:
2409
Tháng này:
6416
Tất cả:
1844610

Đề thi chọn học sinh giỏi lớp 11 năm 2012 - 2013

                SỞ GIÁO DỤC & ĐÀO TẠO THANH HÓA

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

===========

 

KÌ THI CHỌN HSG LỚP 11

Năm học: 2012 - 2013

Môn thi: Tin học

Ngày thi: 13/04/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:

Tên bài

File chương trình

File dữ liệu vào

File kết quả

Thời gian chạy

Chia đồ chơi

TOY.PAS

TOY.INP

TOY.OUT

1 giây/test

Xâu đẹp

STR.PAS

STR.INP

STR.OUT

1 giây/test

Hoán vị

PER.PAS

PER.INP

PER.OUT

2 giây/test

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: Chia đồ chơi (6 điểm)

Nhà trẻ vừa nhận được một số lượng lớn các đồ chơi với M màu khác nhau. Các cô trông trẻ sẽ chia các đồ chơi này cho N em bé. Có các nguyên tắc khi chia đồ chơi như sau:

·        Mỗi em bé sẽ chỉ nhận những đồ chơi giống màu nhau.

·        Tất cả các đồ chơi đều phải được sử dụng.

·        Lượng đồ chơi của em bé có nhiều đồ chơi nhất phải nhỏ nhất có thể.

Ví dụ trong trường hợp có 5 em bé, 4 đồ chơi màu đỏ và 7 đồ chơi màu xanh, một cách chia hợp lý sẽ như sau: 2 đỏ, 2 đỏ, 2 xanh, 2 xanh, 3 xanh.

Yêu cầu: Bạn không cần đưa ra cách chia cụ thể mà chỉ cần đưa ra số đồ chơi của em bé có nhiều đồ chơi nhất.

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

- Dòng 1: Gồm hai số nguyên dương N, M (1<= N<= 109, 1<=M <= 3.105) lần lượt là số em bé và số màu đồ chơi.

- M dòng tiếp theo: Dòng i ghi một số nguyên dương ai (1<= ai<= 109) là số đồ chơi có màu i.

Dữ liệu ra: Ghi ra file TOY.OUT là số đồ chơi của em bé có nhiều đồ chơi nhất trong cách chia tối ưu. Chú ý: dữ liệu của bài toán luôn có đáp án.

TOY.INP

TOY.OUT

5  2

4

7

3

Bài 2: Xâu đẹp (7 điểm)

Ta định nghĩa một xâu kí tự X có độ dài K được gọi là xâu đẹp nếu như nó thõa mãn các điều kiện sau:

-         K chẵn (xâu X có độ dài chẵn).

-         X[1] = X[K].

-         X[2] ≠ X[K-1]

-         ...........

(Tổng quát:  thì nếu i lẻ X[i]=X[k-i+1], nếu i chẵn X[i] ≠ X[k-i+1]).

Yêu cầu: Cho một xâu độ dài N chỉ gồm các kí tự là chữ cái latin thường. Hãy tìm xâu con (không cần liên tiếp) dài nhất của xâu đã cho sao cho nó là một xâu đẹp.

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

- Dòng 1: Số nguyên dương N <=1000 độ dài của xâu đã cho.

- Dòng 2: Chứa một xâu gồm N kí tự chỉ gồm các chữ cái latin in thường.

Dữ liệu ra: Ghi vào file STR.OUT một số duy nhất là độ dài của xâu tìm được.

Ví dụ:

                            

STR.INP

STR.OUT

7

windows

4

Bài 3. Hoán vị (7 điểm)

Ta định nghĩa 1 dãy hoán vị n như sau:

Một dãy p1, p2, p3, ..., pn là 1 dãy hoán vị n nếu như các phần tử đôi một khác nhau và có giá trị từ 1 đến n.

Ví dụ: dãy 1 3 5 2 4 là 1 dãy hoán vị 5.

           dãy 1 2 2 3 4 và dãy 1 3 4 5 6 không phải là 1 dãy hoán vị 5.

Với 2 dãy hoán vị n: A1, A2, ... An và B1, B2, ... Bn bất kì. Dãy C được tính theo công thức: Ci=((Ai+ Bi- 2) mod n) + 1;

Yêu cầu 1: Ðếm số lượng 2 dãy hoán vị n: A và B sao cho dãy C được tạo thành từ dãy A và B theo công thức trên thỏa mãn điều kiện C1= 1, C2= 2, C3= 3, ... , Cn= n (hay Ci=i)

Yêu cầu 2: Ðếm số lượng 2 dãy hoán vị n: A và B sao cho dãy C được tạo thành từ dãy A và B theo công thức trên cũng là 1 dãy hoán vị n

Dữ liệu vào: File văn bản PER.INP gồm 2 dòng:

- Dòng 1: Số nguyên dương n (n<=16).

- Dòng 2: Chứa số nguyên m có giá trị 0 hoặc 1.

Dữ liệu ra: Ghi ra file PER.OUT gồm:

Dòng 1: In ra kết quả với yêu cầu 1.

Dòng 2: Nếu m=0 thì bạn không phải xử lí yêu cầu 2 và in ra 0. Nếu m=1 in ra kết quả với yêu cầu 2. Kết quả lấy dư theo modul 1000000007

Ví dụ

PER.INP

PER.OUT

3

1

3

18

 

 

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

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

Tham khảo code: code.rar

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