[TSNK] Đề thi tuyển sinh PTNK - 2017

Thời gian làm bài: 150 phút.

Tổng quan đề bài

Bài

Tên bài

File chương trình

File dữ liệu vào

File kết quả

1

Trò chơi biểu thức

EXP.*

EXP.INP

EXP.OUT

2

Dàn đèn màu

LIGHTS.*

LIGHTS.INP

LIGHTS.OUT

3

Bội số chung nhỏ nhất

LCM.*

LCM.INP

LCM.OUT

4

Xây dựng trạm phát sóng

STATION.*

STATION.INP

STATION.OUT

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++.

Bài 1: Trò chơi biểu thức

Dũng và Vũ là hai bạn thân rất mê toán học. Đôi bạn thường nghĩ ra các bài toán để chơi giải trí với nhau. Hôm nay Vũ nghĩ ra một trò chơi mới và ngay lập tức mời Dũng cùng chơi. Trò chơi Vũ đề xuất như sau: Vũ viết lần lượt n số nguyên a1, a2,…, an  thành một hàng, sau đó giữa hai số ai và ai+1  sẽ điền vào dấu + khi ilà số chẵn, ngược lại điền dấu -. Như vậy Vũ sẽ có một biểu thức gồm nsố hạng a1, a2, …, an   với dấu –và + đan xen nhau:

 a1-a2+a3-a4+a5-…+(-1)n-1an

Vũ đưa cho Dũng biểu thức này và yêu cầu Dũng thực hiện nhiều nhất một phép đổi chỗ hai số hạng cho nhau sao cho giá trị S của biểu thức nhận được lớn nhất có thể.

Yêu cầu: Hãy giúp Dũng tìm giá trị S.

Dữ liệu: Vào từ file văn bản EXP.INP trong đó:

  • Dòng đầu chứa số n,
  • Dòng thứ hai chứa n số nguyên a1, a2, …, an

Kết quả: Ghi ra file văn bản EXP.OUT số S.

Ví dụ:

 

EXP.INP

EXP.OUT

6

2 -5 +4 -7 +9 -1

12

Giới hạn: n ≤ 106; ai≤109 với mọi i=1, 2, …, n

[Phân tích-gợi ý giải bài - đang cập nhật]

Bài 2: Dàn đèn màu

            Để chuẩn bị cho những đứa con trai mình đón ngày Quốc tế thiếu nhi 1/6, Vũ treo một dãy n đèn màu, các đèn được đánh số từ 1 tới n từ trái qua phải. Mỗi màu có mã màu là một số nguyên dương trong phạm vi từ 1 tới 100 và hai màu khác nhau có mã màu khác nhau, đèn thứ icó mã màu ci . Mấy bé của nhà Vũ đã bắt đầu tập đếm nên mẹ Trân muốn các bé đếm các đèn cùng màu càng nhiều càng tốt. Mỗi lần tập đếm mẹ Trân yêu cầu các bé đếm một dãy liên tiếp các bóng đèn cùng màu. Sau khi treo xong, Vũ mới phát hiện ra dãy liên tiếp các đèn cùng màu không đủ lớn để các bé tập đếm nên quyết định thay đúng một đèn bằng màu khác sao cho nhận được một dãy đèn cùng màu nhiều nhất có thể.

Yêu cầu: Với trạng thái của dãy đèn đã treo, hãy giúp Vũ thay một bóng đèn sao cho nhận được dãy đèn liên tiếp cùng màu với số đèn cùng màu S là lớn nhất.

Dữ liệu: Vào từ file văn bản LIGHTS.INP trong đó:

  • Dòng đầu ghi số n,
  • Dòng thứ hai ghi n số c1, c2, …, cn.

Dữ liệu đảm bảo dãy đèn ban đầu có ít nhất hai bóng đèn có màu khác nhau.

Kết quả: Ghi ra file văn bản LIGHTS.OUT số đèn Sliên tiếp cùng màu sau khi đổi một bóng đèn.

Ví dụ:

LIGHTS.INP

LIGHTS.OUT

10

2 8 8 8 3 8 8 6 6 3

6

Giải thích: Thay bóng đèn thứ 5 có mã màu 3 bằng bóng đèn mã màu 8 nhận được dãy gồm 6 đèn liên tiếp cùng mã màu 8.

Giới hạn: n≤106;1≤ci≤100  với mọi i=1, 2, …, n

[Phân tích-gợi ý giải bài]

Bài 3: Bội chung nhỏ nhất

Bội số chung nhỏ nhất của các số dương a1, a2, …, am  là số nguyên dương K nhỏ nhất sao cho Kchia hết cho mọi số a1, a2, …, am .

Yêu cầu: Với số nguyên dương n cho trước, hãy tìm bội số chung nhỏ nhất  K của các số 1, 2, …, n.  Vì số K có thể rất lớn nên bạn chỉ đưa ra phần dư của phép chia K cho 109+7.

Dữ liệu: Vào từ file văn bản LCM.INP trong đó chứa duy nhất số n.

Kết quả: Ghi ra file văn bản LCM.OUT phần dư của phép chia K cho 109+7.

Ví dụ:

LCM.INP

LCM.OUT

10

2520

Giới hạn: n≤106

[Phân tích-gợi ý giải bài - đang cập nhật]

Bài 4: Xây dựng trạm phát sóng

Wonder Land là một thành phố thông minh với nền tảng là các thiết bị công nghệ cao cùng với hệ thống phần mềm ứng dụng luôn kết nối internet cung cấp dịch vụ tiện ích cho mọi cư dân. Wonder Land có n khu dân cư được quy hoạch cách đều nhau một đơn vị độ dài dọc theo một con đường thẳng tắp. Như vậy Wonder Land được biểu diễn bởi trục số và vị trí n khu dân cư là các điểm có tọa độ nguyên liên tiếp từ 0 đến n-1 .

Nhằm nâng cao tốc độ kết nối các dịch vụ, chính quyền lên kế hoạch xây dựng mới các trạm phát sóng di động thế hệ đột phá (Innovation Generation) sao cho mọi khu dân cư đều nhận được sóng. Mỗi trạm phát sóng phủ một vùng bán kính R với tâm là trạm phát sóng và mọi khu dân cư có khoảng cách đến trạm phát sóng không lớn hơn R đều nhận được sóng từ trạm đó. Sau một thời gian khảo sát, chính quyền có được danh sách m vị trí trên trục đường có thể xây dựng trạm, vị trí thứ icó tọa độxi. Nhà quản lý muốn chọn ra một số vị trí lắp đặt sao cho số trạm cần phải xây dựng là ít nhất và mọi khu dân cư đều nhận được sóng của ít nhất một trạm.

Chẳng hạn n=12 , có thể xây dựng trạm tại 8 vị trí với tọa độ là: 3, 1, 0, 5, 9, 6, 10, 11 . Với bán kính phát sóng R=2 , ta chỉ cần xây 3 trạm tại các tọa độ 1, 6, 11 , tương ứng tại các vị trí 2, 6 và 8 thì có thể phủ sóng cho tất cả khu dân cư.

 

Yêu cầu: Cho số khu dân cư n, dãy m số nguyên x1,x2,…,xm (0≤xi≤n-1;1≤m≤n) – tọa độ có thể xây dựng trạm phát sóng và số nguyên R– bán kính phát sóng. Hãy tìm phương án chọn ra ít nhất các vị trí cần xây dựng trạm sao cho toàn bộ n khu dân cư đều nhận sóng. Nếu không tìm được phương án thì ghi 0.

Dữ liệu: Vào từ file văn bản STATION.INP trong đó:

  • Dòng đầu ghi 3 số n, m vàR,
  • Dòng thứ hai ghi m số x1, x2, …, xm

Kết quả: Ghi ra file văn bản STATION.OUT gồm hai dòng:

  • Dòng đầu ghi số k (k≥0)  – số trạm cần xây dựng,
  • Nếu k>0  thì dòng thứ hai ghi ra k chỉ số các vị trí cần xây dựng trạm.

Ví dụ:

STATION.INP

STATION.OUT

12 8 2

3 1 0 5 9 6 10 11

3

2 6 8

Giới hạn: 1≤n≤106

[Phân tích-gợi ý giải bài - đang cập nhật]

[Tải PDF]