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$ $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