Xóa số để tạo thành số nhỏ nhất, lớn nhất.

Cho một số tự nhiên n chữ số a= a1 a2 ... an (ai  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, i = 1, 2, ..., n; (n có thể đạt tới giá trị 1000000). Hãy tìm cách xoá bỏ m chữ số của a, sao cho số thu được sau khi xoá bỏ m chữ số đó là nhỏ nhất.

Dữ liệu: Vào từ file văn bản XOASO.INP có cấu trúc:
- Dòng đầu ghi giá trị m và n cách nhau ít nhất một dấu cách.
- n dòng tiếp theo ghi các chữ số của a theo thứ tự từ trái qua phải.

Kết quả: Ghi ra file XOASO.OUT gồm m dòng, mỗi dòng chứa chữ số bị xoá và chỉ số của nó trong dãy số gốc, được phân cách bởi ít nhất một dấu cách.

Ví dụ: với m=2, n=5, a= 41325 thì file XOASO.INP gồm 6 dòng sau:
2 5
4
1
3
2
5

và file XOASO.OUT gồm hai dòng sau:
4 1
3 3

Chán quá, chả thấy ai trải lời

Bài cho khó vậy ai mà giải cho được, nên bạn thấy chán là chuyện bình thường.
Vì số liệu cho quá lớn nên muốn giải bài này chạy dưới 1 giây cần đến 2 kỹ thuật cao cấp
- Cơ sở suy luận toán cao cấp
- Cấu trúc cơ sở dữ liệu đặc biệt IT.

Cách làm như sau:

- Trong m+1 số đầu tiên chọn ra số nhỏ nhất. Xóa các số trước đó rồi làm tiếp...

* Ví dụ m=10:
* Ta xét 11 số thì số nhỏ nhất ở vị trí thứ 7. Thì ta sẽ xóa đi 6 số đầu tiên chừa số thứ bảy lại (làm số đứng đầu luôn đấy)
* Sau đó xét tiếp 4+1 (=5) số từ vị trí thứ 8 và chọn ra số nhỏ nhất. Giả sử số nhỏ nhất năm ở vị trí 11 thì ta xóa bỏ hết tất cả các số có vị trí lớn hơn 7 và nhỏ hơn 11. (hiển nhiên là được 3 số). Như vậy ta đã xóa hết 9 số rồi.
* Sau đó xét tiếp 1+1 (=2) số kế tiếp kể từ vị trí 12, số nào nhỏ thì xóa số đó là xong (bằng xóa đại cái nào cũng được)

- Rỏ ràng ta thấy việc tìm số nhỏ nhất trong 1 dãy số cứ liên tục lặp lại. Như vậy độ phức tạp của thuật toán này là O(m.n). Nếu m nhỏ thì không sao cả. Nhưng nếu m đủ lớn thì ta phải dùng đến cây IT để tìm max (cấu trúc này rất khó hiểu đối với độ tuổi các bạn). Chúc các bạn vui.

administrators đã viết:

Bài cho khó vậy ai mà giải cho được, nên bạn thấy chán là chuyện bình thường.
Vì số liệu cho quá lớn nên muốn giải bài này chạy dưới 1 giây cần đến 2 kỹ thuật cao cấp
- Cơ sở suy luận toán cao cấp
- Cấu trúc cơ sở dữ liệu đặc biệt IT.

Cách làm như sau:

- Trong m+1 số đầu tiên chọn ra số nhỏ nhất. Xóa các số trước đó rồi làm tiếp...

* Ví dụ m=10:
* Ta xét 11 số thì số nhỏ nhất ở vị trí thứ 7. Thì ta sẽ xóa đi 6 số đầu tiên chừa số thứ bảy lại (làm số đứng đầu luôn đấy)
* Sau đó xét tiếp 4+1 (=5) số từ vị trí thứ 8 và chọn ra số nhỏ nhất. Giả sử số nhỏ nhất năm ở vị trí 11 thì ta xóa bỏ hết tất cả các số có vị trí lớn hơn 7 và nhỏ hơn 11. (hiển nhiên là được 3 số). Như vậy ta đã xóa hết 9 số rồi.
* Sau đó xét tiếp 1+1 (=2) số kế tiếp kể từ vị trí 12, số nào nhỏ thì xóa số đó là xong (bằng xóa đại cái nào cũng được)

- Rỏ ràng ta thấy việc tìm số nhỏ nhất trong 1 dãy số cứ liên tục lặp lại. Như vậy độ phức tạp của thuật toán này là O(m.n). Nếu m nhỏ thì không sao cả. Nhưng nếu m đủ lớn thì ta phải dùng đến cây IT để tìm max (cấu trúc này rất khó hiểu đối với độ tuổi các bạn). Chúc các bạn vui.

Rất đúng với ý mình. Tuy nhiên chuyện m quá lớn thì mình vẫn để vậy. Bình thường mình làm với n=10 000 còn 1000 000 thì chưa thử bao giờ.

Bó tay toàn tập cho lit luôn. Lúc đầu thì bảo cho bài dễ cho các bạn trong trường còn làm. Giờ cho những bài như thế này thì chắc chỉ có administrators mới giải dc thui

Ừ thì bài này dễ mà