D. [GCC TRAINING 2024 — PRACTICE 2] Số mạnh mẽ
- Xây dựng hàm con
tongChuSo()
để tính tổng chữ số của n và hàmsnt()
để kiểm tra số đó có phải là số nguyên tố không - Lưu ý do đếm trong khoảng $$$l$$$ và $$$r$$$ nên xét từ $$$l + 1$$$ đến $$$r$$$
E. [GCC TRAINING 2024 — PRACTICE 2] Số vui vẻ
- Dễ thấy số có ước số là một số lẻ là số chính phương vì vậy ta chỉ cần kiểu tra xem đó có là số chính phương không ( số chính phương là một số nếu là bình phương của một số nguyên
- Lưu ý do đếm trong khoảng l và r nên xét từ l+1 đến r
F. [GCC TRAINING 2024 — PRACTICE 2] Cửa hàng thuốc lá
- Ban đầu, Bobs có n bao thuốc lá, và mỗi ngày anh ta hút hết một bao.
- Sau khi hút hết một bao, anh ta sẽ giữ lại vỏ bao thuốc. Khi anh ta tích lũy đủ k vỏ bao thuốc, anh ta có thể đổi lấy 1 bao thuốc mới.
- Chúng ta sẽ liên tục thực hiện việc đếm số ngày Bobs hút thuốc, đồng thời khi đủ vỏ bao, ta sẽ đổi lấy bao thuốc mới. Quá trình này lặp lại cho đến khi không còn đủ vỏ bao để đổi.
G. [GCC TRAINING 2024 — PRACTICE 2] Số đặc biệt
- Xây dựng hàm con
tongChuSo()
để tính tổng chữ số của n và hàmsnt()
để kiểm tra số đó có phải là số nguyên tố không và tổng chữ số của n có phải là số nguyên tố không
J. [GCC TRAINING 2024 — PRACTICE 2] Vẽ hình
- Nhận thấy các đường thẳng như trong hình vẽ là các đường thoả mãn để in ra
*
còn lại in ra‘ ‘
L. [GCC TRAINING 2024 — PRACTICE 2] Chữ số cuối cùng khác
Thoạt đầu các bạn sẽ thử tính toàn bộ giá trị của n!, nhưng điều này không khả thi cho n lớn (vì n có thể lên đến $$$10^6$$$). Khi tính giai thừa n!, nó có thể có nhiều số 0 ở cuối. Các số 0 này xuất hiện do tích của 2 và 5, vì 10=2×5.
Ví dụ: 6! = 2.3.4.5.6 = 720 (số 0 ở đây do cặp 2 và 5 tạo nên).
Do đó, để tìm chữ số cuối cùng khác 0, ta cần bỏ qua các số 0 tạo ra bởi các cặp (2,5) và tính giai thừa của các thành phần còn lại.
Cụ thể: Khi phân tích các thừa số trong phép tính giai thừa, chúng ta bỏ qua các bội số của 2 và 5 bằng cách chia các bội này với 2 hoặc 5. Đồng thời, đếm số lần xuất hiện của 2 và 5 trong quá trình tính tích. Sau đó, các thành phần còn lại đều là thành phần không có số 2 và 5, ta tính giai thừa như bình thường và chia modulo 10 để lấy chữ số cuối cùng.
Tuy nhiên, khi chúng ta chia các bội số với 2 hoặc 5; sẽ có những bội số của 2 nhiều hơn bội số của 5, những số 2 này không nhân với 5 được nên không tạo đuôi 0. Do đó chúng ta tính toán số lượng số 2 này và nhân vào giai thừa, tiếp tục chia modulo 10 kết quả cuối cùng là kết quả cần tìm.
M. [GCC TRAINING 2024 — PRACTICE 2] Phép toán cơ
Với bài tập này, chúng ta sẽ tìm ra quy luật từ test mẫu, từ đó code đúng định dạng đề yêu cầu.
Phân tích trường hợp n = 5:
edcbabcde
ddcbabcdd
cccbabccc
bbbbabbbb
aaaaaaaaa
bbbbabbbb
cccbabccc
ddcbabcdd
edcbabcde
Có thể thấy kết quả in ra là một ma trận 2 chiều với kích thước chiều ngang là $$$2 * n – 1$$$ (2 * 5 – 1 = 9 ký tự) và chiều dọc là $$$2 * n – 1$$$ (2 * 5 – 1 = 9 chuỗi).
Về quy luật của chuỗi, các ký tự giảm dần từ n (tương ứng số thứ tự trong bảng chữ cái) ở biên ngoài cho tới 1 ở tâm; nửa còn lại của chuỗi đối xứng nửa đầu tiên. Các chuỗi tiếp theo giảm dần từ biên ngoài vào trong cho tới định dạng giữa là chuỗi n chữ cái a; sau đó các chuỗi tiếp theo tăng dần từ 1 ra ngoài cho tới khi đạt được định dạng đầu tiên.
=> Cách giải: Một khi đã nắm được quy luật, sẽ có rất nhiều cách để trình bày công thức sử dụng vòng lặp for. Ngoài ra, để tránh dài dòng khi sử dụng các mảng char hoặc vector string, có thể tạo hàm biến đổi số thành ký tự; từ đó trong mỗi vòng lặp chỉ cần thao tác xác định tọa độ và chuyển đổi thành ký tự.
N. [GCC TRAINING 2024 — PRACTICE 2] Trò chơi nối điểm
Khi mới đọc đề bài, có thể các bạn nghĩ đây là bài tập phức tạp, nhưng thực chất lại rất đơn giản.
Trước tiên, chúng ta cùng phân tích điều kiện chiến thắng trò chơi này:
Với n điểm, có thể nối tối đa n * (n – 1) / 2
đoạn thẳng.
Để tạo thành một đa giác lồi, cần tối thiểu 3 điểm.
Susan đi trước, Alice đi sau
Nếu n = 1, không thể tạo được đoạn thẳng, vì vậy Alice thắng cuộc do Susan không có lượt đi nào.
Nếu n = 2, Susan tạo một đoạn thẳng và dành chiến thắng do Alice không có lượt đi nào.
Khi n ≥ 3
: Trò chơi bắt đầu có khả năng nối các điểm thành đoạn thẳng và đa giác lồi. Tuy nhiên, để biết ai sẽ thắng, ta cần phân tích một chút về số lượt đi. Tổng số đoạn thẳng có thể nối là n * (n — 1) / 2
. Nếu số lượng này là lẻ, Susan sẽ có lượt đi cuối cùng. Nếu số lượng này là chẵn, Alice sẽ có lượt đi cuối cùng.
=> Cách xác định người thắng:
- Nếu số đoạn thẳng có thể nối là chẵn, Alice sẽ có lượt đi cuối cùng và thắng.
- Nếu số đoạn thẳng có thể nối là lẻ, Susan sẽ có lượt đi cuối cùng và thắng.
Khi đó ta xác định người thắng và in ra tên bằng cách xét phép chia dư với 4:
- n % 4 == 0: n ∗ (n−1) / 2 là chẵn → Alice thắng.
- n % 4 == 1: n ∗ (n−1) / 2 là lẻ → Susan thắng.
- n % 4 == 2: n ∗ (n−1) / 2 là lẻ → Susan thắng.
- n % 4 == 3: n ∗ (n−1) / 2 là chẵn → Alice thắng.
O. [GCC TRAINING 2024 — PRACTICE 2] Tổng cấp số nhân
Đây là một bài toán liên quan đến dãy số hình học. Tổng của dãy hình học với công bội A có thể được biểu diễn bằng công thức:
$$$S=1+A+A^2+...+A^N=\frac{A^{N+1}-1}{A-1}$$$ (Nếu A≠1)
(Nếu A = 1, dãy trở thành S = N + 1.)
Do giá trị của A và N có thể rất lớn (lên đến $$$10^9$$$), ta cần sử dụng các kỹ thuật tính toán nhanh, cụ thể là:
- Lũy thừa nhanh để tính $$$A^{N+1}$$$ mod $$$10^9+7$$$
- Nghịch đảo modulo để chia lấy dư khi cần.