Bedao Regular Contest 17 - Candy game - VNOJ: VNOI Online Judge

Bedao Regular Contest 17 - Candy game

Điểm: 0,40 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nhân dịp trung thu, các bạn tình nguyên viên Bedao được thưởng một thùng toàn là kẹo. Vì em bé FireGhost và TrungNotChung nhỏ nhất nên được ưu tiên lấy kẹo trước. Thùng kẹo có $k$ viên kẹo nhưng không em nào nhường em nào. Hai em đã nghĩ ra trò chơi như sau:

Cho một dãy có $n$ phần tử, phần tử thứ $i$ có giá trị $1 \leq a_{i} \leq k$ . Mỗi lượt một trong hai em sẽ chọn ra một số nguyên $a_{i}$ trong dãy, có giá trị không vượt quá số lượng kẹo còn lại, và bốc ra khỏi thùng kẹo $a_{i}$ viên. Các giá trị $a_{i}$ có thể được dùng nhiều lần. Trò chơi dừng lại khi không thể bốc được thêm.

Hai em chơi luân phiên theo lượt, FireGhost chơi trước, hãy tìm lượng kẹo nhiều nhất FireGhost có thể bốc được, nếu như cả hai em cùng chơi tối ưu nhé.

Input

Dòng đầu chứa hai số nguyên dương $k, n$ $(1 \leq n \leq 100, 1 \leq k \leq 10^{5})$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_{i}$ $(1 \leq a_{i} \leq k)$ mô tả dãy $a$ .
Dữ liệu đảm bảo $a_{1} = 1$ .

Output

Gồm một số nguyên duy nhất là lượng kẹo nhiều nhất FireGhost có thể bốc được, nếu như hai em cùng chơi tối ưu.

Sample Input 1

Copy

10 3
1 3 4

Sample Output 1

Copy

Notes

Tại lượt đầu tiên, FireGhost bốc ra khỏi thùng kẹo $3$ viên.

Nếu TrungNotChung bốc ra $4$ viên thì FireGhost bốc ra $3$ viên, TrungNotChung kết thúc trò chơi với $4$ viên kẹo.
Nếu TrungNotChung bốc ra $3$ viên thì FireGhost bốc ra $4$ viên, TrungNotChung kết thúc trò chơi với $3$ viên kẹo.
Nếu TrungNotChung bốc ra $1$ viên thì FireGhost bốc ra $4$ viên. Khi đó, lượng kẹo còn lại là $2$ viên nên TrungNotChung sẽ kết thúc trò chơi với nhiều nhất là $3$ viên kẹo.

TrungNotChung chơi tối ưu nên sẽ bốc ra $4$ viên kẹo và FireGhost bốc ra $3$ viên kẹo còn lại.

Vậy FireGhost kết thúc trò chơi với $6$ viên kẹo. Có thể chứng minh đây là lượng kẹo nhiều nhất FireGhost nhận được nếu cả hai bạn chơi tối ưu.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-5

tuoitre đã bình luận 7:46:50 sa, 15/10/2023

có ai thuật tham lam mà ac ko ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-2

khanhphamlc đã bình luận 1:50:30 sa, 31/10/2023

co 96 thoi :(