Going Once, Going Twice, Gone!

View as PDF

Submit solution


Points: 0.08 (partial)
Time limit: 0.38s
Memory limit: 512M

Problem source:
USACO November 2008
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Chế độ ăn kiêng của đàn bò khiến cho nông trang của nông dân John dôi ra ~1~ số lượng cỏ khô, vì vậy anh ta muốn bán đấu giá số cỏ khô này để trang trải phần nào chi phí chăn nuôi. Anh ta có ~N~ ~(1 \le N \le 1000)~ bó cỏ khô giống nhau; những khách hàng sẽ đấu giá để mua đống cỏ này là ~M~ ~(1 \le M \le 1000)~ nông dân khác sống gần đó.

Mỗi một nông dân ~i~ sẽ cho nông dân John biết anh ta sẵn sàng trả ~P_i~ ~(1 \le P_i \le 1000000)~ đồng cho ~1~ bó cỏ khô. Mỗi một nông dân chỉ muốn mua ~1~ bó cỏ khô mà thôi.

Để đảm bảo các nông dân không ghen tị với nhau, nông dân John sẽ đưa ra ~1~ mức giá cố định cho tất cả người đến mua và bán các bó cỏ khô cho những ai trả giá lớn hơn hoặc bằng mức giá đó, những người còn lại sẽ bị từ chối giao dịch.

Hãy giúp nông dân John tính xem đặt mức giá nhỏ nhất là bao nhiêu để thu được nhiều tiền nhất có thể.

Input

  • Dòng ~1~: Hai số nguyên cách nhau bởi dấu cách: ~N~ và ~M~
  • Dòng ~2~...~M+1~: Dòng ~i+1~ chứa 1 số nguyên duy nhất: ~P_i~

Output

~1~ dòng duy nhất chứa ~2~ số nguyên cách nhau bởi dấu cách: giá bán của John và số tiền mà John thu được.

Sample Input

5 4
2
8
10
7

Sample Output

7 21

Comments

Please read the guidelines before commenting.



  • -1
    hoangthanh2406  commented on 5, Nov, 2021, 9:04

    ai co test bai nay ko cho xin voi


  • 2
    CODING  commented on 21, Aug, 2021, 13:48

    mn tham khảo ạ: https://www.youtube.com/watch?v=KAHzmJIlspE


  • -2
    codernhi  commented on 12, Aug, 2021, 9:43

    mình chưa hiểu rõ về cái sample output của bài này lắm, với số tiền thu được là 21 thì làm sao có thể tạo được từ 2,8,10,7 ?


    • 6
      T_Q_Khang  commented on 12, Aug, 2021, 13:28 edit 2

      7 x 3 = 21 hay 7 + 7 + 7 = 21 đó bạn.

      Nói rõ hơn thì sẽ lấy số 8, 10, 7. Với giá 7 thì bạn sẽ được như trên. Nếu bạn lấy 6 thì ta có 18 hay lấy 8 thì là 16,... Nên ta xem xét lấy TH tối ưu nhất theo đề bài.