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

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 2008 - 2009 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
Mã hóa	ENCODE.???	ENCODE.INP	ENCODE.OUT
Biến đổi dãy số	EXARRAY.???	EXARRAY.INP	EXARRAY.OUT
Biến đổi bảng	NZTABLE.???	NZTABLE.INP	NZTABLE.OUT
Tìm mật khẩu	PASSWORD.???	PASSWORD.INP	PASSWORD.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.          ENCODE Mã hoá

            Để quản lý tốt các hồ sơ trong kỳ thi tuyển sinh, hội đồng tuyển sinh trường PTNK đã quyết định đánh số các hồ sơ theo một phương pháp khoa học. Mã hồ sơ của thí sinh là một chuỗi gồm 10 chữ số. Tuy nhiên không phải bất kỳ chuỗi 10 chữ số nào cũng là mã hồ sơ hợp lệ bởi vì hội đồng tuyển sinh đưa ra một quy định ràng buộc chặt chẽ cho các chữ số đó. Nếu M=a₁a₂..a₁₀ là một mã hồ sơ thì M phải thỏa mãn ràng buộc:

            Nếu đặt S(M)=1a₁+2a₂+3a₃+…+10a₁₀ thì S(M) phải là một số chia hết cho 11.

            Nhờ quy định này, trong những trường hợp do sơ xuất có một chữ số trong mã hồ sơ bị mờ, không đọc được thì ta vẫn có thể xác định được giá trị của nó. Ví dụ như: (quy ước ? là chữ số bị mờ):

·        Với M=00000000?1 thì có thể suy ra chữ số bị mờ là 5 vì theo ràng buộc, để S(M) là một số chia hết cho 11 nó chỉ có thể có giá trị là 55.

Input	Output
00000000?1	5
00000001?1	9
00722?0858	6

·        Tương tự với M=00000001?1 thì có thể suy ra chữ số bị mờ là 9.

·        Tương tự với M=00722?0858 thì có thể suy ra chữ số bị mờ là 6.

Yêu cầu: Hãy viết chương trình giúp hội đồng tuyển sinh suy ra được chữ số bị mờ trong mã hồ sơ.

Input ghi mã hồ sơ có 1 chữ số bị mờ được thay bằng dấu chấm hỏi.

Output ghi giá trị của chữ số bị mờ trong mã hồ sơ đã cho.

        Bài 1.          EXARRAY Biến đổi dãy số

            Cho dãy các số nguyên khác nhau đôi một a gồm n số a₁, a₂, ..., a_n và dãy số nguyên b gồm n số b₁, b₂, ..., b_n. Trên dãy số a ta có thể áp dụng phép biến đổi T(i) thực hiện phép hoán vị giá trị hai phần tử a_i và a_i+1 (0<i<n) .Vấn đề đặt ra là có tồn tại hay không một dãy các phép biến đổi T_i1, T_i2, …, T_ik sao cho khi áp dụng, dãy a ban đầu sẽ biến thành dãy b.

            Ví dụ nếu dãy a là 1, 3, 2, 4 và dãy b là 2, 1, 3, 4 thì ta có thẻ sử dụng dãy 2 phép biến đổi T(2) và T(1) để biến đổi a thành b.

            Yêu cầu: Cho hai dãy số a, b . Hãy chỉ ra một dãy các phép biến đổi a thành b hoặc cho biết không tồn tại dãy biến đổi như vậy.

Input gồm 3 dòng:

·        Dòng đầu tiên chứa số nguyên n là số lượng phần tử của mỗi dãy số (n ≤ 100).

·        Dòng thứ hai chứa n số nguyên đôi một khác nhau ứng với các phần tử của dãy số a.

·        Dòng cuối cùng chứa n số nguyên ứng với các phần tử của dãy số b.

Input	Output
4 1 3 2 4 2 1 3 4	2 2 1
1 5 2	-1

Các số trong 2 mảng a và b đều có giá trị nằm trong đoạn [-10000, 10000].

Output

·        Nếu không thể biến đổi a thành b, file chứa số duy nhất số -1.

·        Trong trường hợp ngựoc lại, file sẽ gồm 2 dòng:

o   Dòng đầu tiên chứa số nguyên k là số lượng phép biến đổi cần áp dụng.

o   Dòng thứ hai chứa k số nguyên duơng i₁, i₂, …, i_k ứng với các phép biến đổi T_i1, T_i2, …, T_ik tìm được.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi một dấu cách.

        Bài 1.          NZTABLE Biến đổi bảng

            Xét bảng vuông gồm n dòng và n cột. Các dòng được đánh số từ 1 đến n từ trên xuống dưới. Các cột được đánh số từ 1 đến n từ trái sang phải. Ô nằm ở vị trí dòng i và cột j của bảng được gọi là ô (i, j). Trên bảng A đã cho, khoảng cách từ ô (i, j) đến ô (p, q) được tính bằng |i - p| + |j - q|. Tại ô (i, j) của bảng A ghi số nguyên không âm a_ij, i = 1, 2 ,…, n; j = 1, 2, .., n. Dựa vào các số được ghi trên bảng A, người ta cần xây dựng một bảng B cùng kích thước với A mà trên đó ô (i, j) của bảng B sẽ được ghi số b_ij xác định như sau:

·        Nếu a_ij > 0 thì b_ij = a_ij

·        Nếu a_ij = 0 thì b_ij có giá trị bằng giá trị a_pq của ô (p, q) gần ô (i, j) nhất trong số các ô có giá trị khác không trên dòng i và cột j của bảng A. Trong truờng hợp có nhiều ô khác không có cùng khoảng cách nhỏ nhất đến (i, j) thì ô (p, q) đựoc chọn là ô chứa số lớn nhất trong chúng. Nếu tất cả các phần tử của dòng i và cột j đều có giá trị 0 thì b_ij = 0.

Yêu cầu: cho bảng A, hãy tìm bảng B.

Input	Output
4 1 0 3 0 4 0 0 5 0 0 6 0 0 0 0 0	1 3 3 5 4 4 6 5 4 6 6 6 4 0 6 5

Input

·        Dòng đầu tiên ghi số nguyên dương n (n ≤ 50)

·        Dòng thứ i trong số n dòng tiếp theo ghi n số nguyên không âm a_i1, a_i2, …, a_in là các số trên dòng thứ i của bảng, i = 1, 2,…, n; a_ij ≤ 10000.

Output gồm n dòng, dòng thứ i ghi n số nguyên dương b_i1, b_i2, …, b_in là các số trên dòng thứ i của bảng B.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi một dấu cách.

        Bài 1.          PASSWORD Tìm mật khẩu

            Việc bảo vệ máy tính của mình để hạn chế người  khác thâm nhập vào là một vấn đề đặt ra cho mọi nguời sử dụng máy tính. Để tăng tính an toàn trong lưu trữ, một nguời đã quyết định dấu mật khẩu truy cập máy tính của mình vào một xâu T với một quy ước sao cho khi cần anh ta có thể lấy lại đuợc mật khẩu từ T như sau:

            Là một người yêu thích số học anh ta thường chọn mật khẩu P là một số nguyên tố và đem dấu vào một xâu ký tự T sao cho P chính là số nguyên tố có giá trị lớn nhất trong số các số nguyên tố tạo được từ các xâu con của T (xâu con của một xâu ký tự T là một chuỗi liên tiếp các ký tự trong T).

            Ví dụ: xâu T=”Test1234#password5426” chứa mật khẩu là 23 vì T chứa các xâu con ứng với các số nguyên tố 2,3,23 và 5.

            Yêu cầu: Cho một xâu ký tự T. Tìm mật khẩu P đã dấu trong xâu T

Input	Output
Test1234#password5426	23

Input: gồm 1 dòng duy nhất là xâu T chiều dài không quá 250 ký tự

Output: chứa số P tìm được biết P có giá trị nhỏ hơn 10⁵. Dữ liệu cho đảm bảo T chứa ít nhất 1 số nguyên tố.