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.

Author: ntkwan

Ý 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

Please read the guidelines before commenting.


There are no comments at the moment.