Bài tập cho bạn nào thích thuật toán đây

[tungloiloi1]

Bài 1: COMPARE.PAS
Xét hoán vị P các số nguyên từ 1 tới n (1<n<10^5). Các số của hoán vị được viết thành 1 hàng, giữa 2 số liên tiếp người ta đặt dấu so sánh < hay > tùy theo quan hệ của chúng.
Yêu cầu: Cho biết xâu chứa n-1 quan hệ giữa 2 số liên tiếp. Hãy xác định hoán vị P thỏa mãn xâu quan hệ này. Nếu tồn tại nhiều hoán vị khác nhau thỏa mãn thì đưa ra hoán vị bất kì trong số đó.
Dữ liệu: Vào từ file văn bản compare.inp:
_ Dòng đầu ghi số nguyên N.
_ Dòng 2 chứa xâu độ dài N-1 chứa các kí tự trong tập {<,>}.
Kết quả: Đưa ra file văn bản compare.out trên 1 dòng n số nguyên xác định hoán vị tìm được
VD:
compare.inp:
5
>><<
compare.out:
3 2 1 4 5

Bài 2: CHIA.PAS
Cho dãy số X có N số nguyên dương, hãy chọn ra các số trong dãy X sao cho tổng các số được chọn chia hết cho N
INP: dòng 1 chứa số N, dòng 2 là N số nguyên, số thứ i là X
(các số trong tệp đều nguyên dương và nhỏ hơn 10^5)
Out: dòng 1 là 0 hoặc 1 tương ứng với không chọn được hay chọn được dãy thỏa mãn đề bài.
Dòng 2 chứa vị trí các số được chọn và đã sắp tăng.
Thuật toán tự nhiên mà các bạn được biết liệu có áp dụng được không? Suy nghĩ chắc chắn đã nhé [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) giới hạn có thể lên tới 10^6 thậm chí 10^7 (2s) [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

[quechi]

Xét hoán vị P các số nguyên từ 1 tới n (1<n<10^5). Các số của hoán vị được viết thành 1 hàng, giữa 2 số liên tiếp người ta đặt dấu so sánh < hay > tùy theo quan hệ của chúng.
Yêu cầu: Cho biết xâu chứa n-1 quan hệ giữa 2 số liên tiếp. Hãy xác định hoán vị P thỏa mãn xâu quan hệ này. Nếu tồn tại nhiều hoán vị khác nhau thỏa mãn thì đưa ra hoán vị bất kì trong số đó.
Dữ liệu: Vào từ file văn bản compare.inp:
_ Dòng đầu ghi số nguyên N.
_ Dòng 2 chứa xâu độ dài N-1 chứa các kí tự trong tập {<,>}.
Kết quả: Đưa ra file văn bản compare.out trên 1 dòng n số nguyên xác định hoán vị tìm được
VD:
compare.inp:
5
>><<
compare.out:
3 2 1 4 5

Bài này hiện có 2 thuật toán xử lí tốt, 1 là thuật toán O(N log N), 1 là thuật toán O(N). Bạn nào có đóng góp gì thêm, hoặc muốn đưa ra thuật toán của mình thì tham gia topic nhé.

Bài này anh lấy ở đâu thế? Trong xấp bài tập của em cũng có mà không biết nguồn ở đâu ra:
O(n) của em [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
- i=1, j=n.
- Xét các vị trí rõ ràng: vị trí 1, vị trí N, vị trí có dấu quan hệ 2 bên là <> hoặc ><. Mỗi lần gặp 1 vị trị như vậy thì xảy ra 2 trường hợp:
+ Nhỏ rõ ràng: điền i. inc(i).
+ Lớn rõ ràng: điền j. dec(j).
Sau khi điền được các vị trí rõ ràng. Còn lại là các đoạn giảm, tăng liên tục. Điền i,j vào (cũng tăng i, giảm j để điền).
Kết luận 2*N vòng lặp. O(N) ^^ .
Chẳng hay anh Ginta xài thuật toán nào?

[ductrong85]

Bài này anh lấy ở đâu thế? Trong xấp bài tập của em cũng có mà không biết nguồn ở đâu ra:
O(n) của em [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
- i=1, j=n.
- Xét các vị trí rõ ràng: vị trí 1, vị trí N, vị trí có dấu quan hệ 2 bên là <> hoặc ><. Mỗi lần gặp 1 vị trị như vậy thì xảy ra 2 trường hợp:
+ Nhỏ rõ ràng: điền i. inc(i).
+ Lớn rõ ràng: điền j. dec(j).
Sau khi điền được các vị trí rõ ràng. Còn lại là các đoạn giảm, tăng liên tục. Điền i,j vào (cũng tăng i, giảm j để điền).
Kết luận 2*N vòng lặp. O(N) ^^ .
Chẳng hay anh Ginta xài thuật toán nào?

Bài này anh vừa thấy thầy giáo cho hôm trước, bảo là lấy từ tập bài của thầy Nguyễn Thanh Tùng .
Bài này nếu em nhận xét tốt thì vị trí rõ ràng chỉ có 2: 1 hoặc N, những vị trí <> hoặc >< không cần quan tâm. Thuật toán cũng chỉ cần 1 vòng lặp, không cần tới 2. Và 1 điều nữa là lúc đầu không nên cố để tạo luôn kết quả đúng mà qua 1 bước trung gian. Gợi ý thế thôi, còn để thuật toán lại cho mọi người suy nghĩ đã, nói ra bây giờ chán lắm. Em quan tâm thì trao đổi riêng với anh.

[phuongnam]

Bài này anh vừa thấy thầy giáo cho hôm trước, bảo là lấy từ tập bài của thầy Nguyễn Thanh Tùng (thầy ấy về hưu rồi nhưng vẫn là VIP [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) ).
Bài này nếu em nhận xét tốt thì vị trí rõ ràng chỉ có 2: 1 hoặc N, những vị trí <> hoặc >< không cần quan tâm. Thuật toán cũng chỉ cần 1 vòng lặp, không cần tới 2. Và 1 điều nữa là lúc đầu không nên cố để tạo luôn kết quả đúng mà qua 1 bước trung gian. Gợi ý thế thôi, còn để thuật toán lại cho mọi người suy nghĩ đã, nói ra bây giờ chán lắm. Em quan tâm thì trao đổi riêng với anh.

2 tập là cfep và cfkv phải không anh????

[remxinhthoa]

Tập nào anh không biết, em có tài liệu hay cái gì của thầy Tùng thì cho anh với, anh cũng thích làm bài thầy ấy.

[hoang_kisirong]

Tập nào anh không biết, em có tài liệu hay cái gì của thầy Tùng thì cho anh với, anh cũng thích làm bài thầy ấy.

Tài liệu này do thầy trực tiếp giảng dạy và phát cho các thầy ở các trường.
Một số bài em đã post nằm trong đó đấy!
Nếu anh cần em post thêm nhá

[hungvietuc1]

Ừ, post cho anh mấy cái đề của thầy Tùng. Nếu có thuật toán đi kèm thì càng tốt. Tuần trước lên học thầy mấy hôm giờ nghiện [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

[duydiem6868]

Ừ, post cho anh mấy cái đề của thầy Tùng. Nếu có thuật toán đi kèm thì càng tốt. Tuần trước lên học thầy mấy hôm giờ nghiện [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

Có đề + test + thuật toán của em => bài đựoc bài mất [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])