Phân tập

View as PDF
Submit solution
Points: 0.31 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~N~ người ~\left(2 \leq N \leq 32\right)~, mỗi người có một số ~a_{i}~ ~\left(1 \leq a_i \leq 10^9\right)~ được gọi là độ tin cậy.

Cần phân chia ~n~ người này vào ~2~ tập sao cho:

  • Mỗi người thuộc đúng một tập.
  • Chênh lệch tổng độ tin cậy của ~2~ phần là bé nhất.

Input

Dòng đầu chứa số nguyên ~N~.

Dòng tiếp theo chứa ~N~ số: số thứ ~i~ là độ tin cậy của người thứ ~i~.

Output

Ghi ra hai số ~u~ và ~v~ với ~u~ là độ chênh lệch nhỏ nhất và ~v~ là số cách phân chia

Sample Input

5
1 5 6 7 8

Sample Output

1 3

Note

Độ chênh lệch ít nhất của ~2~ phần là ~1~.

Có ~3~ cách phân chia nhóm ~1~ là ~(3,5)~, ~(1,3,4)~ và ~(1,2,5)~

Comments

Please read the guidelines before commenting.


  • -16
    Articulation_points  commented on Sept. 29, 2024, 6:38 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 2
    trieuyanglake_1  commented on April 11, 2023, 7:08 a.m.

    dạ mình có code thử bài này bằng bitmask mà sai ở test 21 không biết sai ở đâu mong mọi người chỉ , cảm ơn ạ https://ideone.com/TiDPD5