Đề kì thi hsg các trường THPT chuyên khu vực duyên hải và đồng bằng bắc bộ môn Tin học - khối 11 - năm 2016 - Đề đề xuất của trường chuyên Bắc Ninh  (Bấm vào liên kết phía dưới để tải xuống)

Đề kì thi hsg các trường THPT chuyên khu vực duyên hải và đồng bằng bắc bộ môn Tin học - khối 11 - năm 2016 - Đề đề xuất của trường chuyên Bắc Ninh. Đề gồm các bài sau: lối đi bộ cho khách du lịch, sâu con, lăn xúc xắc.

Đề kì thi hsg các trường THPT
chuyên khu vực duyên hải và đồng bằng bắc bộ môn Tin học
khối 11 - năm 2016 - Đề đề xuất của trường chuyên Bắc Ninh

LỐI ĐI BỘ CHO KHÁCH DU LỊCH (OAKTREE)
Chính phủ có kế hoạch xây dựng một lối đi bộ dành cho khách du lịch ở giữa một khu rừng sồi. Khu rừng có thể được mô tả như là mặt phẳng có N điểm đặc biệt mô tả các các cây sồi. Lối đi cho khách du lịch là một đường vòng có dạng hình chữ nhật có các cạnh song song với các trục tọa độ. Nếu như cạnh của hình chữ nhật này đi qua cây sồi nào thì cây sồi đó phải được đốn bỏ. Các cây sồi không nằm trên các cạnh của hình chữ nhật thì không cần phải đốn hạ. Một dạnh sách P lối đi bộ cho khách du lịch được đệ trình lên chính phủ. Ljuko, một quan chức cao cấp của Bộ Lâm nghiệp - người rất yêu cây cối quan tâm đến việc với kế hoạch xây dựng được đệ trình thì có bao nhiêu cây sồi bị đốn hạ trong quá trình xây dựng các lối đi bộ.
Viết chương trình xác định với mỗi lối đi bộ được xây dựng thì có bao nhiêu cây sồi bị đốn hạ.
Input: File OAKTREE.INP
- Dòng đầu tiên ghi số N là số lượng cây sồi (N≤300000)
- N dòng tiếp theo, dòng thứ i ghi hai số nguyên X , Y là tọa độ của một cây sồi 
- Dòng kế tiếp ghi P là số lối đi bộ trên kế hoạch (P≤100000)
- P dòng tiếp theo, mỗi dòng ghi 4 số nguyên X1, Y1, X2, Y2 với ý nghĩa (X1,Y1) là tọa độ của góc trái dưới và (X2, Y2) là tọa độ của góc phải trên của 1 lối đi bộ lần lượt được xây dựng (1≤X1≤X2≤10 , 1≤Y1≤Y2≤10 )
Output: File OAKTREE.OUT
Gồm P dòng, dòng thứ i ghi số lượng cây sồi bị đốn hạ khi xây dựng lối đi bộ thứ i (theo trình tự trong file input)

XÂU CON (SUBSTRG)
Cho xâu S độ dài n. Hãy tìm xâu con dài nhất của S, sao cho mỗi ký tự tham gia vào xâu con không quá k lần (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n). Yêu cầu: Chỉ ra độ dài của xâu con tìm được và vị trí của ký tự đầu tiên thuộc xâu con trong xâu S ban đầu. Nếu có nhiều cách chọn xâu con – chỉ cần nêu một trong
các cách.
Input: File SUBSTRG.INP:
- Dòng đầu tiên chứa 2 số nguyên n và k,
- Dòng thứ hai chứa xâu S.
Output: File SUBSTRG.OUT
Một dòng hai số nguyên: độ dài xâu con và vị trí ký tự đầu tiên của xâu con.

LĂN XÚC XẮC
Cho một lưới ô vuông đơn vị kích thước mxn, trên mỗi ô ghi một số tự nhiên  6. Có một con xúc xắc (hình lập phương cạnh 1 đơn vị) nằm tại một ô (x, y) mang số 6. Các mặt con xúc xắc được ghi các số nguyên dương từ 1 đến 6: mặt trên mang số 1, mặt bên hướng về mép trên của lưới mang số 2, mặt bên hướng về mép trái của lưới mang số 3, tổng hai số ghi trên hai mặt đối
diện bất kỳ luôn bằng 7. (Xem hình vẽ)

Cho phép lăn con xúc xắc sang một trong 4 ô kề cạnh. Sau mỗi phép lăn như vậy, mặt trên của xúc xắc sẽ trở thành mặt bên tương ứng với hướng di chuyển và mặt bên theo hướng di chuyển sẽ trở thành mặt đáy. Một phép lăn được gọi là hợp lệ nếu nó luôn đảm bảo số ghi ở ô xúc xắc đang đứng và số ghi ở mặt đáy của xúc xắc bằng nhau. Như ví dụ trên, ta có thể lăn lên trên, sang phải hay sang trái nhưng không thể lăn xuống dưới.

Yêu cầu:
Hãy chỉ ra một số hữu hạn các phép lăn hợp lệ để lăn con xúc xắc ra một ô biên của lưới, nếu có nhiều phương án thực hiện thì chỉ ra phương án mà tổng các số ghi ở mặt trên của xúc xắc sau mỗi bước di chuyển là cực tiểu.

Dữ liệu: Vào từ file văn bản ROLL.INP
- Dòng 1: Chứa 4 số m, n, x, y
- m dòng tiếp theo, dòng thứ i chứa n số mà số thứ j là số ghi tại ô (i, j) của lưới
Các số trên một dòng của Input File cách nhau ít nhất một dấu cách. Dữ liệu vào luôn đúng đắn để tồn tại giải pháp thực hiện

Kết quả: Ghi ra file văn bản ROLL.OUT
Gồm một dòng chứa dãy liên tiếp các ký tự, ký tự thứ k có thể là L, R, U hoặc D tương ứng với phép lăn tại bước thứ k là lăn sang trái, lăn sang phải, lăn lên trên hay lăn xuống dướ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