B. [GCC TRAINING 2024 — MIDDLE CONTEST] Đếm tam giác
Ta nhận thấy đây là 1 đa giác đều có số đỉnh là số chẵn nên nếu ta chọn 1 điểm bất kì và kẻ 1 đường kính đi qua điểm này thì đường kính này cũng sẽ đi qua 1 điểm khác của đa giác. Do đó, ta sẽ làm như sau: - Đầu tiên, chọn 1 trong n đỉnh của đa giác này có n cách. - Tiếp theo, kẻ 1 đường kính đi qua điểm này. Để tạo thành được 1 tam giác tù thì 2 điểm còn lại mà ta chọn sẽ phải nằm ở cùng 1 phía so với đường kính ta kẻ và ta sẽ chỉ chọn các điểm ở 1 phía của đường kính này thôi do nếu chọn ở cả 2 phía thì khi đến điểm đối xứng với điểm mà ta chọn trước đó sẽ bị trùng lặp. Nhiều bạn sẽ băn khoăn rằng chọn 2 điểm ở 2 bên cũng được 1 tam giác tù mà nhưng chọn như vậy lại giống ở trên, chúng ta sẽ bị trùng lặp các hình do việc đếm mà không có quy tắc nhất định. Số cách để chọn 2 điểm trong $$$m = \dfrac{n - 2} {2}$$$ điểm còn lại ở 1 phía là $$$C_m^2$$$ cách = $$$\dfrac{m * (m - 1)} {2}$$$.
$$$\Rightarrow$$$ Vậy số tam giác tù sẽ là $$$\dfrac{n * m * (m - 1)} {2}$$$.
C. [GCC TRAINING 2024 — MIDDLE CONTEST] Happy Women's Day
- Nhập cho đến khi không nhập được nữa dùng
While(cin >> n){ }
.cin >> n
sẽ có giá trị true nếu cin đọc vào được - Bài này tư duy xuất phát từ cách vẽ hình vuông có 2 đường chéo và thêm 1 số điều kiện để vẽ được chữ M thoả mãn
- Cần lưu ý một số trường hợp n nhập vào không vẽ được hình thoả mãn như n=4,n=3,...
D. [GCC TRAINING 2024 — MIDDLE CONTEST] 3 Factors
- Ta có thể thấy được là các số duy nhất có 3 ước số là các bình phương của các số nguyên tố .
Vd: 9 có ước là { 1, 3 ,9 }
25 có ước là { 1, 5, 25 }
⇒ Từ đó có thể thấy được là yêu cầu của bài toán đang muốn ta đếm các số mà khi căn ra ta sẽ có 1 số nguyên tố trong khoảng [l, r] .
Tuy nhiên khi ta chú ý vào phần giới hạn của đề bài: 1 ≤ T ≤ 100; 1 ≤ l, r ≤ $$$10^{12}$$$. Nếu ta duyệt trâu từ l đến r thì Code của chúng ta sẽ bị TLE (Time Limit Exceed).
Giải pháp: Vì số đang tìm là bình phương của các số nguyên tố, nên ta sẽ đơn giản hóa bài toán thành “Đếm các số nguyên tố trong khoảng [ $$$\sqrt{l}$$$ , $$$\sqrt{r}$$$ ]”
Chú ý: $$$\sqrt{l}$$$ đôi khi sẽ là số thập phân nên ta sẽ phải làm tròn lên thay vì làm tròn xuống để ta sẽ không bị dính lỗi như sau:
vd: $$$\sqrt{10}$$$ = 3.1623 khi làm tròn xuống nó sẽ thành 3 mà 3 cũng là số nguyên tố nên khi đếm thì 3 cũng sẽ được tính vào kết quả, mà khoảng $$$\sqrt{l}$$$ thực của chúng ta là 3.1623 > 3. Chính vì thế ta bắt đầu đếm từ 4 để tránh lỗi này.
Hàm làm tròn lên là ceil()
.
E. [GCC TRAINING 2024 — MIDDLE CONTEST] Bibbidi-Bobbidi-Boo
Trường hợp không thể đong:
- Trường hợp không thể đong được là khi không có cách kết hợp giữa hai bao gạo để đạt được n kg. Một trường hợp đặc biệt dễ nhận thấy là:
- Nếu m chia hết cho 3 nhưng n không chia hết cho 3, thì không thể đong được vì không có cách nào sử dụng bao 3 kg để bù phần dư.
- Trường hợp này sẽ đưa ra kết quả -1.
Chiến lược tối ưu số lần đong:
- Giả sử ta có hai loại bao đong 3 kg và m kg. Ý tưởng chính là thử sử dụng bao lớn hơn (bao có trọng lượng lớn hơn giữa 3 và m) nhiều nhất có thể để đong được gần bằng hoặc đúng n kg, sau đó sử dụng bao nhỏ hơn để đong nốt phần còn lại.
- Ví dụ: Nếu bạn dùng bao lớn nhất (MAX kg), hãy tính số lần có thể dùng bao này để lấy gần nhất với n kg mà vẫn còn dư một lượng có thể đong bằng bao nhỏ hơn (MIN kg).
F. [GCC TRAINING 2024 — MIDDLE CONTEST] Mắc kẹt
- Bài này rất dễ các bạn chỉ cần hiểu đề bài rằng có tổng cộng T cánh cửa (Test Case) và 1 số H ban đầu, với mỗi Test như thế bạn chỉ cần kiểm tra xem H có lớn hơn tất cả các số có tổng các chữ số (khác 0) = n hay không. Nếu có cập nhật H — số số thoả mãn + k, nếu không thoát khỏi vòng lặp.
- Nếu muốn biết số số thoả mãn điều kiện thì hãy thử nháp hoặc xem code.