Hỏi về competitive programming

Khac Cuong said:

e biết rồi , nhưng mà ở đây cái hàm sumbignumber trong mẫu nó dùng long thì làm sao lưu tổng của 2 số lớn tầm 10^1000 đc ạ

Click to expand...

• Its length is at least 6

maxpro92 said:

Có bài này mình vừa làm phỏng vấn xong. Mấy bác làm thử nhé.
Cho một dãy số từ 2 đến 1000000. Sắp xếp ước số nhỏ nhất khác 1 theo thứ tự từ lớn tới bé. Hỏi số thứ 240001 là số mấy?
VD: Ước số nhỏ nhất khác 1 của 9 là 3, 11 là 11, 25 là 5.

Click to expand...

nipevt said:

cái này là một dạng biến thể của sàng nguyên tố thôi.

Với mỗi số nguyên tố từ lớn đến bé đếm được nó là ước bé nhất của bao nhiêu số, rồi từ đó chạy qua các số nguyên tố từ lớn tới bé đến khi tìm ra được số thứ 240001.

Click to expand...

maxpro92 said:

Vấn đề là số nó lớn quá, chạy cũng mất thời gian kha khá.
Có khoảng 20ph để code và chạy ra kết quả.

Click to expand...

nipevt said:

sang nguyên tố đpt khoảng O(n log n) với n khoảng 1 triệu thì mất dưới 1s. để code ra kết quả xem sao.

mà kết quả phải là số 2 vì 2 là ước nhỏ nhất của cỡ 500k số mà nhỉ

Click to expand...

maxpro92 said:

Xếp theo thứ tự từ lớn đến bé mà bác.
Mà kết quả là số từ 2 đến 1000000 chứ không phải ước số nhé.
Nếu 2 số có cùng 1 ước số thì xếp theo thứ tự từ lớn đến bé.
VD: 2,4,6,8 đều có ước số là 2. Xếp thành 8,6,4,2.

Click to expand...

nipevt said:

nghĩa là sắp xếp các số theo ước số nhỏ nhất khác 1 của nó từ lớn đến bé? vậy dạng là như này:
999983 999979 999961 999959 999953 999931, ..., 999999 (ước nhỏ nhất là 3), ... ,3, , 1000000 (ước nhỏ nhất là 2), 999998,...,2 đúng không thím?

Click to expand...

maxpro92 said:

Đúng rồi.

Click to expand...

C++:

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 3;

int n = 1000000, k = 1, a[N] = {0};
bool p[N];

int main() {
    for (int i = 2; i <= n; ++i) {
        p[i] = true;
    }
    for (int i = 2; i <= n; ++i) {
        if (! p[i]) continue;
        a[i] = 1;
        for (int j = i + i; j <= n; j += i) {
            if (! p[j]) continue;
            p[j] = false;
            ++a[i];
        }
        //cerr << i << ' ' << a[i] << '\n';
        //a[i] = 1;
    }
    int divi;
    k = 240001;
    for (int i = n; i >= 2; --i) {
        if (! p[i]) continue;
        if (k >= a[i]) k -= a[i]; else {
            divi = i;
            break;
        }
        if (k == 0) {
            divi = i;
            break;
        }
    }
    if (k != 0) k = a[divi] - k;
    for (int i = 2; i <= n; ++i) {
        if (i % divi == 0) {
            if (k == 0) {
                cout << i << '\n';
                break;
            }
            --k;
        }
    }

    return 0;
}

Click to expand...

maxpro92 said:

Có bài này mình vừa làm phỏng vấn xong. Mấy bác làm thử nhé.
Cho một dãy số từ 2 đến 1000000. Sắp xếp các số đó theo ước số nhỏ nhất khác 1 từ lớn tới bé. Hỏi số thứ 240001 là số mấy?
VD: Ước số nhỏ nhất khác 1 của 9 là 3, 11 là 11, 25 là 5.

Click to expand...

tthixk said:

Cho hỏi tên cty với ) bài này code 20 phút khá căng đó.

Cách giải tốt nhất là tạo mảng chứa số nguyên tố rồi tính độ dài của từng thằng từ 2 tới sqrt(n), rồi suy ra vị trí cần tìm là bội số mấy, sau đó lấy thứ tự nhân ngược lại ước số nguyên tố kia là ra. Mấy cái công thức để tính thì khó ở chỗ phải loại trừ những thằng chia hết cho nhiều số.
- ví dụ n=1000000 thì 500000 thằng đầu tiên là bội của 2 (n div 2), tầm 300000 thằng tiếp theo là bội của 3 (n div 3 - n div 6), 100000 thằng tiếp theo là bội của 5 (n div 5 - n div 10 - n div 15 + n div 30)

Phần tricky của bài này là làm cách nào có đc mảng số nguyên tố 1 cách nhanh nhất. Cách làm tốt nhất là google rồi hardcode 1 mảng số nguyên tố từ 2 tới 1000. Mảng này tầm 200 số chứ ko nhiều.

độ phức tạp là tầm 200 lần lặp và phép toán div, chạy tầm 100ms là căng.

Click to expand...

maxpro92 said:

Một cty ở Nhật bác. Nếu bác quan tâm thì mình pm.
Bài test này có 10 câu, làm trong 60 phút. Như vậy trung bình 1 câu 6 phút.
Nhưng không cần phải làm hết. Câu này là câu thứ 7. Tùy theo tốc độ từng ng, mình nhắm là sẽ chỉ còn 15~30 phút cho câu này.
Mảng số nguyên tố thì chỉ cần tới 7 là đủ rồi.
Bác làm ra đáp án hộ em với.

Click to expand...

maxpro92 said:

Một cty ở Nhật bác. Nếu bác quan tâm thì mình pm.
Bài test này có 10 câu, làm trong 60 phút. Như vậy trung bình 1 câu 6 phút.
Nhưng không cần phải làm hết. Câu này là câu thứ 7. Tùy theo tốc độ từng ng, mình nhắm là sẽ chỉ còn 15~30 phút cho câu này.
Mảng số nguyên tố thì chỉ cần tới 7 là đủ rồi.
Bác làm ra đáp án hộ em với.

Click to expand...

tthixk said:

sry thím, tôi ngồi nghĩ lại thì vụ loại trừ mấy số chia hết cho nhiều số khó quá Ko áp dụng vào đc. Cách của thím ở trên kia là ok rồi.
Ở Nhật mà giải toán ko phải faang thì chắc rakuten hoặc line, chúc may mắn. Tưởng ở VN thì mình cũng muốn pv thử

Click to expand...