Bảng B 2020 - Vòng sơ khảo quốc gia

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
Lần thứ XXVI – 2020 (Đề chính thức)

ĐỀ THI TUYỂN CHỌN VÒNG SƠ KHẢO QUỐC GIA
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: 26/7/2020

Tổng quan bài thi

TT	Tên bài	File chương trình	Thời gian chạy	Điểm
1	Trò chơi tính toán	`mgame.*`	1 giây	50
2	Phân số	`fraction.*`	1 giây	50

Hãy lập trình giải các bài toán sau:

Bài 1. Trò chơi tính toán (50 điểm)

Một lớp học gồm n bạn, các bạn được đánh số thứ tự từ 1 đến n để tham gia một trò chơi như sau: Ban đầu, bạn thứ i (i = 1, 2, …, n) sẽ ghi nhớ số i. Sẽ có k lượt, mỗi lượt, mỗi bạn sẽ ghi nhớ một số mới là bình phương số mình đang ghi nhớ. Kết thúc k lượt, các bạn sẽ nói số mà mình đang ghi nhớ cho cô giáo, nếu tất cả các bạn trong lớp đều trả lời đúng cô giáo sẽ cho một phần thưởng cho cả lớp.

Trước khi các bạn trả lời, lớp trưởng muốn kiểm tra sơ bộ bằng cách tìm chữ số hàng đơn vị của số S, trong đó S là tổng tất cả các số mà các bạn đang ghi nhớ sau lượt.

Yêu cầu: Cho k, n, hãy tìm chữ số hàng đơn vị của số S, trong đó S là tổng tất cả các số mà các bạn đang ghi nhớ sau lượt.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm hai số nguyên dương k, n.

Kết quả: Ghi ra thiết bị ra chuẩn một chữ số là chữ số hàng đơn vị của số S.

Ví dụ:

Dữ liệu vào	Kết quả ra	Giải thích
`1 3`	`4`	Các số ban đầu các bạn ghi nhớ là: 1, 2, 3. Các số các bạn ghi nhớ sau lượt 1 là: 1, 4, 9. Tổng các số các bạn đang ghi nhớ là: 14

Ràng buộc:

Có 20% số lượng test ứng với 20% số điểm có n ≤ 10³; k = 1;
Có 20% số lượng test khác ứng với 20% số điểm có n ≤ 10³; k ≤ 10³;
Có 20% số lượng test khác ứng với 20% số điểm có n ≤ 10⁹; k = 1;
Có 20% số lượng test khác ứng với 20% số điểm có n ≤ 10⁹; k ≤ 10⁹;
Có 20% số lượng test còn lại ứng với 20% số điểm có n ≤ 10¹⁸; k ≤ 10¹⁸.

Bài 2. Phân số (50 điểm)

Xét bài toán với n phân số a₁/b₁, a₂/b₂, …, aₙ/bₙ (aᵢ, bᵢ nguyên dương), hãy tìm dãy chỉ số 1 ≤ i₁ < i₂ < ⋯ < i_k ≤ n sao cho a_{i₁}/ b_{i₁} < a_{i₂}/b_{i₂} < ⋯ < a_{i_k}/b_{i_k} mà k lớn nhất.

Bài toán trên được mở rộng như sau: Hãy tìm cách đảo lại một phân số nếu muốn (phân số aᵢ/bᵢ đảo lại thành phân số bᵢ/aᵢ), sau đó lại tìm dãy chỉ số thỏa mãn đề bài mà k lớn nhất có thể.

Yêu cầu: Cho n phân số và số nguyên w, trong đó w = 0 nghĩa là không được phép đảo bất kỳ một phân số nào (bài toán ban đầu) hoặc w = 1 nếu được phép đảo không quá 1 phân số (bài toán mở rộng), hãy đưa ra giá trị k lớn nhất có thể.

Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng đầu ghi hai số nguyên n, w;
Dòng thứ i (i = 1,2, …, n) trong n dòng tiếp theo chứa hai số nguyên dương aᵢ, bᵢ có giá trị không vượt quá 10⁹ lần lượt là tử số và mẫu số của phân số thứ i.

Kết quả: Ghi ra thiết bị ra chuẩn một số nguyên là giá trị k lớn nhất tìm được.

Ví dụ:

Dữ liệu vào	Kết quả ra
`4 0` `5 1` `1 3` `3 2` `1 2`	`2`
`4 1` `5 1` `1 3` `3 2` `1 2`	`3`

Ràng buộc:

Có 25% số test ứng với 25% số điểm của bài có n ≤ 10; w = 0;
Có 25% số test khác ứng với 25% số điểm của bài có n ≤ 10; w = 1;
Có 25% số test khác ứng với 25% số điểm của bài có n ≤ 1000; w = 0;
Có 25% số test còn lại ứng với 25% số điểm của bài có n ≤ 1000; w = 1.

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