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

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
Lần thứ XXVII – Năm 2021

ĐỀ THI BẢNG A – TIỂU HỌC - VÒNG THI SƠ KHẢO (QUỐC GIA)
Thời gian làm bài: 100 phút
Ngày thi: 08/08/2021

Bài 1. Chuẩn bị bàn - pretable

Kì thi Tin học trẻ năm nay có N thí sinh tham gia. Ban tổ chức đang cần chuẩn bị bàn cho các thí sinh ngồi dự thi. Biết mỗi bàn có thể ngồi được tối đa K thí sinh.

Hỏi: Ban tổ chức cần chuẩn bị tối thiểu bao nhiêu bàn?

Input: Dữ liệu nhập vào từ bàn phím gồm hai dòng:

Dòng thứ nhất chứa một số tự nhiên N là số lượng thí sinh tham gia kì thi.
Dòng thứ hai chứa một số tự nhiên K là số lượng tối đa thí sinh có thể ngồi một bàn.

(1 ≤ K ≤ N ≤ 10⁹)

Output: In ra màn hình một số duy nhất là số lượng bàn tối thiểu cần phải chuẩn bị.

Ví dụ:

Input	Output	Giải thích
`8` `2`	`4`	Cần chuẩn bị tối thiểu 4 bàn, khi đó mỗi bàn có 2 thí sinh.
`103` `5`	`21`	Cần chuẩn bị tối thiểu 21 bàn: 20 bàn có 5 thí sinh và 1 bàn có 3 thí sinh.

Bài 2. Số một số - n1digit

Số một số là một số tự nhiên mà các chữ số của số đó giống nhau. Ví dụ: 1, 8, 11, 555, 99999, …

Cho một số tự nhiên N. Hãy đếm số lượng số một số bé hơn hoặc bằng N.

Input: Dữ liệu nhập vào từ bàn phím gồm một số tự nhiên N (N ≤ 10⁹).

Output: In ra màn hình một số duy nhất là số lượng số thỏa mãn đề bài.

Ví dụ:

Input	Output	Giải thích
`15`	`10`	Khi N = 15 thì có 10 số là 1, 2, 3, 4, 5, 6, 7, 8, 9, 11.
`111`	`19`	Khi N = 111 thì có 19 số: 9 số từ 1-9, 9 số 11,22,…,99, và 1 số 111.

Bài 3. Đếm đĩa - countpots

Có hệ thống đĩa xếp chồng trên một cọc. Đĩa 1 đựng được a lít nước, mỗi đĩa sau đựng được nhiều hơn đĩa trước b lít nước. Khi rót nước từ trên xuống, nếu đĩa thứ i đầy, nước sẽ chảy xuống đĩa thứ i+1.

Hỏi: khi rót N lít nước từ đĩa 1 xuống thì có bao nhiêu đĩa có nước? (Giả sử nước không rơi ra ngoài và số lượng đĩa luôn đủ.)

Input: Ba dòng: N (số lít nước rót xuống), a (dung lượng đĩa 1), b (dung lượng đĩa sau nhiều hơn đĩa trước). (N ≤ 10¹⁶; a ≤ 1000; b ≤ 10).

Output: Số lượng đĩa có nước.

Ví dụ:

Input	Output	Giải thích
`8` `1` `1`	`4`	Dung tích các đĩa: 1, 2, 3, 4, 5, … Rót 8 lít: đĩa 1-3 đầy (1+2+3=6), đĩa 4 có 2 lít.
`10` `2` `3`	`3`	Dung tích các đĩa: 2, 5, 8, 11, … Rót 10 lít: đĩa 1-2 đầy (2+5=7), đĩa 3 có 3 lít.

Bài 4. Đặt sỏi - arrball

Ban đầu có 2 viên sỏi đặt trên một đường thẳng. Lặp lại thao tác: ở mỗi lượt, tại vị trí trung điểm của mỗi cặp viên sỏi liên tiếp hiện có, đặt thêm một viên sỏi mới.

Minh hoạ: ban đầu 2 sỏi số 0 ở hai đầu; lượt 1 đặt sỏi số 1 ở giữa; lượt 2 đặt thêm 2 sỏi số 2 vào trung điểm hai đoạn

Nguồn ảnh: scratch.hourofcode.vn

Ban đầu chỉ có hai viên sỏi đặt trên một đường thẳng.
Lượt đặt thứ nhất (N = 1): thêm một viên sỏi vào trung điểm của hai viên ban đầu.
Lượt đặt thứ hai (N = 2): đã có 3 viên sỏi của lượt trước và đặt thêm hai viên sỏi (được đánh số 2) vào vị trí trung điểm của hai đoạn thẳng như hình mô tả.

Giả sử luôn có khoảng cách để có thể đặt một viên sỏi vào giữa hai viên sỏi.

Hỏi: sau lượt đặt thứ N có tất cả bao nhiêu viên sỏi? Vì kết quả có thể rất lớn, chỉ cần đưa ra chữ số cuối cùng của đáp án.

Input: Một số tự nhiên N (N ≤ 10⁹).

Output: Chữ số cuối của số lượng sỏi.

Ví dụ:

Input	Output	Giải thích
`2`	`5`	Khi N = 2 thì số sỏi là 5 viên.
`4`	`7`	Khi N = 4 thì số sỏi là 17 viên → chữ số cuối là 7.

Bài 5. Tìm chữ số thứ N - finddigit

Cho hai số tự nhiên A và N. Viết liên tiếp các số tự nhiên bắt đầu từ A, cùng tính chẵn/lẻ với A (tức là A, A+2, A+4, …) trên một đường thẳng.

Hỏi: chữ số thứ N (tính từ trái) là bao nhiêu?

Input: Hai dòng: A và N (A, N ≤ 10⁹).

Output: Chữ số ở vị trí thứ N.

Ví dụ:

Input	Output	Giải thích
`12` `3`	`1`	Dãy số: 12141618202224… Chữ số thứ 3 là 1.
`7` `8`	`5`	Dãy số: 7911131517… Chữ số thứ 8 là 5.

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