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

Mời các bạn tham khảo
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 -------------------------

ĐỀ THI TUYẾN SINH LỚP 10 Năm học 2014 - 2015 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
Khoảng cách	DISTANCE.???	DISTANCE.INP	DISTANCE.OUT
Bánh sinh nhật	CAKES.???	CAKES.INP	CAKES.OUT
Trò chơi cắm cờ	FLAG.???	FLAG.INP	FLAG.OUT
Chia kẹo	CANDY.???	CANDY.INP	CANDY.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.                       DISTANCE Khoảng cách

            Hai xâu kí tự được gọi là bạn bè của nhau nếu ta có thể sắp xếp các ký tự của một xâu để được xâu còn lại. Ví dụ: xâu ‘banbe’ là bạn bè của xâu ‘beban’, tuy nhiên xâu ‘laptrinh’ không phải là bạn bè của xâu ‘thuattoan’ (vì chữ ‘t’ chỉ xuất hiện 1 lần trong ‘laptrinh’ nhưng xuất hiện đến 3 lần trong xâu ‘thuattoan’).

            Khoảng cách giữa hai xâu ký tự là số ký tự ít nhất cần phải xóa (trên cả hai xâu) để hai xâu còn lại là bạn bè của nhau. Ví dụ, khoảng cách giữa hai xâu ‘ptnk’ và ‘thpt’ là 4, còn khoảng cách giữa hai xâu ‘tin’ và ‘hoc’ là 6.

Yêu cầu: hãy tính khoảng cách giữa hai xâu cho trước.

Input	Output
begin end	4

 Input: gồm 2 dòng, mỗi dòng chứa một xâu kí tự chỉ gồm các chữ cái tiếng Anh thường, mỗi dòng có không quá 10⁶ ký tự.

Kết quả: một số nguyên duy nhất là độ đo giữa hai xâu trong file dữ liệu.

Giới hạn: 50% số test mỗi dòng có không quá 100 ký tự.

CAKES Bánh sinh nhật

Trong ngày sinh nhật của mình, Mai - một hoa khôi của trường, được các bạn nam trong trường hâm mộ tặng cho rất nhiều bánh kem. Vì số lượng bánh là rất lớn nên Mai phải xếp chồng các bánh lên nhau mới có đủ chỗ để.

Vì những chiếc bánh kem rất mềm nên Mai chỉ có thể xếp mỗi chồng tối đa 2 bánh kem và bánh kem ở trên có trọng lượng tối đa bằng một nửa trọng lượng của bánh đặt bên dưới. Như vậy có thể có những chồng chỉ gồm 1 chiếc bánh kem.

Ví dụ: có 8 bánh kem lần lượt có trọng lượng là 2, 5, 7, 6, 9, 8, 4, 2.

Một phương án xếp để nhận được 5 chồng bánh là:

Yêu cầu: tìm số chồng bánh ít nhất mà Mai có thể xếp được từ n chiếc bánh cho trước.

Input

Input	Output
8 2 5 7 6 9 8 4 2	5

·         Dòng đầu ghi số nguyên dương n là số bánh kem (n ≤ 10⁶)

·        Dòng thứ hai ghi n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹) là trọng lượng của n chiếc bánh kem tương ứng.

Output: ghi một số nguyên dương duy nhất là số chồng bánh tìm được.

FLAG Trò chơi cắm cờ

Ban chấp hành Đoàn trường PTNK dự định tổ chức một trò chơi vận động và có tính chất chiến thuật dành riềng cho các học sinh lớp chuyên Tin trong dịp đón học sinh mới năm 2014-2015.

            Để tổ chức trò chơi các anh chị trong Ban chấp hành đoàn trường chuẩn bị một số khu đất hình vuông rời nhau, bốn góc của mỗi khu đất có khoan một lỗ nhỏ để cắm cờ. Tại một số góc cắm sẵn một lá cờ và mỗi khu đất có ít nhất một lá cờ được cắm. Người chơi được phép rút một lá cờ bất kì cắm vào một góc trống của khu đất nào đó, Mỗi lần thực hiện động tác này được tính là một lượt chơi. Nhiệm vụ của bạn là tìm một phương án chơi sao cho số khu đất có đủ bốn lá cờ ở bốn góc là nhiều nhất đồng thời số lượt chơi là ít nhất.

Input	Output
4 2 3	5

            Yêu cầu: Với một trạng thái trò chơi cho trước, hãy xác định số lượt chơi ít nhất để nhận được nhiều nhất các khu đất có đủ 4 lá cờ

Input: ghi một dòng duy nhất chứa 3 số a₁, a₂, a₃ với a₁ là số khu đất chỉ cắm một lá cờ, a₂ là số khu đất chỉ cắm đúng 2 lá cờ và a₃ là số khu đất cắm đúng 3 lá cờ. (0 ≤ a₁, a₂, a₃ ≤ 10⁹)

Output: ghi số lượt chơi ít nhất tìm được

Giải thích: bạn phải cần ít nhất 5 lượt chơi để hình thành được 4 khu đất nà 4 góc đều có cờ. Một trong các phương án đó như sau: Rút 3 lá cờ ở 3 khu đất  chỉ có 1 lá cờ cắm vào 3 khu đất đã có sẵn 3 lá cờ để được 3 khu đất đủ 4 lá cờ. Rút 2 lá cờ ở khu đất có 2 lá cờ cắm vào khu đất còn lại có 2 lá cờ thu được khu đát thứ 4 có 4 lá cờ. tổng cộng cần 5 lượt chơi.

Giới hạn: 15/20 test có 0 ≤ a₁, a₂, a₃ ≤ 10⁵.

CANDY Chia kẹo

            Các bạn học sinh trường PTNK chuẩn bị phân phát kẹo cho trẻ em nhân dịp tết trung thu. Các bạn đã chuẩn bị n hộp để đựng kẹo,các hộp được đánh số từ 1 đến n. ban đầu các bạn học sinh đã bỏ vào các hộp một số lượng kẹo, hộp thứ i có a[i] viên kẹo.

            Ban đại diện Cha Mẹ học sinh của trường chuẩn bị thêm cho các em M viên kẹo và các học sinh trong nhóm quyết định đưa thêm kẹo vào các hộp. Để cho các hộp có số lượng kẹo tương đối đều nhau, các bạn quyết định bỏ thêm kẹo vào các hộp theo quy tắc sau : Mỗi lần lấy một viên kẹo trong số các kẹo mà Ban đại diện Cha Mẹ học sinh chuẩn bị và bỏ vào hộp chứa ít kẹo nhất. Nếu có nhiều hộp như vậy thì đưa vào hộp có chỉ số nhỏ nhất. Quá trình này lặp lại cho tới khi hết M viên kẹo.

Yêu cầu: Xác định số lượng kẹo trong mỗi hộp sau khi phân hết M viên kẹo

Input

Input	Output
4 4 2 1 4 2	3 3 4 3

·        Dòng đầu chứa hai số N và M (0 ≤ N ≤ 10⁵; 1 ≤ M ≤ 10⁹)

·        Dòng thứ hai chứa N số a₁, a₂, …, a_N. (0 ≤ a_i ≤ 10⁹)

Output: ghi một dòng duy nhất gồm N số, trong đó số thứ i là số kẹo trong hộp thứ i sau khi chia xong M viên kẹo.

Giới hạn: 50% số test có N ≤ 5000 và M ≤ 5000.