# Bài tập về nhà : Sắp xếp trong Python

## **Lưu ý cho phần bài tập:**

1. **Dành thời gian suy nghĩ**:
- Dành ít nhất **10 phút** để tự tìm cách làm cho mỗi bài trước khi đọc hướng dẫn.

2. **Phương pháp khi đọc hướng dẫn**:
- **Bước 1**: Đọc phần **Tóm tắt đề** và suy nghĩ để làm bài trong 10 phút.
- **Bước 2**: Nếu chưa giải được, đọc tiếp phần **Hướng làm bài** và suy nghĩ thêm 10 phút.
- **Bước 3**: Nếu vẫn chưa giải được, đọc phần **Thuật toán** và suy nghĩ thêm 10 phút.
- **Bước 4**: Cuối cùng, dành 5-10 phút để đọc phần **Code lời giải** và hiểu từng dòng code.

---

## [Luyện tập](https://lqdoj.edu.vn/problem/practice)

### **Tóm tắt đề bài:**

Bạn được cung cấp một danh sách các bài tập với yêu cầu về kỹ năng tối thiểu và mức tăng kỹ năng sau khi giải mỗi bài. Ban đầu, bạn có một mức kỹ năng nhất định. Nhiệm vụ của bạn là xác định số lượng bài tập tối đa có thể giải được theo bất kỳ thứ tự nào, với mục tiêu tăng kỹ năng để có thể giải được càng nhiều bài tập càng tốt.

- **Input:**
- Dòng đầu tiên chứa hai số nguyên `n` (số lượng bài tập) và `c` (trình độ kỹ năng ban đầu).
- Tiếp theo là `n` dòng, mỗi dòng chứa hai số nguyên `a_i` (kỹ năng tối thiểu để giải bài `i`) và `b_i` (mức tăng kỹ năng sau khi giải bài `i`).

- **Output:**
- Một số nguyên là số lượng bài tối đa có thể được giải.

### **Ví dụ:**

- **Input:**

  4 1
  1 10
  21 5
  1 10
  100 100

- **Output:**

  3

- **Giải thích:**
- Bắt đầu với kỹ năng `c = 1`.
- Giải bài 1, tăng kỹ năng lên `11`.
- Giải bài 3, tăng kỹ năng lên `21`.
- Giải bài 2, tăng kỹ năng lên `26`.
- Không đủ kỹ năng để giải bài 4, nên giải được tổng cộng 3 bài.

### **Phân tích bài toán**

Bài toán yêu cầu xác định số lượng bài tập tối đa mà bạn có thể giải được, dựa trên trình độ kỹ năng ban đầu `c` và danh sách các bài tập với yêu cầu kỹ năng tối thiểu và mức tăng kỹ năng sau khi giải mỗi bài.

#### **Ý tưởng giải bài:**
- Bạn sẽ bắt đầu với một kỹ năng ban đầu `c`.
- Mỗi bài tập có yêu cầu kỹ năng tối thiểu `a_i` và khi giải xong, kỹ năng của bạn sẽ tăng thêm `b_i`.
- Bạn có thể làm các bài theo bất kỳ thứ tự nào, nên ý tưởng là:
- Sắp xếp các bài tập theo yêu cầu kỹ năng `a_i`.
- Sau đó, duyệt qua các bài tập và nếu kỹ năng hiện tại của bạn đủ để giải được bài (tức là `c >= a_i`), thì giải bài đó và tăng kỹ năng lên.
---
### **Cách làm chi tiết:**

1. **Nhập dữ liệu:** Đầu tiên, ta sẽ nhập số lượng bài tập `n` và trình độ kỹ năng ban đầu `c`. Sau đó nhập lần lượt các bài tập vào
3. **Sắp xếp các bài tập:** Sắp xếp các bài tập theo yêu cầu kỹ năng `a_i` tăng dần để đảm bảo bạn sẽ giải các bài dễ trước, qua đó tăng kỹ năng để có thể giải các bài khó hơn.
4. **Duyệt qua các bài tập:** Bắt đầu từ bài dễ nhất, nếu kỹ năng của bạn đủ để giải, thì tăng kỹ năng và tiếp tục giải bài tiếp theo.
5. **Đếm số lượng bài giải được:** Mỗi lần bạn giải được bài nào thì tăng biến đếm.

### **Code lời giải:**

# Hãy hoàn thiện chương trình sau bằng 
# cách điền vào dấu 3 chấm thích hợp.

# Nhập dữ liệu đầu vào
n, c = map(int, input().split())
exercises = []

# Nhập các bài tập với yêu cầu kỹ năng và kỹ năng tăng thêm
for _ in range(n):
    a, b = map(int, input().split())
    exercises.append((a, b))

# Sắp xếp các bài tập theo yêu cầu kỹ năng tối thiểu
...

# Biến đếm số lượng bài giải được
count = 0

# Duyệt qua từng bài tập
for a, b in exercises:
    # 'a' là kỹ năng cần để giải bài
    # 'b' là trình độ tăng lên sau khi giải bài
    if ...:  # Nếu kỹ năng hiện tại đủ để giải bài
        c += ...  # Tăng kỹ năng sau khi giải bài
        ...  # Tăng biến đếm

# In ra số lượng bài tối đa có thể giải được
...

### **Giải thích code:**

- **Dữ liệu đầu vào:** `n` là số lượng bài tập, `c` là trình độ kỹ năng ban đầu. Mỗi bài tập có yêu cầu kỹ năng tối thiểu `a_i` và sau khi giải sẽ tăng kỹ năng `b_i`.

- **Sắp xếp:** Các bài tập được sắp xếp theo yêu cầu kỹ năng tối thiểu `a_i`. Điều này giúp bạn giải các bài dễ trước để có thể tăng kỹ năng, sau đó mới giải các bài khó hơn.

- **Duyệt qua các bài tập:** Với mỗi bài tập, kiểm tra xem kỹ năng hiện tại có đủ để giải không (`c >= a_i`). Nếu đủ thì giải và tăng kỹ năng.

- **Kết quả:** In ra số lượng bài tập tối đa mà bạn có thể giải được.

### **Ví dụ:**
- **Input:**

  4 1
  1 10
  21 5
  1 10
  100 100

- **Output:**

  3

- **Giải thích:**
- Bạn bắt đầu với `c = 1`.
- Bạn có thể giải bài thứ 1 (kỹ năng yêu cầu `1`, sau khi giải tăng thêm `10`), tăng kỹ năng lên `11`.
- Sau đó bạn giải bài thứ 3 (kỹ năng yêu cầu `1`, sau khi giải tăng thêm `10`), tăng kỹ năng lên `21`.
- Cuối cùng bạn giải bài thứ 2 (kỹ năng yêu cầu `21`, sau khi giải tăng thêm `5`), tăng kỹ năng lên `26`.
- Bài thứ 4 yêu cầu `100` kỹ năng nên không thể giải được. Tổng cộng bạn giải được 3 bài.

---

## [Lì xì](https://lqdoj.edu.vn/problem/lixi)

### **Tóm tắt đề bài:**

Nhân dịp Tết, ba bé Bo chuẩn bị `n` túi lì xì cho bé Bo. Mỗi túi lì xì có một số tiền `a_i` và một số lượng túi khác `b_i` mà bé Bo có thể chọn thêm sau khi chọn túi đó. Bé Bo có thể bắt đầu chọn một túi bất kỳ và sau đó tiếp tục chọn thêm các túi khác nếu còn lượt chọn. Nhiệm vụ của bạn là xác định thứ tự chọn túi sao cho tổng số tiền bé Bo có được là lớn nhất.

- **Input:**
- Dòng đầu tiên chứa số nguyên `n` (số lượng túi lì xì).
- `n` dòng tiếp theo, mỗi dòng chứa hai số nguyên `a_i` (số tiền trong túi lì xì thứ `i`) và `b_i` (số lượng túi lì xì khác mà bé Bo được phép chọn thêm sau khi chọn túi `i`).

- **Output:**
- Một số nguyên xác định tổng số tiền lớn nhất mà bé Bo có thể thu được.

### **Ví dụ:**

- **Input 1:**

  3
  1 0
  2 0
  0 2

- **Output 1:**

  3

- **Input 2:**

  5
  0 0
  2 0
  2 0
  3 0
  5 1

- **Output 2:**

  8

### **Giải thích:**

- **Input 1:**
- Bé Bo có thể chọn túi thứ 2 (có 2 đồng) và sau đó chọn túi thứ 1 (có 1 đồng), tổng cộng là 3 đồng.
- Hoặc chọn túi thứ 3 để có thêm quyền chọn 2 túi khác, sau đó chọn túi 2 và túi 1, nhưng tổng số tiền vẫn là 3 đồng.

- **Input 2:**
- Bé Bo có thể chọn túi 5 trước (có 5 đồng và được chọn thêm 1 túi nữa).
- Sau đó chọn túi thứ 4 (có 3 đồng).
- Tổng cộng là 8 đồng.

### **Phân tích bài toán**

Bài toán yêu cầu xác định tổng số tiền lớn nhất mà bé Bo có thể nhận được bằng cách chọn các túi lì xì theo một thứ tự tối ưu, tận dụng số lượng túi có thể chọn thêm `b_i`.

#### **Ý tưởng giải bài:**
- Ta cần sắp xếp các túi lì xì dựa trên số tiền và số lượng túi có thể chọn thêm.
- Sau đó, thực hiện việc chọn túi theo chiến lược: ưu tiên chọn túi có số tiền lớn trước và có khả năng chọn thêm túi.

### **Cách làm chi tiết:**

1. **Nhập dữ liệu:** Đầu tiên, ta sẽ nhập số lượng túi lì xì `n` và các giá trị `a_i`, `b_i` cho mỗi túi.
2. **Sắp xếp túi lì xì:** Sắp xếp các túi theo số tiền `a_i` giảm dần. Nếu có nhiều túi có cùng số tiền thì ưu tiên chọn túi có khả năng chọn thêm nhiều túi nhất `b_i` lớn hơn.
3. **Tính toán tổng tiền:** Bắt đầu chọn các túi từ danh sách đã sắp xếp, cập nhật tổng tiền và số lượng túi có thể chọn thêm.
4. **Xuất kết quả:** In ra tổng số tiền lớn nhất mà bé Bo có thể nhận được.

### **Code lời giải:**

# Nhập dữ liệu đầu vào
n = int(input())
bags = []

# Nhập các túi lì xì với số tiền và số túi có thể chọn thêm
for _ in range(n):
    a, b = map(int, input().split())
    bags.append((a, b))

# Sắp xếp các túi theo số tiền giảm dần, nếu cùng số tiền thì ưu tiên túi có b_i lớn hơn
bags.sort(key=lambda x: (-x[0], -x[1]))

# Biến đếm tổng tiền và số túi có thể chọn thêm
total_money = 0
remaining_picks = 1

# Duyệt qua từng túi lì xì
for a, b in bags:
    if remaining_picks > 0:
        total_money += a
        remaining_picks += b - 1

# In ra tổng số tiền lớn nhất mà bé Bo có thể nhận được
print(total_money)

### **Giải thích code:**

- **Dữ liệu đầu vào:** Ta nhập số lượng túi `n` và các giá trị `a_i` (số tiền) và `b_i` (số túi có thể chọn thêm).

- **Sắp xếp:** Các túi được sắp xếp theo số tiền `a_i` giảm dần để chọn túi có số tiền lớn trước. Nếu có cùng số tiền, ưu tiên túi có `b_i` lớn hơn.

- **Duyệt qua các túi:** Với mỗi túi được chọn, nếu còn lượt chọn, ta cộng số tiền của túi vào tổng tiền và cập nhật số lượng túi còn có thể chọn thêm.

- **Kết quả:** In ra tổng số tiền lớn nhất mà bé Bo có thể nhận được.

### **Ví dụ:**

- **Input 1:**

  3
  1 0
  2 0
  0 2

- **Output 1:**

  3

- **Input 2:**

  5
  0 0
  2 0
  2 0
  3 0
  5 1

- **Output 2:**

  8

- **Giải thích:**
- Chọn túi có số tiền lớn nhất trước, đảm bảo chọn được tối đa số lượng túi với tổng số tiền cao nhất.

---

### **Tóm tắt đề bài:**

Bạn được cung cấp `n` túi lì xì, mỗi túi có số tiền `a_i` và số lượt chọn thêm `b_i`. Bé Bo có thể bắt đầu chọn một túi bất kỳ, sau đó nếu túi đó có `b_i > 0`, bé Bo sẽ được chọn thêm `b_i` túi nữa. Nhiệm vụ của bạn là xác định số tiền lớn nhất bé Bo có thể nhận được bằng cách chọn túi lì xì theo chiến lược tối ưu.

- **Input:**
- Dòng đầu tiên chứa số nguyên `n` (số lượng túi lì xì).
- Tiếp theo là `n` dòng, mỗi dòng chứa hai số nguyên `a_i` (số tiền trong túi lì xì thứ `i`) và `b_i` (số lượt chọn thêm túi lì xì sau khi chọn túi `i`).

- **Output:**
- Một số nguyên là số tiền lớn nhất có thể nhận được.

### **Ví dụ:**

- **Input:**

  3
  1 0
  2 0
  0 2

- **Output:**

  3

- **Giải thích:**
- Bé Bo sẽ chọn túi thứ 3 trước (vì có `b_3 = 2`), nhưng vì túi này không có tiền (`a_3 = 0`), sau đó sẽ chọn túi 2 và túi 1 để nhận tổng cộng 3 tiền.

### **Phân tích bài toán**

Bài toán yêu cầu tìm tổng số tiền lớn nhất có thể nhận được từ các túi lì xì, bắt đầu từ bất kỳ túi nào và tiếp tục chọn thêm theo số lượt chọn thêm.

#### **Ý tưởng giải bài:**

- **Sắp xếp:** Đầu tiên, sắp xếp các túi lì xì theo số lượt chọn thêm (`b_i`) giảm dần. Nếu số lượt chọn thêm bằng nhau, ưu tiên chọn túi có số tiền lớn hơn (`a_i`).
- **Duyệt qua các túi:** Bắt đầu với một lượt chọn ban đầu, và chọn các túi theo thứ tự đã sắp xếp. Với mỗi túi được chọn, cập nhật số tiền và số lượt chọn thêm còn lại.

### **Cách làm chi tiết:**

1. **Nhập dữ liệu:** Đầu tiên, ta sẽ nhập số lượng túi lì xì `n` và thông tin về các túi.
2. **Sắp xếp:** Sắp xếp các túi lì xì theo số lượt chọn thêm giảm dần. Nếu số lượt chọn thêm bằng nhau, sắp xếp theo số tiền giảm dần.
3. **Duyệt qua các túi:** Với mỗi túi, nếu còn lượt chọn thêm, cộng số tiền của túi đó vào tổng tiền và cập nhật số lượt chọn thêm còn lại.
4. **In kết quả:** Cuối cùng, in ra số tiền lớn nhất có thể nhận được.

### **Code lời giải:**

# Nhập dữ liệu đầu vào
n = int(input())
li_xi = []

# Nhập các túi lì xì với số tiền và số lượt chọn thêm
for _ in range(n):
    a, b = map(int, input().split())
    li_xi.append((a, b))

# Sắp xếp các túi lì xì theo số lượt chọn thêm giảm dần, sau đó là số tiền giảm dần
li_xi.sort(key=lambda x: (-x[1], -x[0]))

# Biến đếm số lượng lượt chọn thêm còn lại
remaining_picks = 1
# Biến lưu số tiền hiện tại của ta
total_money = 0

# Duyệt qua từng túi lì xì đã sắp xếp
for a, b in li_xi:
    if remaining_picks > 0:  # Nếu còn lượt chọn thêm
        # số tiền của ta tăng lên
        ...
        # số lượt của ta tăng lên
        ...

# In ra số tiền nhiều nhất có thể nhận được
...

### **Giải thích code:**

- **Nhập dữ liệu:** Đọc số lượng túi lì xì và thông tin về từng túi.
- **Sắp xếp:** Các túi lì xì được sắp xếp sao cho ưu tiên chọn những túi có nhiều lượt chọn thêm nhất, và trong trường hợp lượt chọn thêm bằng nhau, chọn túi có nhiều tiền nhất.
- **Duyệt qua các túi:** Nếu còn lượt chọn thêm, chọn túi đó và cộng số tiền vào tổng số tiền, đồng thời cập nhật số lượt chọn thêm còn lại.
- **Kết quả:** Tổng số tiền lớn nhất mà bé Bo có thể nhận được.

### **Ví dụ:**
- **Input:**

  3
  1 0
  2 0
  0 2

- **Output:**

  3

---

## [Mua sách](https://lqdoj.edu.vn/problem/book)

### **Tóm tắt đề bài:**
Bạn được yêu cầu tính toán tổng số tiền nhỏ nhất mà một khách hàng phải trả khi mua sách từ một cửa hàng với quy tắc "mua 3, tặng 1". Cụ thể:
- Nếu khách hàng mua 3 quyển sách, sẽ được tặng quyển sách có giá rẻ nhất trong 3 quyển đó.
- Khách hàng có thể mua nhiều quyển sách, và cô bán hàng muốn sắp xếp sao cho khách hàng trả ít tiền nhất có thể.

**Input:**
- Dòng đầu tiên chứa số nguyên `N` (số lượng sách khách hàng mua).
- Tiếp theo là `N` dòng, mỗi dòng chứa giá của một quyển sách.

**Output:**
- In ra số nguyên là tổng tiền nhỏ nhất mà khách hàng phải trả.

### **Hướng làm bài:**
1. **Sắp xếp giảm dần giá các quyển sách:** Để tối ưu, ta sẽ sắp xếp các quyển sách theo giá từ cao đến thấp. Điều này đảm bảo rằng những quyển sách rẻ nhất trong mỗi nhóm 3 quyển sẽ được miễn phí.
2. **Nhóm sách:** Sau khi sắp xếp, chia các quyển sách thành các nhóm 3 quyển. Trong mỗi nhóm, quyển sách thứ 3 (rẻ nhất) sẽ được miễn phí.
3. **Tính tổng tiền phải trả:** Cộng giá của các quyển sách trong mỗi nhóm, bỏ qua quyển sách thứ 3.

### **Thuật toán:**
1. Nhập số lượng sách `N` và giá của từng quyển sách.
2. Sắp xếp danh sách giá sách theo thứ tự giảm dần.
3. Khởi tạo biến `total` để lưu tổng tiền.
4. Duyệt qua danh sách sách theo nhóm 3 quyển, cộng giá của 2 quyển đầu tiên trong mỗi nhóm (bỏ qua quyển thứ 3).
5. Sau khi duyệt hết, in ra tổng tiền.

### **Code lời giải:**

# Nhập dữ liệu đầu vào
n = int(input())  # Số lượng sách
books = []

# Nhập giá từng quyển sách
for _ in range(n):
    books.append(int(input()))

# Sắp xếp giá sách theo thứ tự giảm dần
books.sort(reverse=True)

# Tính tổng tiền phải trả
total = 0
for i in range(n):
    if (i % 3) != 2:  # Bỏ qua quyển sách thứ 3 trong mỗi nhóm 3 quyển
        total += books[i]

# In ra tổng số tiền phải trả
print(total)

### **Giải thích code:**
- **Nhập dữ liệu:** Dòng đầu tiên nhận vào số lượng sách `n`, sau đó lần lượt nhập giá từng quyển sách vào danh sách `books`.
- **Sắp xếp:** Ta sắp xếp giá của các quyển sách theo thứ tự giảm dần, để chắc chắn rằng quyển sách rẻ nhất trong mỗi nhóm 3 quyển sẽ được miễn phí.
- **Tính tổng:** Duyệt qua từng quyển sách và cộng giá của 2 quyển đầu tiên trong mỗi nhóm 3 quyển. Quyển thứ 3 trong mỗi nhóm được miễn phí, vì vậy ta bỏ qua nó.
- **Kết quả:** Cuối cùng, in ra tổng số tiền mà khách hàng phải trả.

### **Ví dụ:**

- **Input 1:**

  6
  6
  4
  5
  5
  5
  5

- **Output 1:**

  21

**Giải thích:**
- Sách được sắp xếp thành: `6, 5, 5, 5, 5, 4`.
- Tổng tiền phải trả là `6 + 5 + 5 + 5 = 21` (bỏ qua sách có giá 4).

- **Input 2:**

  4
  3
  2
  3
  2

- **Output 2:**

  8

**Giải thích:**
- Sách được sắp xếp thành: `3, 3, 2, 2`.
- Tổng tiền phải trả là `3 + 3 + 2 = 8` (bỏ qua sách có giá 2).

---

## Thắc mắc và hỗ trợ khi làm bài

Nếu trong quá trình giải bài các bạn gặp khó khăn, có thể liên hệ với mình qua Zalo hoặc Facebook dưới đây. Hãy nhớ áp dụng phương pháp được hướng dẫn trước khi nhờ giúp đỡ.

- Zalo: ***0914167544*** (Lê Đức Phúc Long)
- Facebook: m.me/phuclong.leduc

**Chúc các bạn học tập vui vẻ!**