Editorial for Bedao PROM Hay Không? Hay Hay
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ý tưởng:
Gọi ~X~ là số lượng bạn nam, ~Y~ là số lượng bạn nữ
Gọi ~A~ là số lượng bạn nữ mà một bạn nam sẽ khiêu vũ, ~B~ là số lượng bạn nam mà một bạn nữ sẽ khiêu vũ.
Trong buổi khiêu vũ, một bạn nam có thể nhảy với bạn nữ thứ ~1~,rồi chuyển qua nhảy với bạn nữ thứ ~2~, ..., bạn nữ thứ ~Y~. Thực hiện tương tự như thế với một bạn nữ, từ đó ta có thể tưởng tượng một đồ thị hai phía có tổng cộng ~N~ đỉnh gồm ~X~ đỉnh bên trái và ~Y~ đỉnh bên phải. Ta lại có ~A \times X~ cạnh hay tương tự ta cũng có ~B \times Y~ cạnh. Vậy ta có hệ phương trình:
~X + Y = N~
~A \times X - B \times Y = 0~
Từ đây ta có thể giải ~X~ và ~Y~ bằng phương pháp cộng hoặc phương pháp thế khi giải hệ phương trình.
Comments