Codeforces Round #673 (Div. 2) & Codeforces Round #674 (Div. 3)

Đây là 2 bài trong 2 contest khác nhau, gom lại 1 post cho nó đỡ ngắn.

A (#673). Copy-paste

Tóm tắt: Có n ống kẹo, mỗi ống có a[i] viên kẹo. Mỗi hành động copy-paste có thể được định nghĩa như sau:

• Chọn hai ống kẹo i, j sao cho 1 ≤ i, j ≤ n và i ≠ j
• Tất cả kẹo từ ống i được copy sang ống j (i.e a[j] = a[i] + a[j]).

Bạn có thể copy-paste bao nhiêu lần tùy thích, tuy nhiên nếu một trong các ống kẹo có nhiều hơn (>) k viên kẹo thì bạn không thể thực hiện hành động copy-paste nữa. Tính xem bạn có thể thực hiện copy-paste tối đa bao nhiêu lần?

Hướng dẫn: Algoritham. 

Ta nhận xét rằng số lần thực hiện nhiều nhất chỉ xảy ra khi ta dùng kẹo trong ống chứa ít kẹo nhất đổ vào các ống khác. Do đó dùng phương pháp tham lam (Algoritham) để giải quyết là hợp lý.

Code mẫu (C++).

A (#674). Floor Number.

Tóm tắt: Petya ở trong một căn chung cư đặc biệt: tầng 1 chỉ có 2 phòng; các tầng khác mỗi tầng có x căn hộ và các căn hộ được đánh số từ 1. Hôm nay Vasiya đến thăm Petya, biết rằng căn hộ của Petya được đánh số n (và giả sử căn chung cư đủ cao để có ít nhất n căn hộ), hãy tìm xem Petya đang ở tầng nào nhé?

Giới hạn (1 ≤ n, x ≤ 1000)

Hướng dẫn: 

Do n ≤ 1000 nên duyệt 1 vòng lặp dư sức AC. 

Với phương pháp O(1): ta dễ dàng nhận thấy nếu n ≤ 2 thì Petya ở tầng 1, còn lại ta có thể áp dụng công thức ((n - 3) / x) + 2, với (n - 3) / x làm tròn dưới.

Code mẫu (C++).

Happy coding!