Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#1112 · Trò chơi thẻ bài

MÔ TẢ BÀI TOÁN

Bảo Bay Bổng vừa nghĩ ra một trò chơi mới dành cho k bạn nhỏ ở một ngôi trường nọ.

Cậu đặt n tấm thẻ lên bàn, trên tấm thẻ thứ i có ghi số a_i. Mặt có ghi số của các tấm thẻ được đặt úp xuống mặt bàn.

Mỗi lượt chơi, Bảo gọi một bạn nhỏ chưa từng được chơi lượt nào trước đó lên rút ra hai tấm thẻ bất kì mà bạn nhỏ muốn. Sau khi chọn xong bạn nhỏ sẽ để tấm thẻ có ghi số lớn hơn lại trên bàn (bạn lên sau không biết được tấm thẻ mà bạn lên trước chọn) và mang tấm thẻ có giá trị nhỏ hơn về cho mình. Nếu hai tấm thẻ mà bạn nhỏ chọn có ghi hai số bằng nhau, bạn nhỏ có thể lựa chọn mang về một tấm thẻ bất kì trong hai tấm thẻ đó.

Đặt S là tổng các số ghi trên k tấm thẻ mà các bạn nhỏ mang về. Hãy cho biết S có thể đạt giá trị nhỏ nhất và lớn nhất là bao nhiêu.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên dương $n, k (1 \leq k < n \leq 10^5)$.
  • Dòng thứ hai chứa n số nguyên dương a_1, a_2,..., a_n (1 \leq a_i \leq 10^9)

Dữ liệu ra

In ra hai số nguyên dương cách nhau bởi một dấu cách là giá trị S nhỏ nhất và lớn nhất có thể đạt được.

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
T
Nguyễn Tri Bão Thắng @2180601452
11 ms 2040 KB
5868 Bytes
15/01/2023
18:08
2
C
Nguyễn Xuân Chung @2016019
24 ms 1048 KB
359 Bytes
04/04/2023
15:22
3
A
Nguyễn Thuận An @1911256118
25 ms 1056 KB
553 Bytes
26/03/2023
12:42
4
L
Phạm Khắc Duy Long @2280610603
28 ms 1056 KB
516 Bytes
04/12/2022
14:39
5
T
Nguyễn Tri Bão Thắng @2180601452
29 ms 1064 KB
1437 Bytes
05/12/2022
10:18
6
X
Lê Dương Định Xuân @2280618826
30 ms 680 KB
3596 Bytes
22/11/2023
22:25
7
B
Trần Gia Bảo @2380600172
30 ms 692 KB
434 Bytes
25/11/2023
13:20
8
L
Mai Dương Long @2380601236
30 ms 692 KB
583 Bytes
15/06/2024
06:31
9
T
Nguyễn Thăng Tiến @2180608641
30 ms 1052 KB
494 Bytes
19/06/2023
11:12
10
H
Clb Olympic Tin Học Hutech @olympictinhoc
31 ms 676 KB
434 Bytes
04/12/2022
13:53
11
N
Nguyễn Văn Nguyên @2180606793
31 ms 1052 KB
453 Bytes
27/12/2022
22:15
12
T
Nguyễn Thăng Tiến @2180608641
32 ms 1056 KB
494 Bytes
19/06/2023
11:09
13
T
Nguyễn Thăng Tiến @2180608641
32 ms 1060 KB
494 Bytes
19/06/2023
11:09
14
T
Nguyễn Thăng Tiến @2180608641
32 ms 1064 KB
494 Bytes
19/06/2023
11:10
15
Trần Tuấn Anh @2280600132
33 ms 1472 KB
460 Bytes
04/02/2024
22:58
16
B
Nguyễn Hữu Ngự Bình @2280600266
34 ms 1084 KB
438 Bytes
03/04/2024
10:09
17
Lê Duy Hải @2280600799
35 ms 984 KB
1579 Bytes
21/07/2023
23:45
18
Lê Duy Hải @2280600799
36 ms 980 KB
1063 Bytes
21/07/2023
23:49
19
T
Dương Ngọc Trâm @2080601170
37 ms 1056 KB
482 Bytes
08/03/2023
17:38
20
Q
Nguyễn Phan Hoàng Quân @2280602604
39 ms 1084 KB
660 Bytes
21/01/2025
00:04

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

Trong trường hợp xấu nhất:

  • Bạn thứ nhất bốc tấm thẻ thứ 1 và 2, mang tấm thứ 1 về và để lại tấm thứ 2.
  • Bạn thứ hai bốc tấm thẻ thứ 2 và 3, mang tấm thứ 2 về và để lại tấm thứ 3.
  • Bạn thứ ba bốc tấm thẻ thứ 3 và 4, mang tấm thứ 3 về và để lại tấm thứ 4.

Tổng các số trên các tấm thẻ của các bạn nhận được: 1 + 2 + 3 = 6.

Trong trường hợp tốt nhất:

  • Bạn thứ nhất bốc tấm thẻ thứ 2 và 3, mang tấm thứ 2 về và để lại tấm thứ 3.
  • Bạn thứ hai bốc tấm thẻ thứ 3 và 4, mang tấm thứ 3 về và để lại tấm thứ 4.
  • Bạn thứ ba bốc tấm thẻ thứ 4 và 5, mang tấm thứ 4 về và để lại tấm thứ 5.

Tổng các số trên các tấm thẻ của các bạn nhận được: 2 + 3 + 4 = 9.

Viết code