1 số bài toán tràn ô nhớ !!!!!!!!

[acaceva]

đây là 1 số bài toán pascal khá hay, mong các bác có thể giúp em tìm phương hướng giải quyết
Bài 1: BỐ TRÍ PHÒNG HỌP
Có n cuộc họp đăng kí làm việc tại 1 phòng hội thảo, cuộc họp thứ i bắt đầu tại thời điểm si và kết thúc vào lúc fi. Làm sao để bố trí nhiều cuộc họp tại phòng hội thảo nhiều nhất và các cuộc họp không xen vào nhau
Dữ liệu vào: dòng đầu chứa số n (số cuộc họp n<=1000000)
dòng thứ i trong n chứa 2 số nguyên dương si,fi (si,fi<=10000), i=1,2,..,n;
Kết quả ra: số cuộc họp có thể sắp xếp, các dòng tiếp theo la thứ tự cuộc họp được sắp xếp
VD: vào
5
1 3
2 4
1 6
3 5
7 9
ra
3
1
4
5

[acaceva]

Bài 2: XÓA SỐ
cho số tự nhiên có n chữ số a=a1 a2 a3 .. an(ai={0,1,2,3,4,5,6,7,8,9}, i=1,2..n; n có thể đạt đến 1000000). Hãy tìm cách xóa m chữ số a sao cho số thu được sau khi bỏ đi m số là nhỏ nhất
VD:
Dữ liệu vào: với m=2, n=5, a=41325;
2 5
4
1
3
2
5
Dữ liệu ra:gồm m dòng, mỗi dòng chứa chữ số bị xóa và vị trí của nó nằm tropng dãy gốc
4 1
3 3

[bete]

Tui thử bài 1 nghen:

S: tập hợp các cặp (si,fi) với si tăng dần (s1<=s2<=s3<=...<=sn)
Đặt Tmax=max{fì}. Đặt R là tập kết quả.

Xét bài toán ở cấp k: k cuộc họp đầu tiên trong S; mình phải chọn các cuộc họp lọt trong khỏang thời gian s1->tmax (tmax tùy thuộc vào k; cách tính sẽ được nói sau)
Đặt F là 1 hàm lấy vào 2 tham số: k và tmax; F trả về số cuộc họp cho bài toán cấp k
Mình có 2 lựa chọn cho cuộc họp thứ k (sk,fk):

1) Chọn (sk,fk) ((sk,fk) thuộc R): nếu fk <= tmax. Sau khi chọn (sk,fk) thì mình giải bài toán ở cấp k-1 với tmax trở thành sk (kế tiếp mình không được chọn cuộc họp nào chấm dứt trễ hơn sk) => số nhiều nhất các cuộc họp chọn được theo cách này sẽ là 1+F(k-1, sk) (1 là vì mình chọn (sk,fk))

2) Không chọn (sk,fk) ((sk,fk) không thuộc R): Sau khi không chọn (sk,fk) thì mình giải bài toán ở cấp k-1 với tmax không đổi (kế tiếp mình không được chọn cuộc họp nào chấm dứt trễ hơn tmax) => số nhiều nhất các cuộc họp chọn được theo cách này sẽ là F(k-1, tmax)

Như vậy đáp sồ của bài toán cấp k (được trả về bởi F(k,tmax)):

a) nếu fk<=tmax: đặt n1=1+F(k-1, sk); n2=F(k-1, tmax); đặt r=max(n1,n2) => trả về r.

b) nếu fk>tmax: đặt r=F(k-1, tmax) => trả về r.

Cuối cùng, đáp số của bài toán ban đầu là F(n,Tmax)

Có vài điểm:

* Mình chưa xét điều kiện dừng (khi k=1 ??? khi k=0 ???).

* Mình chỉ đếm số nhiều nhứt các cuộc họp chọn được. Để in ra các cuộc họp trong đáp số phải làm thêm 1 chút.

* Đây là giải đệ qui. Để giải QHD thì sửa lại 1 chút.

(nhưng với n<=1000000 thì tui cũng không nghĩ cách này chịu nỗi :):) Bài toán cho số gì mà lớn dã man quá :):))

(có gì sai sót các bạn chỉ giùm cho, xin cám ơn trước)

[Junior IT]

Gọi a[i] là thời gian bắt đầu trễ nhất của cuộc họp có thời gian kết thúc là i
for i := 1 to 10000 do {
Chọn thời gian kết thúc từ nhỏ đến lớn
Nếu cùng thời gian kết thúc thì chọn thời gian bắt đầu trễ nhất
}

[bete]

Thân gửi Junior IT: cách giải của bạn thật là hay !!!

[Junior IT]

Bài Xóa Số:
Thực hiện tuần tự như sau:
Trong M+1 số đầu tiên, tìm chữ số nhỏ nhất với ưu tiên chọn số bên trái nhất. Gọi vị trí số đó là i, xóa i-1 số đầu tiên. Giảm M := M - (i-1), lại thực hiện như thế với vị trí bắt đầu là i+1...