• Không có kết quả nào được tìm thấy

Đề thi HSG Tin vĩnh Phúc chuyên

N/A
N/A
Protected

Academic year: 2022

Chia sẻ "Đề thi HSG Tin vĩnh Phúc chuyên"

Copied!
1
0
0

Loading.... (view fulltext now)

Văn bản

(1)

SỞ GD&ĐT VĨNH PHÚC ---

ĐỀ CHÍNH THỨC

KỲ THI CHỌN HSG LỚP 12 THPT NĂM HỌC 2010-2011 ĐỀ THI MÔN: TIN HỌC

Dành cho học sinh trường THPT Chuyên

Thời gian làm bài: 180 phút, không kể thời gian giao đề.

(Đề thi có 02 trang, gồm 03 bài)

---

Tổng quan

Tên bài File bài làm File dữ liệu File kết quả Điểm Thời gian

Bảng đèn bul.pas bul.inp bul.out 40 1s/test

Đi xe buýt bus.pas bus.inp bus.out 40 1s/test

Thả bóng dro.pas dro.inp dro.out 20 1s/test

Lập chương trình giải các bài toán sau:

Bài 1. Bảng đèn

Bờm thiết kế cho em trai một món đồ chơi là một bảng đèn điện tử. Bảng đèn có dạng hình chữ nhật kích thước M × N, các hàng đánh số 1 … M từ trên xuống dưới, các cột đánh số 1 … N từ trái sang phải, trên mỗi ô có một bóng đèn và một công tắc. Thay đổi trạng thái công tắc ở ô (u, v) (1 ≤ u ≤ M, 1 ≤ v≤ N) có tác dụng thay đổi trạng thái bật/tắt của tất cả các ô (x, y) thỏa mãn điều kiện 1 ≤ x ≤ u, 1 ≤ y ≤ v.

Trò chơi dành cho em trai Bờm là từ một trạng thái của bảng đèn tìm cách bật sáng toàn bộ đèn trong bảng. Để có thể chỉ ra trước mục tiêu phấn đấu cho em trai mình, Bờm muốn nhờ bạn tính toán số lần thay đổi trạng thái công tắc ít nhất cần thực hiện.

Dữ liệu (bul.inp)

 Dòng 1: hai số nguyên M, N (1 ≤ M, N ≤ 100);

 Từ dòng 2 đến dòng (M+1): mỗi dòng ghi một xâu nhị phân độ dài N, kí tự thứ j trên dòng (i+1) là 0/1 tương ứng là trạng thái ban đầu tắt/bật của bóng đèn tại ô (i, j).

Kết quả (bul.out)

 Dòng 1: số nguyên là số lần thay đổi trạng thái công tắc ít nhất cần thực hiện.

Ví dụ

bul.inp bul.out

1 5

01001 3

Bài 2. Đi xe buýt

Càng ngày xe buýt càng chứng tỏ được vai trò thiết yếu trong giao thông. Bờm cũng như phần lớn các bạn của cậu chủ yếu di chuyển bằng xe buýt. Một câu hỏi nhỏ hay gặp với mọi người là đi từ địa điểm này đến địa điểm kia cần phải đi ít nhất bao nhiêu tuyến. Bờm muốn nhờ bạn lập một chương trình giải quyết yêu cầu này để tích hợp vào điện thoại di động.

Giả thiết hệ thống giao thông có N bến và M tuyến xe buýt hai chiều. Các bến được đánh số 1, 2, …, N, mỗi tuyến được mô tả bằng một dãy các bến xuất hiện tuần tự theo một chiều xe chạy.

Có Q yêu cầu về di chuyển giữa các bến xe buýt.

(2)

Dữ liệu (bus.inp)

 Dòng 1: ba số nguyên N, M, Q (1 ≤ N ≤ 200; 1 ≤ M ≤ 100; 1 ≤ Q ≤ 200);

 Từ dòng 2 đến dòng (1+M): mỗi dòng ghi một dãy số là số hiệu các bến có trong một tuyến, mỗi bến xuất hiện trong một tuyến không quá 1 lần;

 Từ dòng (2+M) đến dòng (1+M+Q): mỗi dòng ghi hai số nguyên A, B là một yêu cầu về di chuyển từ bến A đến bến B, dữ liệu đảm bảo có cách di chuyển đối với mọi yêu cầu.

Kết quả (bus.out)

 Gồm Q dòng: dòng i ghi một số nguyên là số tuyến ít nhất cần phải đi để di chuyển giữa hai bến A, B của yêu cầu thứ i.

Ví dụ

bus.inp bus.out

5 4 1 1 2 2 4 3 4 5 1 5 1 3

2

Chú ý: chương trình của bạn phải trả lời đúng mọi yêu cầu trong một test thì mới được điểm test đó.

Bài 3. Thả bóng

Những khi rảnh rỗi, Bờm thường chơi trò chơi thả bóng trên máy tính, trò chơi như sau:

 Có một cột hình trụ chứa bóng, ban đầu cột rỗng.

 Mỗi lượt Bờm được lấy một bóng để thả vào cột, bóng có màu là một trong 4 màu Đỏ, Trắng, Vàng, Xanh, bóng sẽ rơi và nằm trên bóng cao nhất đang có trong cột (hoặc nằm ở đáy cột nếu trước đó cột rỗng).

 Mỗi khi có L bóng liên tiếp cùng màu, L bóng này sẽ nổ, các bóng phía trên sẽ rơi xuống thế chỗ.

Bờm muốn bạn xác định giúp có bao nhiêu cách ra dãy N bóng để kết thúc trò chơi cột rỗng.

Hai dãy được coi là khác nhau nếu tồn tại chỉ số i để bóng thứ i trong hai dãy là khác màu.

Dữ liệu (dro.inp)

 Một dòng ghi hai số nguyên L, N (2≤ L ≤ 10, 1 ≤ N ≤ 1000).

Kết quả (dro.out)

 Một số nguyên là phần dư của số lượng dãy thỏa mãn yêu cầu đề bài khi chia cho 1000000007.

Ví dụ

dro.inp dro.out

2 4 28

---Hết---

Giám thị coi thi không giải thích gì thêm.

Tài liệu tham khảo

Tài liệu liên quan

Choïn Yes ñeå löu taäp tin, choïn No ñeå khoâng löu vaø choïn Cancel seõ trôû veà maøn hình laøm vieäc cuûa Excel. Baïn coù muoán löu nhöõng thay

Để công suất tiêu thụ trên mạch cực đại đì phải điều chỉnh tần số của dòng điện đến giá trị bằng:A. âm sắc Câu 15: Khi sóng âm truyền từ môi trường không

Trái Đất nằm ở vị trí thứ mấy trong các hành tinh, theo thứ tự xa dần Mặt Trời.. - Hệ Mặt Trời: gồm có Mặt Trời và tám hành tinh là sao Thủy, sao Kim, Trái Đất,

- MÆt trêi cïng c¸c hµnh tinh quay xung quanh nã gäi lµ hÖ mÆt trêi.. HÖ - MÆt trêi cïng c¸c hµnh tinh quay xung quanh nã gäi lµ hÖ

Hình thái : Màu sắc lông da đen tuyền hoặc đen có đốm trắng ở đầu, đuôi và chân.. Lông thưa

Bài 1.. MỘT SỐ BÀI THI ĐẠI HỌC VÊ PHƯƠNG TRÌNH LƯỢNG GIÁC Bài 1.. Lấy 3 miếng bìa này đặt lần lượt cạnh nhau từ trái sang phải để được các số gồm 3 chữ số. Từ 8 chữ số

XXI Câu 5: Trong các số đo dưới đây, số đo thích hợp chỉ khối lượng một con bò

[r]