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

[09520019]

Thẻ [PHP]
Nếu bạn được xem bảng điểm của các kỳ thi Olympic thì bài thi thường hay được điểm lẻ, hiếm khi có điểm chẵn vì đa số mọi người code lần đầu tiên đều dính bug nhỏ cả

Bạn không cần kiểm tra Lỗi gì hết vì đề bài cho 1 <= n <= 1000 thì n sẽ luôn nằm trong khoảng đó

to 09520019: Vâng, có lẽ vậy thật, để mình kiểm tra kĩ lại xem, cảm ơn bạn, dạo này mình hay chủ quan sao ấy :x.

Các bạn cho mình hỏi hơi lạc đề tí là làm sao để chèn CODE của mình vào forum vậy mà có màu cho đẹp vậy.

[09520019]

) Ngây thơ quá ^_^
Bạn chưa tính tới bạn bị bug nhỏ ở chỗ nào đó ư )

Muốn như bạn nói, thì đem tổng thời gian chạy của các bài làm hệ số phụ khi có số bài làm đúng(điểm) bằng nhau thì được. Nếu vậy phải cho nộp nhiều lần

Uhm. Tức là phụ thuộc vào thời gian chạy. Nhưng mình nghĩ cái này vẫn không đảm bảo lắm với thời gian chạy rất bé do khi đó ảnh hưởng của sai số đo sẽ lớn. Vd như câu 2, rất nhiều người sẽ viết thuật toán O(1) nên thời gian chạy rất nhỏ (chủ yếu tốn time là do xuất ra màn hình), nên khi đo ng này lệch ng kia vài chục msec là cả vấn đề rồi.

À, cho mình hỏi nữa là chương trình mình viết có cần kiểm tra thông số nhập vào k. Ví dụ như câu 1 có cần đoạn này không:

if ((n <= 0) || (n > 100))
printf("Loi!\n");

hay việc nhập cho phù hợp là của ban giám khảo.

to 09520536:

Ý mình là giới hạn 1s là quá nhiều với giới hạn số trên đề bài.
Câu 1: Viết chương trình theo kiểu đơn giản nhất (kiểm tra từng số và đến n/2 chứ đừng nói sqrt(n)) và in ra số ng tố thứ 1000 (MAX), vẫn chưa đến một giây.
Câu 2: O(1), khỏi bàn.
Câu 3: O(log(n)), nói chung phụ thuộc vào số chữ số --> tối đa là 18 --> làm sao tới đc 1s.
Câu 4: Chỉ duy nhất có câu này là đủ khả năng chạy quá 1s nếu giải thuật tồi -- mình thử làm theo kiểu đơn giản nhất là tính toán từng số và đếm thì chạy mất 5 phút mà vẫn chưa xét đến 1tr --> nản. Bài này làm đủ kiểu O(1), O(log(n)), O(n), O(n^2)... Nói chung trong trường hợp tồi nhất chỉ có cái O(1) là đảm bảo dưới 1s (dĩ nhiên), O(logn) xấp xỉ 3s... mấy cái sau nản quá k chờ.
--- Edit: O(logn) thực ra vẫn dưới 1s. Hồi nãy nhầm.

[09520668]

Ủa, vậy nếu có nhiều người làm đúng cả 4 bài thì sao. Cứ mỗi bài đúng đc 10đ thì nhỡ có nhiều người 40đ thì sao. Chọn cả à. Còn cái tiêu chuẩn 1s thì mình nghĩ nên xem lại chứ nếu đúng với giới hạn của đề bài thì muốn làm chạy lâu hơn 1s mới khó.

Muốn như bạn nói, thì đem tổng thời gian chạy của các bài làm hệ số phụ khi có số bài làm đúng(điểm) bằng nhau thì được. Nếu vậy phải cho nộp nhiều lần

[09520536]

Ủa, vậy nếu có nhiều người làm đúng cả 4 bài thì sao. Cứ mỗi bài đúng đc 10đ thì nhỡ có nhiều người 40đ thì sao. Chọn cả à. Còn cái tiêu chuẩn 1s thì mình nghĩ nên xem lại chứ nếu đúng với giới hạn của đề bài thì muốn làm chạy lâu hơn 1s mới khó.

Đây là cuộc thi thuật toán, bỏ giới hạn thì còn gì là tối ưu thuật toán nữa.

Ủa, vậy nếu có nhiều người làm đúng cả 4 bài thì sao. Cứ mỗi bài đúng đc 10đ thì nhỡ có nhiều người 40đ thì sao. Chọn cả à. Còn cái tiêu chuẩn 1s thì mình nghĩ nên xem lại chứ nếu đúng với giới hạn của đề bài thì muốn làm chạy lâu hơn 1s mới khó.

[09520019]

Anh cho em hỏi tại sao ta không gán sẵn giá trị Input luôn khỏi cần nhập chi cho mất công kiểm tra thời gian chạy khó khăn( vì mình chỉ quan tâm thời gian chạy cho giải thuật thôi mà).

Em trình bày lại code mẫu đề số 2 thế này có được không ạ!

#include <stdio.h>
int main()
{
    int   a = 100,
          b =  200;
    printf("%d\n",a + b); // chú ý: phải có xuống dòng ở hàng cuối cùng
    return 0;
} 

Khi chấm BTC chỉ cần thay giá trị a,b (trong bài thi vòng loại la n) vào rồi biên dịch( em sài CodeBlock nó hiện ra thời gian chạy liền mà) thế là xong.

P/s: có gì không hợp lý anh góp ý luôn nha ! Thank !

Đúng rồi em. Cách chấm như em nói thì có 1 online judge trên mạng chấm theo kiểu này là topcoder. Mình viết phần giải thuật chính của chương trình, còn việc input/output là của hệ thống judge. Tuy nhiên có 1 hạn chế : Nếu làm theo ý em thì trình chấm của giám khảo phải "hiểu" code của em như thế nào thì mới chèn đc chứ ? Còn cách mà topcoder sử dụng là class, em sẽ code cho nó 1 cái class chứa lời giải theo mẫu. Như vậy mấy bạn nào chưa học OOP sẽ không làm được vì không biết class là gì.
Với lại đa số theo chuẩn là input => Process => output rồi em ạ Chỉ có mỗi topcoder là "khác người thôi", còn lại judge nào từ thế giới cho tới VN như AMM đều theo chuẩn đó nên mình phải theo

[09520668]

Các bạn cứ nhập xuất chuẩn màn hình là được, việc còn lại là của ban tổ chức mà, suy nghĩ làm gì cho mệt. Ví dụ chương trình bài 1: Bai1.zip
Cuộc thi này rất hay phải chi nó ra đời sớm hơn 1 năm nữa thì hay biết mấy, giờ ngại tham gia thi cử quá nên làm cổ vũ vậy

[08520001]

Tiêu chí để nhận xét đúng sai là bài làm đúng kết quả, và thời gian chạy nằm trong giới hạn cho phép.

tiêu chí chấm là thời gian chạy hả.

[08520522]

yêu cầu mấy anh chị K3 ko tham gia, để cho tụi nhỏ có cơ hội kiếm vé xem phim với gf!

K3 rồi nhưng thuật toán còn cùi mía lắm, với lại K3 cũng biết đi xem phim với gf...

[08520059]

Anh cho em hỏi tại sao ta không gán sẵn giá trị Input luôn khỏi cần nhập chi cho mất công kiểm tra thời gian chạy khó khăn( vì mình chỉ quan tâm thời gian chạy cho giải thuật thôi mà).


P/s: có gì không hợp lý anh góp ý luôn nha ! Thank !

Lỡ có 100 test thì ngồi nhập từng test một hả bạn. Chương trình chấm có sẵn nên không cần lo lắng về việc nhập test, thời gian chấm, chỉ việc code thuật toán cho "ngoan" là được rồi.

[10520567]

Cho em hỏi về mẫu code khi nộp bài chút !

Mà để mình ví dụ 2 bài mẫu cho các bạn nộp bài nhá

Đề: Xuất ra dòng chữ "Hello World !!! Welcome to UIT Olympiad Contest 2011 - Winter Season"
Input: không có
Output: "Hello World !!! Welcome to UIT Olympiad Contest 2011 - Winter Season"

#include <iostream>
using namespace std;
int main()
{
    cout << "Hello World !!! Welcome to UIT Olympiad Contest 2011 - Winter Season" << endl; //chú ý: phải có xuống hàng ở dòng cuối cùng
    return 0;
} 

Đề : Cho 2 số a và b, hãy tính tổng 2 số a và b
Input: Dòng 1 chứa 2 số a b, (0 <= a,b <= 1000)
Output: 1 dòng duy nhất chứa kết quả a + b

#include <stdio.h>
int main()
{
    scanf("%d%d",&a,&b);
    printf("%d\n",a + b); // chú ý: phải có xuống dòng ở hàng cuối cùng
    return 0;
} 

Tất cả các bài đều nhập xuất bằng standard stream thay vì file vì đề không có ghi tên file nhập xuất

Anh cho em hỏi tại sao ta không gán sẵn giá trị Input luôn khỏi cần nhập chi cho mất công kiểm tra thời gian chạy khó khăn( vì mình chỉ quan tâm thời gian chạy cho giải thuật thôi mà).

Em trình bày lại code mẫu đề số 2 thế này có được không ạ!

#include <stdio.h>
int main()
{
    int   a = 100,
          b =  200;
    printf("%d\n",a + b); // chú ý: phải có xuống dòng ở hàng cuối cùng
    return 0;
} 

Khi chấm BTC chỉ cần thay giá trị a,b (trong bài thi vòng loại la n) vào rồi biên dịch( em sài CodeBlock nó hiện ra thời gian chạy liền mà) thế là xong.

P/s: có gì không hợp lý anh góp ý luôn nha ! Thank !