Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Fri 19 Mar 2010, 21:20

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
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Sat 20 Mar 2010, 21:24

Chán quá, chả thấy ai trải lời
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Sun 21 Mar 2010, 20:37

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.


Được sửa bởi administrators ngày Sun 21 Mar 2010, 21:00; sửa lần 1. (Reason for editing : gõ nhằm m^2 và m.n)
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Sun 21 Mar 2010, 21:22

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ờ.
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Wed 24 Mar 2010, 21:05

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
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Wed 24 Mar 2010, 21:07

Ừ thì bài này dễ mà confused
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Xóa số để tạo thành số nhỏ nhất, lớn nhất.   Today at 21:29

Về Đầu Trang Go down
 
Xóa số để tạo thành số nhỏ nhất, lớn nhất.
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến