Elearning CodePath – CTP Online Judge

Số Lớn

NUMMAX

🟢 Hard #String

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho trước một xâu ký tự $S$, có thể chứa các chữ cái, chữ số và dấu cách.

Yêu cầu:
Hãy loại bỏ một số ký tự ra khỏi xâu $S$ sao cho **6 ký tự số** còn lại, theo đúng thứ tự ban đầu, tạo thành số **lớn nhất** có 6 chữ số.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `NUMMAX.INP`:

* Gồm một dòng chứa xâu $S$ cho trước.

Giới hạn:
* Độ dài xâu $S$ không quá $300$ ký tự.

---
### 📤 Định dạng Đầu ra

Ghi ra file `NUMMAX.OUT` gồm:

1.  Dòng thứ nhất: Chứa 6 ký tự số cần tìm theo yêu cầu (tạo thành số lớn nhất).
2.  Dòng thứ hai: Là một số nguyên thể hiện **tổng** của 6 ký tự số trên.

Trong trường hợp xâu $S$ không chứa đủ 6 ký tự số hợp lệ để tạo thành một dãy số 6 chữ số, ghi ra $-1$.

---
### ✨ Ví dụ

| Input (`NUMMAX.INP`) | Output (`NUMMAX.OUT`) |
| :--- | :--- |
| `23459225` | `459225` <br> `27` |
| `1g9ahgj78hd6r4g28a` | `986428` <br> `37` |
| `Abc43-1` | `-1` |

Giải thích ví dụ 2:
Xâu số hợp lệ là $19786428$. Cần chọn 6 ký tự để tạo số lớn nhất.
Chọn tham lam từ trái sang phải:
1. Chọn 9 (ở vị trí 2).
2. Ký tự tiếp theo phải là lớn nhất sau vị trí của 9 (từ $786428$). Chọn 8.
3. Ký tự tiếp theo phải là lớn nhất sau vị trí của 8 (từ $6428$). Chọn 6.
4. Ký tự tiếp theo phải là lớn nhất sau vị trí của 6 (từ $428$). Chọn 4.
5. Ký tự tiếp theo phải là lớn nhất sau vị trí của 4 (từ $28$). Chọn 2.
6. Ký tự cuối cùng phải là lớn nhất sau vị trí của 2 (từ $8$). Chọn 8.
Số lớn nhất là **986428**. Tổng các chữ số: $9+8+6+4+2+8 = 37$.

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $50\%$ | Độ dài xâu $S$ không quá $100$ ký tự |
| $50\%$ | Độ dài xâu $S$ không quá $300$ ký tự |

---

✅ Đã AC: 0 / 3 submissions