Người ta đâu tính thời gian đâu mà sợ :)
Kiên thì cứ đợi sau khoảng 1 giờ cho bình tĩnh lại là sẽ như lên đồng
Đảm bảo Việt Nam sẽ có người 2 bài 100 điểm
Solution bài 1:
Nếu không hiểu lầm đề thì ta sẽ lấy (số khu vực có đội div số quà có thể lấy mỗi lần)*số khu vực+thời gian phát quà tối ưu cho các đội còn lại
Phần đầu dễ rồi, phần "thời gian phát quà tối ưu cho các đội còn lại" chắc phải xét khoảng 4 trường hợp thôi
Độ phức tạp ước tính là \(O(n)\)
Có vẻ dễ, chạy test ví dụ đúng rồi :)
À nhầm, mỗi khu vực lại có nhiều đội thì ta chia hình tròn làm nửa hình tròn, phát quà cho mỗi nửa hình tròn, sau đó phát quà cho lần lượt cho nửa hình tròn nên độ phức tạp sẽ khoảng tầm \(O(n^{2})\), với \(n \leq 10^{7}\) không biết có qua không nhỉ
Đề bài có hình minh họa gây nhiễu, thuật toán không ra đường đi như đề bài nhưng vẫn là tối ưu!
Solution bài 2:
Bài này cũng chày cối chia nhiều trường hợp, nói chung chỉ cần biện luận và giải được bài toán cho 6 đồng xu đánh số từ 1 đến 6, trong đó có một đồng xu giả, dùng cân Rô-béc-van để tìm ra đồng xu giả trong hai lần cân (đề bài có các hàm trả ra kết quả cân)
Độ phức tạp từ \(O(1)\) (code dài) đến \(O(n)\) (code thông minh)
Bài này dân Tổng hợp chắc làm vô cùng tốt rồi
Bài 3 liên quan đến đồ thị hai phía thì phải, cái này mình chưa học :(
