Bảng B 2021 - Thành phố Hà Nội

HỘI THI TIN HỌC TRẺ THÀNH PHỐ HÀ NỘI LẦN THỨ XXVI
Năm 2021

ĐỀ THI VÒNG CHUNG KẾT — BẢNG B - TRUNG HỌC CƠ SỞ
Thời gian làm bài 120 phút, không kể thời gian phát đề
Ngày thi: 18/04/2021 — Địa điểm thi: trường Đại học Phương Đông

Tổng quan

Tên bài	File chương trình	Điểm
Bài 1. Ghép hình	puzzle.*	100 điểm
Bài 2. Robot tặng quà	grobot.*	100 điểm
Bài 3. Ngày nghỉ phép	cday.*	100 điểm

Bài 1. Ghép hình (100 điểm)

Ghép hình là trò chơi mà các bạn nhỏ hay cả người lớn đều rất thích. Có một trò chơi ghép hình rất đơn giản như sau: cho ba mảnh ghép hình chữ nhật, hãy kiểm tra xem có thể ghép lại thành một hình chữ nhật to không, nếu có, hãy tính đường chéo của hình chữ nhật đó. Chú ý: không được xếp các hình chữ nhật chồng lên nhau; nếu có nhiều cách xếp thì chọn cách xếp tạo ra đường chéo lớn hơn.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm ba dòng, mỗi dòng gồm hai số nguyên dương a, b mô tả kích thước của hai cạnh kề nhau của hình chữ nhật.

Kết quả: Ghi ra thiết bị ra chuẩn

Nếu ghép được thành hình chữ nhật thì in ra độ dài của đường chéo hình chữ nhật đó (in ra phần nguyên được làm tròn xuống).
Nếu không ghép được thành hình chữ nhật thì in ra −1.

Dữ liệu	Kết quả	Giải thích
2 2 1 2 2 1	4	Ghép được thành hình chữ nhật như hình bên. Đường chéo có độ dài là 4.
4 3 1 1 1 1	-1	Không thể ghép được thành hình chữ nhật.

Ràng buộc:

Có 50% số lượng test ứng với 40% số điểm có 0 < a, b ≤ 10³;
Có 30% số lượng test khác ứng với 40% số điểm có 0 < a, b ≤ 10⁶;
Có 20% số lượng test còn lại ứng với 20% số điểm có 0 < a, b ≤ 2×10⁹.

Bài 2. Robot tặng quà (100 điểm)

Để khuyến khích các bạn trẻ nghiên cứu và chế tạo robot, Thành Đoàn Hà Nội đã tổ chức một hoạt động có tên “ROBOT tặng quà” dành cho các bạn thí sinh của kỳ thi Tin học trẻ.

Trên trục số có một robot đặt tại điểm 0 và n bạn đánh số từ 1 tới n, bạn thứ i đứng tại điểm a_i trên trục số (có thể có nhiều bạn đứng cùng một vị trí). Người chơi chính được lựa chọn một số nguyên d (d > 1) và thiết đặt bước nhảy của robot là d. Khi đó, từ một vị trí, robot có thể nhảy tiến hoặc nhảy lùi một khoảng cách đúng bằng d trên trục số, tức là nếu robot đang ở vị trí x, robot chỉ có thể nhảy sang một trong hai vị trí x + d hoặc x − d. Một bạn sẽ được robot tặng quà nếu tồn tại cách di chuyển robot nhảy từ điểm 0 tới vị trí bạn đó sau một số hữu hạn lần nhảy.

Với mong muốn có nhiều bạn được robot tặng quà, em hãy giúp người chơi chính chọn tham số nguyên d > 1 để có nhiều bạn được robot tặng quà nhất, cho biết số bạn được robot tặng quà.

Dữ liệu: Vào từ thiết bị vào chuẩn

Dòng đầu chứa số nguyên dương T ≤ 10⁵ là số bộ dữ liệu.
T nhóm dòng tiếp theo, mỗi nhóm gồm hai dòng mô tả một bộ dữ liệu: dòng 1 chứa số nguyên dương n ≤ 10⁶; dòng 2 chứa n số nguyên a₁,…,aₙ cách nhau bởi dấu cách (|a_i| ≤ 10⁶). Tổng các giá trị n trong các bộ dữ liệu vào không vượt quá 10⁶.

Kết quả: Ghi ra thiết bị ra chuẩn — với mỗi bộ dữ liệu, ghi ra một số nguyên duy nhất trên một dòng là số bạn được robot tặng quà theo phương án tìm được.

Dữ liệu	Kết quả	Giải thích
2 4 1 20 12 15 3 5 -5 15	2 3	Bộ dữ liệu thứ nhất: chọn d bằng 2, 3, 4 hoặc 5. Bộ dữ liệu thứ hai: chọn d bằng 5.

Bài 3. Ngày nghỉ phép (100 điểm)

Một công ty lập trình lên một kế hoạch làm việc cho N ngày, với T dự án, dự án thứ i có thời gian kéo dài từ ngày thứ a_i đến ngày thứ b_i. Các nhân viên phải đi làm trong thời gian công ty có dự án. Để đảm bảo số nhân viên làm việc và vẫn để nhân viên được nghỉ ngơi, công ty có quy định là những ngày không có dự án thì nhân viên được nghỉ và trong mỗi dự án nhân viên được nghỉ phép không quá một ngày.

Là một nhân viên lười biếng, Dino muốn nghỉ thật nhiều nhưng vẫn phải đúng luật của công ty, nên Dino sẽ lên kế hoạch nghỉ để mỗi dự án đều có chứa đúng một ngày nghỉ.

Em hãy lập trình giúp Dino tính xem theo kế hoạch trong N ngày của công ty và theo mong muốn của Dino thì được nghỉ tối đa bao nhiêu ngày?

Dữ liệu: Vào từ thiết bị nhập chuẩn

Dòng đầu tiên chứa hai số nguyên N, T (2 ≤ N, T ≤ 10⁶) tương ứng là kế hoạch trong N ngày và T dự án của công ty.
T dòng sau, dòng thứ i chứa hai số nguyên a_i và b_i mô tả thời gian bắt đầu và kết thúc dự án thứ i của công ty (1 ≤ i ≤ T; 1 ≤ a_i ≤ b_i ≤ N).

Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số ngày tối đa Dino có thể được nghỉ. Nếu không có cách chọn mà mỗi dự án đều có chứa đúng một ngày nghỉ thì in ra −1.

Dữ liệu	Kết quả	Giải thích
6 3 1 4 3 5 2 4	3	Có thể nghỉ 3 ngày: ngày 2, ngày 5, ngày 6.
5 3 1 5 2 3 4 5	-1	Không có cách chọn để mỗi dự án nghỉ đúng 1 ngày.

Ràng buộc:

Có 20% số lượng test ứng với 20% số điểm có 2 ≤ N, T ≤ 20;
Có 20% số lượng test khác ứng với 20% số điểm có 2 ≤ N, T ≤ 5000;
Có 30% số lượng test khác ứng với 30% số điểm có 2 ≤ N, T ≤ 10⁵;
Có 30% số lượng test còn lại ứng với 30% số điểm không có ràng buộc bổ sung.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English