Vừa xem lại rating trên Codechef mới phát hiện NOV19B bị đánh dấu đạo bài, trong khi mình vắt óc làm mới AC được có 2 bài, đã khiếu nại mà không biết có được giải quyết hay không. Nhưng có một điều mình sure kèo là mới bị đánh đạo bài gần đây, vì NOV19B diễn ra hồi tháng 11 năm ngoài mà lần cuối cùng mình vào Codechef là August Challenge đầu tháng 8 thì kết quả NOV19B của mình vẫn chưa bị gì.
Chả hiểu làm ăn kiểu gì vậy nữa, công sức người ta làm như thế mà đánh đạo bài như thật huhu.
Tóm tắt đề bài: Cho mảng A gồm N số nguyên. Đếm xem số lần xuất hiện (tần số) của mỗi số A[i], sau đó dựa vào tần số của các tần số đó mà tìm ra tần số xuất hiện nhiều nhất.
Dẫn lại nguyên đề bài: với mỗi v mà tồn tại ít nhất một chỉ số i sao cho A[i] = v, đếm số lượng chỉ số j thỏa mãn A[j] = v và gọi số lượng chỉ số đó là tần số của v, ký hiệu là freq(v). Khi đó, tìm giá trị w sao cho freq(v) = w với hầu hết v được xét trong bước trên. Nếu có nhiều giá trị w thì đưa ra giá trị nhỏ nhất.
Hướng giải: đếm tần số thì dùng map, thêm 1 map nữa đếm tần số của các tần số sau đó đưa ra kết quả.
Tóm tắt đề bài: Cho dải băng A dài N ô được đánh dấu từ 1 tới N. Với 1 <= i <= N, A[i] = 1 thì ô thứ i bị khóa và A[i] = 0 thì ô thứ i được mở. Ở lượt đầu của mỗi người, người chơi được nhảy tới bất kỳ ô nào đang mở. Các lượt sau đó người chơi đang đứng tại ô c chỉ nhảy được đến ô c - 1 hoặc c + 1, với điều kiện ô đó được mở, sau đó ô c sẽ bị khóa. Trò chơi kết thúc khi người chơi không nhảy được bước nào nữa. Biết rằng Nayeon chơi lượt đầu và cả 2 chơi tối ưu, tìm xem liệu Nayeon có thắng được Tzuyu hay không.
Hướng giải: Người chơi chỉ có thể đi được 1 trong 2 ô c + 1 và c - 1, nghĩa là người chơi nếu di chuyển chi di chuyển được 1 hướng duy nhất sau khi đi bước đầu và chọn hướng đầu tiên.
"Cách chơi tối ưu" là người chơi đầu tiên sẽ chọn dãy ô chưa mở dài nhất, gọi độ dài dãy này là l, sau đó bắt đầu ở ô giữa của dãy này (vì nếu bắt đầu ở 1 trong 2 ô sát biên thì sẽ thua ngay lập tức nếu người kia đi ô kế bên). Khi đó người đi thứ 2 chỉ có l / 2 (làm tròn dưới) ô để đi. Nếu l chẵn thì người chơi đầu tiên sẽ thua, l lẻ thì người đầu tiên sẽ thắng.
Nhưng đó chỉ là trường hợp nếu chỉ có 1 dãy ô trống - 50 điểm. Nếu có từ 2 dãy trở lên, ta phải xét trường hợp tồn tại 1 dãy thứ 2 có độ dài lớn hơn 1/2 độ dài dãy 1, tức là nếu người chơi thứ 1 đi ở ô giữa dãy 1 thì người chơi thứ 2 bắt đầu ở biên dãy 2, khi đó người chơi 1 chỉ đi được 1/2 dãy 1 và người chơi 2 đi được cả dãy 2 và người chơi 2 thắng. Vì vậy ta phải xét trường hợp này: tồn tại dãy 2 dài hơn 1/2 dãy 1 thì người chơi đầu tiên thua, còn lại người chơi đầu tiên thắng.
No comments:
Post a Comment