Đề thi tuyển sinh lớp 10 chuyên Tin, trường Phổ Thông Năng Khiếu, năm học 2006 - 2007

Mời các bạn tham khảo (đề thi đã được biên tập, chỉnh sửa lại)
Link chấm bài: http://coder.chuyenluongthevinh.edu.vn/Contest/Enter/41
---

ĐẠI HỌC QUỐC GIA TP HCM TRƯỜNG PHỔ THÔNG NĂNG KHIẾU ĐỀ ĐÃ ĐƯỢC CHỈNH SỬA LẠI!!! -------------------------

ĐỀ THI TUYẾN SINH LỚP 10 Năm học 2006 - 2007 Môn thi: TIN HỌC Thời gian: 150 phút, không kể thời gian phát đề ------------------

TỔNG QUAN ĐỀ THI

Tên bài	File CT	File Input	File Output
Đoạn con dài nhất	SUBSTR.???	SUBSTR.INP	SUBSTR.OUT
Đường đi	PATH.???	PATH.INP	PATH.OUT
Đếm vùng	REGIONS.???	REGIONS.INP	REGIONS.OUT
Số ước	DIVISORS.???	DIVISORS.INP	DIVISORS.OUT

Chú ý:

• Dấu ??? được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài đặt chương trình
• Trong các file dữ liệu vào và ra, các số trên cùng dòng cách nhau bằng khoảng trắng.
• Thí sinh chỉ nộp các file mã nguồn của chương trình.

        Bài 1.          SUBSTR Đoạn con dài nhất

            Cho chuỗi kí tự S gồm toàn các chữ cái in hoa (A…Z) với độ dài không vượt quá 255. Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đầu tiên trong chuỗi S.

Input	Output
ABABCDAC	3 4

Input: gồm một dòng duy nhất chứa chuỗi S.

Output: hai số nguyên P và L tương ứng là vị trí và chiều dài của đoạn con dài nhất tìm được (kí tự đầu tiên trong chuỗi có vị trí là 1).

        Bài 1.          PATH Đường đi

            Một con robot di chuyển theo một chương trình định sẵn trên mặt phẳng toạ độ. Chương trình này được thể hiện dưới dạng một dãy N lệnh (1N3000). Các lệnh thuộc một trong các dạng sau:

·        F S: Đi thẳng theo hướng hiện tại S bước.

·        R S: Rẽ phải 90⁰ và đi S bước.

·        L S: Rẽ trái 90⁰ và đi S bước.

Input	Output
4 1 F 5 R 7 F 2 L 9	23

            Yêu cầu: Cho một chương trình điều khiển robot, hãy xác định chiều dài T đoạn đường mà con robot đã đi được, biết mỗi bước của nó dài d(cm). Ban đầu con robot đứng tại vị trí (0,0) và hướng theo chiều dương của trục hoành.

Input

·        Dòng đầu tiên chứa 2 số nguyên dương N và d.

·        N dòng tiếp theo, mỗi dòng chứa một lệnh theo quy cách nêu trên.

Output chứa chiều dài T tìm được.

        Bài 1.          REGIONS Đếm vùng

            Một khu vườn hình chữ nhật được chia thành  ô đơn vị. Các dòng đánh số từ 1 tới M từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái sang phải. Ô nằm ở hàng i, cột j được gọi là ô (i, j). Người ta có đắp K lối đi trên mảnh vườn đó, lối đi thứ i là một dãy các ô liên tiếp nhau theo đường ngang hoặc đường dọc, và được cho bởi 4 số nguyên dương x_i, y_i, z_i và t_i trong đó (x_­i­, y_i) là vị trí của ô đầu, còn (z_i­, t_i) là vị trí của ô cuối của lối đi. Các lối đi chia khu vườn thành các miền. Mỗi miền là một tập tất cả các ô không thuộc các lối đi sao cho hai ô bất kì trong đó có thể đi tới bằng cách di chuyển qua các ô chung cạnh và không phải là ô thuộc lối đi.

Input	Output
10 10 2 5 1 5 10 1 5 7 5	3

            Yêu cầu: Hãy xác định số miền S mà các lối đi chia khu vườn.

Input

·        Dòng đầu chứa 3 số M, N, K.

·        Dòng thứ i trong K dòng tiếp theo chứa 4 số xác định lối đi thứ i: x_i, y_i, z_i, t_i.

Output: số S tìm được.

        Bài 2.          DIVISORS Số ước

            Cho số nguyên dương N. Giai thừa của N, kí hiệu là N!, là tích của các số tự nhiên từ 1 đến N. Gọi T là số lượng ước lớn hơn 1 của N!. Ví dụ với N = 4, ta có 4! = 24. Như vậy 4! có 7 ước lớn hơn 1 là: 2, 3, 4, 6, 8, 12, 24.

Input	Output
4	7

            Yêu cầu: Cho N, hãy xác định T.

Input ghi duy nhất số N (N20).

Output số T tìm được.

Giới hạn: trong đó 50% số test có N10