Educational Codeforces Round 96 (Rated for Div. 2) - Problem A & B

Như mọi lần trước, vẫn làm nhiều nhưng vẫn ngu.

A - Number of Apartments.

Tóm tắt đề bài: Cho số nguyên n, hãy tìm bộ ba i, j, k sao cho 3i + 5j + 7k = n. Nếu không có bộ ba phù hợp, in ra -1. 

Ràng buộc 1 ≤ n ≤ 1000

Hướng dẫn giải: Naive method O(n³) AC tốt nếu như đặt điều kiện dừng đúng cách. Một cách làm khác (thần kinh hơn và không khuyến khích thử, nhưng vẫn AC) là dựng một sàng O(n³) lưu các bộ i, j, k có thể (và duy nhất) cho mỗi giá trị n trong đoạn [1, 1000]; khi đó kết quả cho mỗi truy vấn là O(1).

Code mẫu (C++).

B -  Barrels.

Tóm tắt đề bài: Bạn có N cái thùng, cái thùng thứ i chứa A[i] lít nước. Trong một thao tác, bạn có thể chọn hai thùng x và y (x ≠ y) rồi đổ nước từ thùng x vào y hoặc ngược lại. Giả sử các thùng không giới hạn sức chứa và bạn có thể đổ nước từ thùng x vào thùng y cho đến khi thùng x rỗng. Với k thao tác, hãy tính thể tích nước chênh lệch tối đa giữa thùng nhiều nước nhất và thùng ít nước nhất.

Hướng dẫn giải: Chênh lệch thể tích lớn nhất xảy ra khi ta so sánh lượng nước trong thùng nhiều nước nhất với một thùng rỗng. Nếu ta đổ nước từ thùng nhiều nước nhất vào thùng nhiều nước 2nd thì sẽ được một thùng rỗng và thùng kia chứa nhiều nước nhất, khi đó chênh lệch giữa hai thùng sẽ là cao nhất trong tất cả các cặp thùng. Lặp đi lặp lại đến hết k bước thì chênh lệch sẽ đạt tối đa. 

tl;dr: Algoritham - lấy k + 1 thùng nhiều nước nhất cộng nhau là ra kết quả.

Code mẫu (C++).

Happy coding!