Tin học Tiểu học

Bài gợi ý: Số lần xuất hiện 2 (bản dễ)

Tóm tắt: Bạn có một dãy gồm \(N\) số nguyên dương. Nhiệm vụ của bạn là liệt kê các số xuất hiện trong dãy theo thứ tự từ bé đến lớn, kèm theo số lần mỗi số xuất hiện.

Giả sử dãy có 9 số: 2 3 1 2 3 4 5 4 3. Số bé nhất là số 1 và số 1 chỉ có đúng 1 lần. Số 2 có 2 lần, số 3 có 3 lần, số 4 có 2 lần, còn số 5 có 1 lần. Kết quả cần in ra lần lượt từng dòng: 1 1, 2 2, 3 3, 4 2, và 5 1.

Nếu với mỗi số, ta lại đi dò từ đầu đến cuối dãy để đếm, ta sẽ phải nhìn lại cả dãy rất nhiều lần. Thay vì dò đi dò lại, ta có thể chuẩn bị sẵn một bảng ghi nhớ hay một mảng đếm, đặt tên là cnt. Lúc đầu, mọi ô trong bảng đều mang số 0. Khi đọc đến mỗi giá trị \(x\), ta chỉ cần tăng ô tương ứng lên một đơn vị bằng lệnh cnt[x] += 1.

Cách làm này gọi là đếm phân phối, tức là gom các số giống nhau vào chung một ô để đếm. Vì các số \(A_i\) trong đề bài không vượt quá \(10^5\), bảng đếm chỉ cần chứa tối đa \(100001\) ô là đủ. Sau khi đọc xong cả dãy, bạn cho một biến \(v\) chạy từ \(1\) lên đến số lớn nhất: hễ thấy cnt[v] > 0 thì in ra giá trị \(v\) cùng số lần cnt[v].

Bài tập tương tự:

• Diff-Query (version 1): Luyện tập xử lý các giá trị khác nhau trên từng đoạn của dãy.
• CSES - Distinct Values Queries | Truy vấn Giá trị Khác nhau: Nâng cao kỹ năng đếm số lượng phần tử phân biệt khi có nhiều câu hỏi.

Bạn chỉ cần tạo mảng đếm cnt, duyệt qua từng phần tử để cập nhật cnt[x] += 1, rồi duyệt \(v\) từ \(1\) đến \(10^5\) và in ra những ô có cnt[v] > 0.

Bài gợi ý: Sắp xếp không giảm
Tóm tắt: Cho một dãy gồm \(n\) số nguyên dương. Nhiệm vụ của bạn là sắp xếp lại các số này theo thứ tự từ bé đến lớn rồi in ra màn hình.

Chẳng hạn với \(6\) số: 91 451 43 3 451 54. Số nhỏ nhất trong dãy là \(3\), tiếp theo là \(43\), rồi đến \(54\), \(91\), và hai số \(451\) đứng ở cuối cùng. Kết quả sau khi xếp lại là 3 43 54 91 451 451.

Nếu làm thủ công, ta thường tìm số nhỏ nhất rồi nhặt ra trước, sau đó tìm tiếp số nhỏ nhì trong các số còn lại. Tuy nhiên, khi dãy có đến \(N = 10^4\) số, việc tự duyệt tìm từng số như vậy sẽ phải so sánh rất nhiều lần và dễ bị chậm thời gian.

Trong các ngôn ngữ lập trình, ta có sẵn công cụ sắp xếp (thuật toán sort) giúp máy tự đảo các số về đúng thứ tự tăng dần rất nhanh. Bạn chỉ cần lưu toàn bộ dãy vào một danh sách, gọi lệnh a.sort() trong Python hoặc sort(a, a + n) trong C++, rồi dùng một vòng lặp in lần lượt từng số ra màn hình.

Bài gợi ý: Đếm nguyên âm
Tóm tắt: Với mỗi từ trong số \(n\) từ được nhập vào, bạn hãy đếm xem từ đó có bao nhiêu chữ cái là nguyên âm (\(a, e, i, o, u\)).

Hãy nhìn vào từ "Hello" trong ví dụ của đề bài. Từ này gồm \(5\) chữ cái: H, e, l, l, o. Khi kiểm tra từng chữ, ta thấy có đúng \(2\) nguyên âm là e và o.

Để máy tính làm giúp bạn, ta dùng một biến đếm và gán cnt = 0 ở đầu mỗi từ. Sau đó, ta cho máy đi xem lần lượt từng chữ cái từ trái sang phải. Nếu gặp một trong các chữ cái a, e, i, o, u (hoặc chữ in hoa tương ứng), ta lập tức tăng biến đếm bằng câu lệnh cnt += 1.

Lưu ý nhỏ là đề bài cho nhiều dòng tương ứng với \(n\) từ khác nhau. Vì vậy, sau khi đếm xong một từ và in kết quả ra, bạn chỉ cần gán lại cnt = 0 trước khi đọc sang từ tiếp theo.

Kỳ thi: KOI 2026 - Vòng 2 - Tiểu học
Tóm tắt: Bộ đề gồm 4 bài toán về xếp hàng, ghép khối xúc xắc và chia đồ vật với các bài đầu rất gần gũi cho học sinh tiểu học luyện tư duy đếm và viết vòng lặp.

Ở bài KOI 2026 - Distancing, ta có \(N\) bạn nhỏ cần đứng xếp hàng trên một đường thẳng sao cho bạn thứ \(i\) không đứng quá mốc \(A_i\) và mỗi bạn cách bạn đứng ngay sau ít nhất \(K\) bước. Cách nghĩ trực tiếp là thử chọn vị trí bắt đầu cho bạn thứ nhất từ số lớn nhất có thể, sau đó kiểm tra xem vị trí của từng bạn tiếp theo có vượt quá mốc cho phép hay không.

Chỉ cần một vòng lặp kiểm tra từ mốc lớn giảm dần về mốc nhỏ, người học đã có thể tìm được vị trí hợp lệ cho cả hàng. Đề thi KOI 2026 - Vòng 2 - Tiểu học xoay quanh các tình huống đời sống rất trực quan, giúp các bạn nhỏ dễ dàng vẽ thử ra giấy và chuyển ý tưởng thành từng bước lệnh so sánh.

Sang bài KOI 2026 - Dice Tower Stacking, đề bài cho các viên xúc xắc có hai mặt đối nhau luôn có tổng bằng \(7\) và yêu cầu xếp chồng thành ít tháp nhất. Bằng cách đếm số viên có mặt trên là \(x\) và mặt trên là \(7-x\), ta có thể ghép từng cặp số đối nhau để giảm số lượng tháp cần dùng.

Nếu muốn thử sức với bài toán logic nhiều bước hơn, bạn có thể khám phá KOI 2026 - Snack Distribution để sắp thứ tự vào phòng nhận bánh, hoặc bài KOI 2026 - Game với trò chơi tìm đường thoát khỏi mê cung.

Bạn nên đọc và viết code thử ngay bài KOI 2026 - Distancing, sau đó chuyển sang bài KOI 2026 - Dice Tower Stacking trước khi đọc tiếp các bài còn lại.