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

[09520019]

Vậy cái gì gây nên lỗi này anh ?

long long int không chứa nổi con số đó.
Long long int max = 2^63 - 1
unsigned long long int max = 2^64 - 1
Anh tính ra số đó bằng calculator của windows (Hỗ trợ số lớn)

ủa, sao máy mình chạy không được code này bạn (kể cả n = 2). Mình debug thấy biến k chả bao giờ tăng cả --> lặp mãi không thôi. Mình cũng không hiểu rõ thuật toan của bạn lắm. Bạn vui lòng giải thích rõ hơn tí cho mình học tập với được không.
Cảm ơn bạn.

Bạn tìm trên forum mình có code sàn số nguyên tố rồi. Mình không post code đó nữa

3. Đá nhỏ: ủa, 1203 thì ra 3021 bug sao anh ????

Bạn trẻ nào dùng if (n % 10 != 0) cout .... thì sẽ dính

1 Lời khuyên cho bài số 4: Khi bạn đi thi Olympic cá nhân, với bài số 1 2 3 ai cũng có thể làm đc, bài số 4 ko ai làm đc thì tốt nhất mình cứ.....vét cạn, hơn đc vài điểm là hơn hạng rồi. Nhưng điều này ko áp dụng đc cho IOI / ACM

[10520272]

Bài 1 của mình. >450k 1s.

#include <stdio.h>
int main()
{
    long int n,i,j,k,l;
    //do scanf("%ld",&n);while ((n<=0)||(n>1000));
    n=450000;
    long int m[n];
    m[0]=2;
    k=0;
    for (i=3;k<=n-1;i++)
        for (j=0;;j++)
        {
            l=(m[j]*m[j]);
            if (l>i)
            {
                k++;
                m[k]=i;
                break;
            }
            if (i%m[j]==0) break;
        }
    printf("So nguyen to thu %ld la: %ld",n,m[k-1]);
} 

ủa, sao máy mình chạy không được code này bạn (kể cả n = 2). Mình debug thấy biến k chả bao giờ tăng cả --> lặp mãi không thôi. Mình cũng không hiểu rõ thuật toan của bạn lắm. Bạn vui lòng giải thích rõ hơn tí cho mình học tập với được không.
Cảm ơn bạn.

[11520132]

Kết quả đúng không ?
Output = 66666666666666666666666666666666

Công thức nhìn có vẻ đúng 2*(N/3) + (N%3)/2

N dư 1 thì N%3 / 2 = 0
N dư 2 thì N%3 / 2 = 1

OK => Accepted

Vậy cái gì gây nên lỗi này anh ?

[10520516]

Anh Châu nói đúng, hehe. Bạn trẻ nên thận trọng.
Bài 3 dùng chuổi ---> dính chưởng....Anh Châu kiếm bug hay thiệt

[09520019]

[ATTACH=CONFIG]1549[/ATTACH]
Nhưng mà nó tính được là sao anh.
Vấn đề này em cũng không hiểu nữa. Em thầy nó tính được nên em nghĩ nó với tới thôi.
mà em cũng không biết nó tính đúng hay sai nữa. Tại cứ nhập thêm số 9 vào tới khi nó không tính được nữa.
Anh dùng từ "láo" xúc phạm em đó.

Kết quả đúng không ?
Output = 66666666666666666666666666666666

Công thức nhìn có vẻ đúng 2*(N/3) + (N%3)/2

N dư 1 thì N%3 / 2 = 0
N dư 2 thì N%3 / 2 = 1

OK => Accepted

[10520272]

Anh dùng từ "láo" xúc phạm em đó.

Vô tình thôi mà bạn, đừng giận.

Không bị dính cái nào .

Chúc mừng nhá.

[11520132]

1. Bạn nào làm đc 200k < 1s post lên học tập nào.
2. May mà mình để long long tất --> OK (mừng quá).
3. Đá nhỏ: ủa, 1203 thì ra 3021 bug sao anh ????
Đá lớn: Có khởi tạo bằng 0, mừng quá, cái này là hên chứ không hề để ý.
4. Em dùng công thức Số số chia hết cho 3 <= N là 2*(N/3) + (N%3)/2 được không anh, chứng minh cả buổi chiều :x

Bài 1 của mình. >450k 1s.

#include <stdio.h>
int main()
{
    long int n,i,j,k,l;
    //do scanf("%ld",&n);while ((n<=0)||(n>1000));
    n=450000;
    long int m[n];
    m[0]=2;
    k=0;
    for (i=3;k<=n-1;i++)
        for (j=0;;j++)
        {
            l=(m[j]*m[j]);
            if (l>i)
            {
                k++;
                m[k]=i;
                break;
            }
            if (i%m[j]==0) break;
        }
    printf("So nguyen to thu %ld la: %ld",n,m[k-1]);
} 

[11520132]

Mà tưởng 12h đêm mới hết hạn chớ ai dè 12h trưa ^_^

Đây là 1 bug nho nhỏ:

Bài 1: không có gì để nói
Bài 2: input = 999999,output có âm không ?
bài 3 : Biển lặng dễ đắm thuyền
Tảng đá nhỏ: input 1203 ,output = ?
Tảng đá to: input = 0, output = ?
Bài 4: Không có gì để nói.

Unofficial Solution :
Bài 1: các bạn cài 1 hàm isprime đơn giản là được. Nếu siêng hơn có thể dùng Eratosthenes
Bài 2: công thức : n * (n + 1) / 2, chú ý n * n có thể tràn nếu để int
Bài 3: bài đảo số đơn giản, có thể dùng long long int hoặc string tùy ý, nhưng lưu ý trường hợp n = 0
Bài 4: công thức : res = 2 * (n / 3), nếu n % 3 dư 2 thì res = res + 1.

Không bị dính cái nào .

[10520272]

Em đừng có nói láo. 999999999999999999999999999999999999999999999 vượt khoảng long long int rồi.

Mà tưởng 12h đêm mới hết hạn chớ ai dè 12h trưa ^_^

Đây là 1 bug nho nhỏ:

Bài 1: không có gì để nói
Bài 2: input = 999999,output có âm không ?
bài 3 : Biển lặng dễ đắm thuyền
Tảng đá nhỏ: input 1203 ,output = ?
Tảng đá to: input = 0, output = ?
Bài 4: Không có gì để nói.

1. Bạn nào làm đc 200k < 1s post lên học tập nào.
2. May mà mình để long long tất --> OK (mừng quá).
3. Đá nhỏ: ủa, 1203 thì ra 3021 bug sao anh ????
Đá lớn: Có khởi tạo bằng 0, mừng quá, cái này là hên chứ không hề để ý.
4. Em dùng công thức Số số chia hết cho 3 <= N là 2*(N/3) + (N%3)/2 được không anh, chứng minh cả buổi chiều :x

[10520101]

Đây là 1 bug nho nhỏ:

Bài 1: không có gì để nói
Bài 2: input = 999999,output có âm không ?
bài 3 : Biển lặng dễ đắm thuyền
Tảng đá nhỏ: input 1203 ,output = ?
Tảng đá to: input = 0, output = ?
Bài 4: Không có gì để nói.

Bài 2: input = 999999, output chưa có thấy âm
bài 3: input 1203, output vẫn bình thường mà anh.
input=0 cái này chưa từng để ý đến

[11520132]

Em đừng có nói láo. 999999999999999999999999999999999999999999999 vượt khoảng long long int rồi.

Mà tưởng 12h đêm mới hết hạn chớ ai dè 12h trưa ^_^

Đây là 1 bug nho nhỏ:
bài 3 : Biển lặng dễ đắm thuyền
Tảng đá nhỏ: input 1203 ,output = ?
Tảng đá to: input = 0, output = ?

Untitled-1.jpg
Nhưng mà nó tính được là sao anh.
Vấn đề này em cũng không hiểu nữa. Em thầy nó tính được nên em nghĩ nó với tới thôi.
mà em cũng không biết nó tính đúng hay sai nữa. Tại cứ nhập thêm số 9 vào tới khi nó không tính được nữa.
Anh dùng từ "láo" xúc phạm em đó.

[09520019]

long long int anh. thật ra thì nếu dùng vòng lặp thì không chạy nổi tới đó

Em đừng có nói láo. 999999999999999999999999999999999999999999999 vượt khoảng long long int rồi.

Mà tưởng 12h đêm mới hết hạn chớ ai dè 12h trưa ^_^

Đây là 1 bug nho nhỏ:

Bài 1: không có gì để nói
Bài 2: input = 999999,output có âm không ?
bài 3 : Biển lặng dễ đắm thuyền
Tảng đá nhỏ: input 1203 ,output = ?
Tảng đá to: input = 0, output = ?
Bài 4: Không có gì để nói.

Unofficial Solution :
Bài 1: các bạn cài 1 hàm isprime đơn giản là được. Nếu siêng hơn có thể dùng Eratosthenes
Bài 2: công thức : n * (n + 1) / 2, chú ý n * n có thể tràn nếu để int
Bài 3: bài đảo số đơn giản, có thể dùng long long int hoặc string tùy ý, nhưng lưu ý trường hợp n = 0
Bài 4: công thức : res = 2 * (n / 3), nếu n % 3 dư 2 thì res = res + 1.

Bài 4 nếu phân tích chúng ta sẽ nhận ra điều sau đây.
Thứ nhất : dấu hiệu nhận biết chia hết cho 3 là tổng các chữ số phải chia hết cho 3
Thứ 2: tính chia hết cho 3 của số thứ k của dãy (gọi là f(k)) sẽ cùng tính chia hết cho 3 của (1 + 2 + 3 + .... + k)

Nhận thấy : với 3 số tự nhiên liên tiếp lần lượt chia cho 3 sẽ dư 1, 2 và 0 ( 1 chia 3 dư 1, 2 chia 3 dư 2, 3 chia 3 dư 0, 4 chia 3 dư 1,....)
Mà f(k) = (1 + 2 + 3 + 4 + 5 + 6 + .....) % 3, bằng cách gom nhóm, ta gom những số chia hết cho 1 và 2 với nhau, ta được
f(k) = [(1 + 2) + 3 + (4 + 5) + 6 + .....k] % 3

Nếu kết thúc là 1 số chia 3 dư 1: f(3x + 1) = [(1 + 2) + 3 + (4 + 5) + 6 +.... + (3x + 1)] % 3 dư 1
Nếu kết thúc là 1 số chia 3 dư 2: f(3x + 2) = f(3x + 1) % 3 + (3x + 2) % 3 = (1 + 2) % 3 = 0
Nếu kết thúc là 1 số chia 3 dư 0: f(3x + 3) = f(3x + 2) % 3 + (3x + 3) % 3 = 0

=> dãy có tính chất: 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 ....(Với 0 là số cần tìm)
=> bộ 3 số liên tiếp trong dãy có độ dài n = n / 3
=> Mỗi bộ 3 số liên tiếp sẽ có 2 số 0 => res = 2 * (n / 3)
Trường hợp thừa ra ở cuối, có 2 TH thừa:
[1 0 0 1 0 0 1 0 0 1 0 0..... 1] => (n % 3 dư 1 , không xét)
[1 0 0 1 0 0 1 0 0 1 0 0..... 1 0] => (n % 3 dư 2, tăng kết quả lên 1)
[1 0 0 1 0 0 1 0 0 1 0 0..... 1 0 0] => (không xét vì đủ số bộ 3)

Từ đó suy ra: res = 2 * (n / 3) , if ( n % 3 == 2) ++res;

[10520272]

Vào lúc 11h59 phút ngày mai mình sẽ post cho mấy bạn vài bug bất ngờ. Hy vọng trong vòng 60 giây các bạn có thể sửa bài kịp và nộp ) Sẵn tối mai post luôn cái solution của mình luôn :P (ko phải solution chính thức của BGK nhá)
(PS: Anh V.An kỳ trước nợ quà Thailand em kỳ này nợ thêm quà bug em phát hiện nha ) => 2 món rồi )
PS2: gợi ý nho nhỏ cho mấy bạn khác: nếu mấy bạn làm được bài 4 mà ko đc full điểm thì chắc chắn là bug ko nằm trong bài 4)

Chuyển thành 11:59 trưa đi anh.

long long int anh. thật ra thì nếu dùng vòng lặp thì không chạy nổi tới đó

Thanks bạn.

[11520132]

bài 4 bạn dùng kiểu dữ liệu gì mà cho nhập số lớn thế ?
Thế khi nào thì có kết quả ạ.

long long int anh. thật ra thì nếu dùng vòng lặp thì không chạy nổi tới đó

[08520522]

Thông cáo với các bạn là : Anh Cao Văn An là người lo lắng chấm bài cho các bạn, nó ngồi nó than là nó sửa từng bài vì các bạn hok biết cách thi kiểu ACM , tội nó ghê gớm, quá trời bài nộp mà nó ngồi sửa từng bài... )
Mấy nay nick của Quốc trên diễn đàn có 1 số bài trả lời là của An , Quốc có đưa nick Diễn đàn của Quốc cho An sử dụng ^^
Các bạn có thể liên hệ Quốc ở sđt : 01689942711 và số Điện thoại của siêu nhân An0925920347

Nguyễn Việt Quốc không phụ giúp à ^_^