Đăng file Zip lên GitHub có lẽ là một ý tưởng tệ vô cùng :( Thôi thì quay trở lại viết lách trên blog vậy.
 |
| Phải đăng cái hình này để phân biệt mấy bài contest, bài này nhiều hình nên dễ bị sai thumbnail |
Bài viết lần này sẽ là về Long Challenge tháng 2. Lần này solve được 3 bài, code nhấn mạnh là rất xấu, tuy nhiên editorial của 3 bài này lại cùng phương pháp với mình. Nhấn mạnh là code lần này rất xấu nên cân nhắc kỹ trước khi copy hay cố gắng hiểu code các bạn nhé?
Đề bài yêu cầu tìm giá trị lớn nhất có thể của tổng đường kính N hình tròn. Bài này giải bằng cách sort lần lượt các dãy A và B từ lớn tới nhỏ, khi đó mỗi cặp A[i] và B[i] là 2 cạnh của 1 hình chữ nhật. Tính tổng đường kính các hình chữ nhật đó sẽ được đáp án theo đề bài.
Notes:
- Chú ý điều kiện ràng buộc A[i], B[i] <= 10^9 và N <= 10^4. Trường hợp tệ nhất là 10^4 * 10^9 = 10^13 => phải dùng kiểu dữ liệu long long trong C/C++ hay int_64 trong Pascal.
- Đường kính hình tròn nội tiếp hình chữ nhật tạo bởi cặp A[i] và B[i] bằng độ dài cạnh nhỏ hơn trong cặp A[i] và B[i]. Bạn có thể vẽ hình để kiểm chứng.
Đề bài yêu cầu phân phối các đồng xu theo chiều từ trái qua phải, sao cho số xu của mỗi túi (sau khi phân phối) chia hết cho K và số xu còn dư ra là nhỏ nhất có thể. Từ đây ta có thể suy ra tư tưởng chia xu: chia nhiều nhất có thể để số xu của một túi trở thành bội của K và lấy ít nhất có thể để số xu của một túi trở thành bội của K. Nếu số xu túi đó đã là bội của K thì không lấy cũng không thêm.
Nói ra nghe có vẻ khó, nhưng trong thực tế cài đặt giải thuật khá dễ. Ta gọi S là số xu dư ra, mỗi lần bỏ thêm xu vào một túi ta sẽ lấy xu từ S, mỗi lần lấy xu từ một túi ta sẽ bỏ vào S. Để bỏ xu vào một túi, ta cộng S với số xu hiện tại của túi đó rồi chia lấy dư cho K - phần dư sẽ là phần xu còn lại của S sau khi bỏ số xu cần thiết để số xu trong túi đó chia hết cho K.
Cụ thể ta lấy test mẫu số 2 làm ví dụ:
3 9
1 10 19
Ban đầu S = 0.
- Bước 1: (S + số xu túi 1) mod 9 = (1 + 0) mod 9 = 1. S = 1
- Bước 2: (S + số xu túi 2) mod 9 = (1 + 10) mod 9 = 2. S = 2.
- Bước 3: (S + số xu túi 3) mod 9 = (2 + 19) mod 9 = 3. S = 3. Đây cũng là kết quả.
Đề bài yêu cầu chọn thởi điểm phát phim, sao cho mỗi giờ chỉ chiếu 1 bộ phim và doanh thu đạt được cao nhất. Nếu bạn để ý kỹ thì N <= 100 => brute force được.
Tổng kết: Contest lần này ăn 300 điểm, nhưng gánh mình lên 3* là Cook-off. Nhưng cũng phải bổ sung quả ảnh ăn mừng lên 3* :D
Do đây là lần đầu cháu nó lên rank nên các bạn thông cảm, cảm ơn các bạn nhiều.
 |
| 3* nè he |
 |
| biểu đồ nè he |
 |
| biểu đồ cột nè he |
Năm mới vui vẻ, Happy coding!
No comments:
Post a Comment