Editorial for Nâng cấp tuyến đường

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: Yunan

Với $N=16$ ~N=16~, ta tiến hành chọn các cạnh như sau:

Chọn cạnh nối đỉnh $1$ ~1~ và một đỉnh khác $($ ~(~từ đỉnh $2$ ~2~ đến đỉnh $16$ ~16~ $)$ ~)~: có tổng cộng $15$ ~15~ cách chọn.
Chọn cạnh nối đỉnh $a$ ~a~ $($ ~(~đỉnh $a$ ~a~ chưa được chọn $)$ ~)~ và một đỉnh khác $($ ~(~còn lại $13$ ~13~ đỉnh $)$ ~)~: có tổng cộng $13$ ~13~ cách chọn.
Chọn cạnh nối đỉnh $b$ ~b~ $($ ~(~đỉnh $b$ ~b~ chưa được chọn $)$ ~)~ và một đỉnh khác $($ ~(~còn lại $11$ ~11~ đỉnh $)$ ~)~: có tổng cộng $11$ ~11~ cách chọn
$...$ ~...~

Với cách chọn như trên, có tổng cộng tối đa $15 \times 13 \times 11 \times 9 \times 7 \times 5 \times 3 \times 1=2027025$ cách chọn. Vì vậy, có thể giải quyết bài toán này bằng cách kiểm tra tất cả $2027025$ ~2027025~ cách chọn trên. Lưu ý đối với hai trường hợp $N$ ~N~ chẵn $($ ~(~tất cả đỉnh đều được chọn $)$ ~)~ và $N$ ~N~ lẻ $($ ~(~có một đỉnh không được chọn $)$ ~)~.

Editorial for Nâng cấp tuyến đường

Comments