Wednesday 19 August 2020

Codechef August Challenge 2020 - Division 2


> Finished finals
> Go home
> gatheredfamily.png
> Sleep
> Wake up
> 3rd day at the dorm, 1 week to go
I'm suffering from the finals right now anons.

Chef Wars - Return of the Jedi

Tóm tắt: Bạn đang đánh một con quái có lượng máu là H, sức mạnh của bạn (damage) hiện tại là P. Sau mỗi cú đánh, máu của con quái giảm xuống H - P và sức mạnh của bạn giảm xuống một nửa đến khi 1 trong 2 - máu của con quái hoặc sức mạnh của bạn - bằng 0. Xác định xem bạn có đánh chết được con quái sau một số lần đánh nhất định hay không.

Hướng dẫn: Chỉ cần sức mạnh của bạn > H / 2 là bạn có thể xiên chết cụ con quái này.

Link code mẫu (C++).

Chef and Linear Chess

Tóm tắt: Chef đang chơi cờ với N người bạn trên một bàn cờ kích thước 1 ×  (bàn cờ chỉ có 1 dòng duy nhất và dòng này dài đến vô cùng). Ban đầu, quân cờ của Chef đang ở ô thứ K và sẽ đứng yên cho đến cuối trò chơi. Bạn của Chef, người thứ Pi (1 ≤ i ≤ N), sẽ đặt quân cờ của họ lên ô Pi và di chuyển nó một khoảng Pi ô. Ví dụ, người thứ Pi  = 3 sẽ đặt quân cờ của họ lên ô thứ 3, sau đó di chuyển đến ô thứ 6, 9, 12, .. Xác định xem quân cờ của Chef có bị người nào ăn mất không, nếu có thì xuất ra người có số bước đi ít nhất để ăn được quân cờ của Chef, nếu không xuất ra -1.

Hướng dẫn: Duyệt tìm các ước số của K trong P. Nếu không có ước số nào của K trong P, xuất ra -1. Ngược lại, xuất ra giá trị lớn nhất của các ước số đó. Code mẫu có sử dụng std::map để tìm giá trị lớn nhất.

Link code mẫu (C++).

Another Card Game Problem

Tóm tắt: Chef và Rick đang chơi với nhau một trò chơi: mỗi người chọn cho mình một số nguyên Pc và Pr. Xem mỗi số nguyên đó là tổng các chữ số của một số nguyên N nào đó, e.g 18 là tổng chữ số của 99, 909, 990,... và N ít chữ số nhất thì người đó chiến thắng, nếu số lượng chữ số bằng nhau thì Rick ăn gian và thắng. Giả sử 2 người này chơi tối ưu nhất có thể, i.e số N của mỗi người sẽ ít chữ số nhất có thể, tìm xem ai là người thắng.

Hướng dẫn: Phương pháp tham lam. Phân tích Pc thành 9x + n, khi đó số lượng chữ số nhỏ nhất cần dùng để tổng của các chữ số bằng P là Nc = x + 1 (nếu n ≠ 0) hoặc x (nếu n = 0). Tính toán tương tự với Pr thu được Nr, so sánh Nc và Nr rồi đưa ra kết quả.

Link code mẫu (C++).

No comments:

Post a Comment

Popular posts