Tổng hợp tất cả các đề đề xuất Trại hè Hùng Vương môn Tin khối 11 năm 2018 có đáp án  (Bấm vào liên kết phía dưới để tải xuống)

Đây là Tổng hợp tất cả các đề đề xuất Trại hè Hùng Vương môn Tin khối 11 năm 2018 có đáp án. Tài liệu là tập hợp các đề của các đơn vị: Bắc Giang, Hà Giang, Hạ Long, Hòa Bình, Lào Cai, Thái Nguyên, Tuyên Quang, Vĩnh Phúc, Yên Bái. Mời các bạn tải về để tham khảo.

SỞ GD&ĐT LÀO CAI

TRƯỜNG THPT CHUYÊN

ĐỀ THI ĐỀ XUẤT

---------------------

ĐỀ THI CHỌN HỌC SINH GIỎI

TRẠI HÈ HÙNG VƯƠNG LẦN THỨ XIV

NĂM HỌC 2017 - 2018

Môn: TIN HỌC 11

(Thời gian làm bài: 180 phút)

-----------------------------------------------------------------

 TỔNG QUAN BÀI THI

Bài

Tên bài

Tên chương trình

Dữ liệu vào

Dữ liệu ra

Điểm

1

Chặt cây

OPTCUT.*

OPTCUT.INP

OPTCUT.OUT

6

2

Xâu đối xứng dài nhất

PALINY.*

PALINY.INP

PALINY.OUT

7

3

Cây xương rồng

CACTUS.*

CACTUS.INP

CACTUS.OUT

7

Bài 1: Chặt cây

Gia đình nhà Mike mở một xưởng sản xuất than sạch không khói để xuất khẩu ra ngước ngoài (Nhật Bản, Hàn Quốc, Úc...). Mỗi ngày đều phải chặt nhỏ rất rất nhiều thanh gỗ để nghiền, đưa vào máy ép,... tạo ra than sạch. Qua quan sát, Mike thấy rằng muốn chặt một thanh gỗ ra thành n đoạn (mỗi đoạn có độ dài ai, các đoạn phải được chặt theo đúng thứ tự a1, a2, ..., an từ trái sang phải), có thể chặt một nhát chia một thanh gỗ làm hai và chi phí cho nhát chặt này bằng độ dài của thanh gỗ trước khi chặt. Thứ tự chặt khác nhau sẽ cho ra tổng chi phí khác nhau khi chặt thanh gỗ thành n đoạn. Bạn hãy giúp Mike tìm cách chặt để có tổng chi phí nhỏ nhất.

Ví dụ cần chặt thanh gỗ độ dài 20 ra thành 4 đoạn độ dài: 3, 5, 2 và 10 theo thứ tự. 

Khi chặt từ trái sang phải: 20 chặt thành 3 và 17, chi phí 20. 17 chặt thành 5 và 12, chi phí 17. 12 chặt thành 2 và 10, chi phí 12. Tổng chi phí: 49

Khi chặt từ phải sang trái: 20 chặt thành 10 và 10, chi phí 20. 10 chặt thành 8 và 2, chi phí 10. 8 chặt thành 3 và 5, chi phí 8. Tổng chi phí: 38

Đầu vào: Dòng 1: n (1 ≤ n ≤ 2000); Dòng 2: n số nguyên dương a1, a2, ..., an, biết rằng độ dài của thanh gỗ a1+a2+...+an ≤ 500000

Kết quả: Một số nguyên duy nhất là chi phí nhỏ nhất tìm được.

Ràng buộc:

30% số test có;

30% số test tiếp theo có;

40% test còn lại có.

Bài 2: Xâu đối xứng dài nhất

Thời gian này, Mike đang nghiên cứu kĩ thuật về xử lý xâu kí tự, trong đó Mike rất thích thú với các kĩ thuật về so khớp chuỗi.

Có một bài toán khiến Mike thích thú đó là tìm xâu con đối xứng dài nhất gồm các kí tự liên tiếp của xâu ban đầu gồm n kí tự.

Đầu vào: Dòng 1: n (số ký tự của xâu S; ); Dòng 2: Xâu ký tự độ dài n

Đầu ra: Một số duy nhất là độ dài của xâu con đỗi xứng dài nhất.

Ràng buộc:

30% số test có;

30% số test có;

40% số test

 

Bài 3. Cây xương rồng:

Bạn được cho một đồ thị vô hướng liên thông, ở đó mỗi cạnh chỉ thuộc tối đa một chu trình. Nhiệm vụ của bạn là xóa bỏ nhiều cạnh nhất có thể để tao ra cây (đồ thị liên thông, không có chu trình). Khi đó, ta luôn cần thực hiện cách xóa bỏ cạnh để khoảng cách giữa mỗi cặp đỉnh trên cây là nhỏ nhất, khoảng cách được hiểu là số cạnh nối giữa 2 đỉnh.

Đầu vào: Dòng đầu tiên ghi 2 số n, m là số đỉnh, số cạnh của đồ thị ban đầu, với ; m dòng tiếp theo là các cặp u, v thể hiện có cạnh giữa 2 đỉnh u, v, với .

Đầu ra: n số là các khoảng cách xa nhất từ một đỉnh đến các đỉnh còn lại, mỗi số cách nhau một kí tự trắng. Số thứ i là khoảng cách xa nhất từ nút i đến nút lá xa nhất.

Ràng buộc:

30% số test có;

30% số test có;

40% số test có còn lại

 

 

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 11
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap