Cuộc thi Lập trinh thuật toán

[10520272]

Ờh há. Giờ mới ngộ ra, cảm ơn bạn nhiều.

[09520019]

Ấy, ấy. Chỉ là mình đề xuất vậy thôi. Vì thấy các bài khác có thể giải bằng O(1) được nên mình thử đặt vấn đề như vậy xem có ai giải quyết được không. Thêm một lý do nữa là với n có hai chữ số thì ta có công thức O(1) là : m = 11*(n/10 + n%10) - n. Nên mình mới hy vọng rằng biết đâu có công thức tổng quát cho mọi trường hợp thì tuyệt vời quá.

Công thức đó không thể phát triển thành O(1) trong TH tổng quát vì n/10 + n%10 đã nói lên điều đó O(log n)

Cái này có lẽ mình không hiểu ý bạn lắm, prime[10000000000] thì dĩ nhiên không được 0.001s rồi. Nhưng chả là mình đang tối ưu tất cả các bài toán (time = 0s hoặc 0.001s), ba bài kia thì OK trong trường hợp xấu nhất rồi chỉ có bài này với n = 1000 thì nó cứ ra 0.002s, thế mới tức.


Thanks bạn, nhờ bạn mà bây giờ mình chạy 200k chỉ mất ~0.4s. Đúng là chịu khó tìm kiếm một tí sẽ ra ngay. Nhưng có sửa thế nào thì time prime[1000] vẫn là 0.002s, lạ nhỉ.

Thậm chí bạn cout << "Hello world" << endl vẫn mất 0.001s.

[10520272]

Mình không làm đc O(1) nếu bạn có cách giải O(1) thì chỉ mình với

Ấy, ấy. Chỉ là mình đề xuất vậy thôi. Vì thấy các bài khác có thể giải bằng O(1) được nên mình thử đặt vấn đề như vậy xem có ai giải quyết được không. Thêm một lý do nữa là với n có hai chữ số thì ta có công thức O(1) là : m = 11*(n/10 + n%10) - n. Nên mình mới hy vọng rằng biết đâu có công thức tổng quát cho mọi trường hợp thì tuyệt vời quá.

Thôi đủ rồi ông tướng ạ. prime[1000000000] xem anh hai có ra 0.001s nổi không nhá =))

Cái này có lẽ mình không hiểu ý bạn lắm, prime[10000000000] thì dĩ nhiên không được 0.001s rồi. Nhưng chả là mình đang tối ưu tất cả các bài toán (time = 0s hoặc 0.001s), ba bài kia thì OK trong trường hợp xấu nhất rồi chỉ có bài này với n = 1000 thì nó cứ ra 0.002s, thế mới tức.

bài 1 mà 200k dưới 1s thì đã có 1 bài phân tích từ lâu trên forum rồi ^_^ chịu khó lục lại

Thanks bạn, nhờ bạn mà bây giờ mình chạy 200k chỉ mất ~0.4s. Đúng là chịu khó tìm kiếm một tí sẽ ra ngay. Nhưng có sửa thế nào thì time prime[1000] vẫn là 0.002s, lạ nhỉ.

[08520581]

Các bạn lưu ý: Hiện có nhiều bạn sử dụng gmail để nộp bài, nhưng BTC chưa nhận được bất kì bài làm nào gửi tới bằng yahoo mail hết. Vì vậy có khả năng yahoo gửi quá chậm. Nếu bạn nào có gmail thì nên xài gmail, không nên dùng yahoo mail để nộp bài

[09520019]

Hổm giờ chỉ thấy bàn bài 1 thôi nhỉ. Xem ra chỉ có bài này là đáng quan tâm xem xét. Có ai giải bài 3 O(1) được không nhỉ ?

Mình không làm đc O(1) nếu bạn có cách giải O(1) thì chỉ mình với

p/s: Vẫn là bài 1, có ai làm prime[1000] mà ra 0s không :d, mình làm hết sức vẫn ra 0.002. Lâu lâu mới ra 0.001

Thôi đủ rồi ông tướng ạ. prime[1000000000] xem anh hai có ra 0.001s nổi không nhá =))

Thế đáp án của bài 3 cho test này là 7654321123456789 đúng không các bạn.
Mà hình như cái này nhập xuất (10^18) là phải xài long long chứ không được xài double nhỉ.

p/s: Đã có ai thực sự code bài 1 200.000 mà ra dưới 1s chưa vậy.

Hình như vậy: 3 số đầu thì đúng rồi
bài 1 mà 200k dưới 1s thì đã có 1 bài phân tích từ lâu trên forum rồi ^_^ chịu khó lục lại

[10520101]

mình đã sửa lại rồi, 200.000 0.751 s

[10520513]

Thế đáp án của bài 3 cho test này là 7654321123456789 đúng không các bạn.
Mà hình như cái này nhập xuất (10^18) là phải xài long long chứ không được xài double nhỉ.

p/s: Đã có ai thực sự code bài 1 200.000 mà ra dưới 1s chưa vậy.

à, đúng mới dám nói chứ bạn, sai thì tính time làm gì,hic. muốn 200000 mà dưới 1 s hả, dễ mà, if(n==200000) dem=2750159 hehe, giỡn thôi chứ để nghỉ cách tối ưu thử xem, mà chắc không có quá.
uhm, phải xài long long

[10520272]

Tại vì chỉ có bài 1 là khác nhau giữa các input là khá lớn thôi, các bài còn lại thì không có gần như không có khác nhau mấy, bài 3 mình xài đệ quy lâu quá nãn. với input là 987654321123456700 thử 3 lần cho các kết quả sao 0,9-0,3-0,5--->> chả hiểu thế nào.

Thế đáp án của bài 3 cho test này là 7654321123456789 đúng không các bạn.
Mà hình như cái này nhập xuất (10^18) là phải xài long long chứ không được xài double nhỉ.

p/s: Đã có ai thực sự code bài 1 200.000 mà ra dưới 1s chưa vậy.

[11520126]

Bạn cho mình email của bạn lun đi

Mail em: hoang_1434@yahoo.com.vn

[10520513]

Hay quá anh. Em làm mất tới 5.565s =.='

chắc tại em phải nhập n, còn cái này anh gán n=200000 luôn.

[11520126]

uhm, 2.750.159 đúng rồi, của mình chạy 200000 chậm quá, chạy kiểm tra là 1.946s, biên dịch bằng g++.

Hay quá anh. Em làm mất tới 5.565s =.='

[10520101]

Thế là có người đã phải nộp bài lại )

Chắc phải vậy thôi

[10520513]

Hổm giờ chỉ thấy bàn bài 1 thôi nhỉ. Xem ra chỉ có bài này là đáng quan tâm xem xét. Có ai giải bài 3 O(1) được không nhỉ ?

p/s: Vẫn là bài 1, có ai làm prime[1000] mà ra 0s không :d, mình làm hết sức vẫn ra 0.002. Lâu lâu mới ra 0.001

Tại vì chỉ có bài 1 là khác nhau giữa các input là khá lớn thôi, các bài còn lại thì không có gần như không có khác nhau mấy, bài 3 mình xài đệ quy lâu quá nãn. với input là 987654321123456700 thử 3 lần cho các kết quả sao 0,9-0,3-0,5--->> chả hiểu thế nào.

[10520272]

Hổm giờ chỉ thấy bàn bài 1 thôi nhỉ. Xem ra chỉ có bài này là đáng quan tâm xem xét. Có ai giải bài 3 O(1) được không nhỉ ?

p/s: Vẫn là bài 1, có ai làm prime[1000] mà ra 0s không :d, mình làm hết sức vẫn ra 0.002. Lâu lâu mới ra 0.001

[10520513]

Theo mình thì n = 200.000 thì kết quả là 2.750.159.
Còn số 847.987 có lẽ không phải là số nguyên tố bạn à, nó chia hết cho 7.
Có ai có đáp án khác về n=200.000 không.

uhm, 2.750.159 đúng rồi, của mình chạy 200000 chậm quá, chạy kiểm tra là 1.946s, biên dịch bằng g++.