Elearning CodePath – CTP Online Judge

DOISO

🟢 Easy #Dynamic Programming #Number Theory

### Thông tin chung

### Đề bài

Cho một số nguyên dương $N$. Ta thực hiện thao tác thay đổi các chữ số của $N$ theo quy tắc sau:

Chọn một vị trí bất kỳ trong chuỗi chữ số của $N$.

Thay chữ số tại vị trí đó bằng một chữ số mới từ $0$ đến $9$.

Số mới được tạo thành phải có cùng số lượng chữ số với $N$ và không được có chữ số $0$ ở đầu.

Mỗi lần thay đổi một vị trí được tính là một thao tác.

Yêu cầu: Hãy tìm số thao tác tối thiểu để biến đổi số $N$ ban đầu thành một số mới là bội của $111$.

### Dữ liệu vào

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

Điều kiện:

$$1 \le T \le 25$$

Mỗi số $N$ có không quá $18$ chữ số.

### Dữ liệu ra

Ghi ra file DOISO.OUT gồm $T$ dòng, mỗi dòng là kết quả tương ứng với một bộ dữ liệu.

Nếu không thể biến đổi $N$ thành một số có cùng số chữ số, không bắt đầu bằng $0$ và chia hết cho $111$, in ra $-1$.

### Ví dụ

| DOISO.INP | DOISO.OUT | Giải thích |
| :------------------------------------------------ | :------------------------------ | :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `4` `111` `220` `13` `991990` | `0` `1` `-1` `2` | Số `111` đã chia hết cho `111`. Số `220` có thể đổi chữ số cuối từ `0` thành `2` để được `222`, chia hết cho `111`. Số `13` không thể biến đổi thành số có 2 chữ số chia hết cho `111`. Số `991990` đổi chữ số ở vị trí 3 và vị trí 6 để được `999999`, chia hết cho `111`. |

### Subtask

| Subtask | Ràng buộc                                                                                          | Điểm  |
| :------ | :------------------------------------------------------------------------------------------------- | :---- |
| 1       | Mỗi số nguyên có số lượng chữ số không quá $9$ và có nhiều nhất một chữ số khác các chữ số còn lại | $30%$ |
| 2       | $T \le 10$, mỗi số nguyên có số lượng chữ số không quá $9$                                         | $40%$ |
| 3       | $T \le 25$, mỗi số nguyên có số lượng chữ số không quá $18$                                        | $30%$ |

✅ Đã AC: 2 / 2 submissions