Ví dụ 2 trong đề:

2 trạm thu: 1 999999 K = 1

Khoảng cách trên đường tròn:

• Giữa 1 và 999999 = 2

Vậy chỉ cần R = 1.

#include <bits/stdc++.h>

using namespace std;

const int CIRCLE = 1000000;   // Chu vi đường tròn

int n, k;

vectora;

// Hàm kiểm tra: với phạm vi phát R, có thể phủ hết N trạm thu bằng ≤ K trạm phát không?

bool check(int R) {

    int need;  // số trạm phát cần dùng

    // Tạo mảng 2N để "trải phẳng" đường tròn thành đường thẳng

    vectorb(2 * n);

    for (int i = 0; i < n; i++) {

        b[i] = a[i];

        b[i + n] = a[i] + CIRCLE;  // điểm phía sau được cộng thêm chu vi

    }

    // Thử mỗi trạm thu làm điểm xuất phát

    for (int start = 0; start < n; start++) {

        need = 1;  // bắt đầu với 1 trạm phát

        int cover = b[start] + 2 * R;  // vùng phủ tối đa của trạm phát đầu tiên

        // Duyệt các trạm thu tiếp theo

        for (int i = start + 1; i < start + n; i++) {

            if (b[i] > cover) { 

                // Trạm thu này nằm ngoài vùng phủ → cần thêm 1 trạm phát

                need++;

                cover = b[i] + 2 * R;  // cập nhật vùng phủ mới

            }

        }

        if (need

    }

    return false;  // thử mọi điểm xuất phát đều cần > K trạm phát

}

int main() {

    freopen("tps.inp", "r", stdin);

    freopen("tps.out", "w", stdout);

    cin >> n;

    a.resize(n);

    for (int i = 0; i < n; i++) cin >> a[i];

    cin >> k;

    sort(a.begin(), a.end());  // sắp xếp vị trí trạm thu

    // Tìm kiếm nhị phân trên đáp án R

    int left = 0, right = CIRCLE;  // R nằm trong [0, 1e6]

    while (right > left + 1) {

        int mid = (left + right) / 2;

        if (check(mid)) right = mid;  // R này đủ → thử nhỏ hơn

        else left = mid;              // R này chưa đủ → tăng lên

    }

    cout << right;

    return 0;

}

//////////////////////////////////////////

TỔNG QUAN ĐỀ THI

Chú ý: Dấu * được thay thế bởi PAS, CPP, PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C/C++ hoặc Python.

Bài I (5,0 điểm)                                              Mật khẩu

Nam là người yêu thích các số nguyên tố, cậu thường tìm ra những số nguyên tố có tính chất đặc biệt để tạo mật khẩu cho các tài khoản facebook, zalo, email … của mình. Nam đã phát hiện ra những số nguyên tố mà tổng các chữ số của nó cũng là số nguyên tố. Xét các ví dụ sau:

• Số 17 có tổng các chữ số bằng 8 không phải là số nguyên tố, vì vậy Nam không thể chọn 17 làm mật khẩu.
• Số 32 có tổng các chữ số bằng 5 là một số nguyên tố nhưng 32 không phải là số nguyên tố, vì vậy Nam không thể chọn 32 làm mật khẩu.
• Số 67 là số nguyên tố và tổng các chữ số bằng 13 là một số nguyên tố, vì vậy Nam có thể chọn 67 làm mật khẩu.

Yêu cầu: Cho hai số l, r hãy cho biết trong đoạn từ l đến r có những số nguyên tố nào Nam có thể chọn để làm mật khẩu cho các tài khoản của mình.

Dữ liệu vào từ tệp văn bản password.inp:

Gồm hai số nguyên dương l và r trên cùng 1 dòng (1 ≤ l ≤ r ≤ 10⁷ ). Dữ liệu đảm bảo bài toán luôn có nghiệm.

Kết quả ghi ra tệp văn bản password.out: Gồm các số nguyên tố từ l đến r. Các số trên cùng một dòng và in theo thứ tự tăng dần.

Ví dụ:

Bài II (3,0 điểm)                                             Mật mã

Một mật thư chứa mật mã bí ẩn được tạo ra là một xâu kí tự chỉ gồm các chữ số và các kí tự in thường. Mật mã bí ẩn là số lượng các số nguyên phân biệt xuất hiện trong thư.

Ví dụ: Với mật thư as00023dkrf23smk1asd23sam09aa9 chứa 3 số nguyên phân biệt 23, 1, 9. Nên mật mã là 3.

Yêu cầu: Hãy lập trình đưa ra mật mã bí ẩn.

Dữ liệu vào từ tệp văn bản mm.inp:Một xâu (độ dài xâu  100) gồm các chữ số và các kí tự in thường. Tất cả các số nguyên trong xâu có nhiều nhất 3 chữ số.

Kết quả ghi ra tệp văn bản mm.out:Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Bài III (3,0 điểm)                                           Virus

Flashback là một loại virus máy tính sinh sản rất nhanh khi gặp môi trường thuận lợi và là một loại virus nguy hiểm, có tốc độ lây lan nhanh trong môi trường mạng. Flashback lần đầu tiên được phát hiện vào năm 2011 bởi công ty diệt virus Intego dưới dạng một bản cài đặt flash giả và chúng sinh sản theo quy luật sau:

• · Ngày đầu tiên (ngày thứ 0) có n cá thể ở mức 1.
• · Ở mỗi ngày tiếp theo, mỗi cá thể mức i sinh sản ra i cá thể mức 1, các cá thể mới sẽ sinh sôi, phát triển từ ngày hôm sau.
• · Bản thân cá thể thứ i sẽ phát triển thành mức i+1 và chu kỳ phát triển trong ngày chấm dứt.

Yêu cầu: Hãy xác định sau k ngày trong môi trường mạng có bao nhiêu cá thể.

Dữ liệu vào từ tệp văn bản flashback.inp:

Gồm một dòng chứa hai số nguyên n và k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 10⁵ ).

Kết quả ghi ra tệp văn bản flashback.out: 

Một số nguyên duy nhất là số dư của kết quả tìm được chia cho 10⁹ +7.

Ví dụ:

Bài IV (5,0 điểm)                                           Vườn cây

Một mảnh vườn hình chữ nhật được chia thành các ô đất nhỏ gồm M hàng, N cột để ươm các loại cây giống khác nhau. Độ dài cạnh mỗi ô được xem là 1 đơn vị chiều dài, mỗi ô sẽ ươm một trong số các loại cây cần ươm. Để phân vùng các loại cây giống khác nhau trong khu vườn, người làm vườn tiến hành căng dây để phân biệt theo các đường ranh giới các ô đất. Dây được căng xung quanh mảnh vườn và cạnh của ô nếu 2 ô chứa cạnh đó ươm hai loại cây khác nhau.

Yêu cầu: Tính độ dài của dây cần dùng để khoanh vùng các loại cây trong mảnh vườn theo yêu cầu. 

Dữ liệu vào từ tệp văn bản vuoncay.inp:

• Dòng đầu chứa 2 số nguyên dương M, N (0 < M, N ≤ 100). 

• M dòng tiếp theo mỗi dòng chứa N số nguyên dương. Giá trị ở dòng thứ i, cột thứ j là a_ij với (1 ≤ i ≤ M; 1 ≤ j ≤ N và 1 ≤ a_ij ≤ 100) để mô tả loại cây được ươm tại ô ở hàng i cột j của mảnh vườn (các giá trị giống nhau để chỉ cùng một loại cây). 

Kết quả ghi ra tệp văn bản vuoncay.out:

Chứa một số nguyên dương duy nhất cho biết chiều dài của dây được dùng khoanh vùng theo yêu cầu của người làm vườn. 

Ví dụ:

Bài V (4,0 điểm)                                             Trạm phát sóng

Các trạm thu, phát sóng viễn thông của thành phố được đặt trên một đường tròn. Đường tròn này được chia thành 10⁶ điểm cách đều nhau theo chiều kim đồng hồ. Một vị trí trên đường tròn được chọn là mốc . Có  trạm thu sóng được đánh thứ tự từ 1 đến , trạm thứ  đặt ở vị trí  ).

Thành phố dự kiến sẽ đầu tư  trạm phát sóng với phạm vi phát như nhau. Tuy nhiên, một trạm phát sóng với phạm vi phát càng dài thì chi phí càng cao. Vì vậy, thành phố cần tính toán để đầu tư các trạm phát sóng có phạm vi phát ngắn nhất và phải đảm bảo các trạm thu sóng đều nhận được tín hiệu.

Khi một trạm phát sóng có phạm vi phát là  thì các trạm thu sóng trong khoảng cách  theo cả hai chiều kim đồng hồ đều nhận được tín hiệu. Ví dụ: Trạm phát sóng tại vị trí 3 với phạm vi phát 1 thì cả trạm thu sóng ở vị trí 2 và 4 đều nhận được tín hiệu.

Yêu cầu: Tìm phạm vi phát ngắn nhất của  trạm phát sóng sẽ đầu tư để  trạm thu sóng đều nhận được tín hiệu.

Dữ liệu vào từ tệp văn bản tps.inp:

- Dòng đầu tiên chứa số nguyên dương  ().

- Dòng thứ  trong  dòng tiếp theo chứa một số nguyên  là vị trí trạm thu sóng thứ . Không có hai trạm nào cùng vị trí (0 £ ).

- Dòng cuối cùng chứa số nguyên  là số trạm phát sóng (). Chú ý, vị trí trạm phát có thể được đặt cùng vị trí của một trạm thu nào đó.

Kết quả ghi ra tệp văn bản tps.out:  Số nguyên duy nhất là phạm vi phát sóng ngắn nhất của  trạm phát.

Ví dụ:

……………Hết……………

1. Trong hình học chuẩn: có tồn tại hình tròn chia đều thành 10^6 cung bằng nhau không?

Có. Và chuyện này… hoàn toàn bình thường.

Trong hình học phẳng:

• Hình tròn bất kỳ có:

\mathrm{chu\ vi}=2\pi R

• Nếu bạn muốn chia đường tròn thành n cung bằng nhau, mỗi cung sẽ có:

\mathrm{góc\ ở\ tâm}=\frac{2\pi }{n}

• Ứng với mỗi góc như vậy, bạn có một điểm trên đường tròn.

Vậy với n=10^6, chỉ cần:

• Chọn một bán kính R>0 bất kỳ (1, 10, 2025, \sqrt{2}, gì cũng được).
• Từ một điểm mốc, quay lần lượt các góc:

0,\ \frac{2\pi }{10^6},\ \frac{2\pi \cdot 2}{10^6},\ \dots ,\ \frac{2\pi \cdot (10^6-1)}{10^6}

• Bạn thu được đúng 10^6 điểm trên đường tròn, các cung tròn giữa hai điểm liên tiếp có cùng độ dài vì góc bằng nhau.

Không có yêu cầu nào nói:

• Chu vi phải là số “đẹp”.
• Hay độ dài mỗi cung phải là số hữu tỉ, hay đo được bằng thước chia mm.

Toán học không cần “dụng cụ đo” chính xác, chỉ cần tồn tại về mặt logic. Và nó hoàn toàn tồn tại.

2. Chỗ trực giác dễ gây hiểu lầm của bạn

Bạn đang nghĩ theo kiểu:

“Làm sao chia một cái gì đó có độ dài 2\pi R thành đúng 10^6 đoạn bằng nhau khi \pi là số vô tỉ?”

Ý ngầm là: “Làm sao dùng đơn vị đo hữu tỉ (cm, mm) mà chia được?”

Nhưng toán học không cần độ dài từng cung phải là số hữu tỉ hay đo được chính xác bằng dụng cụ vật lý.

• Nếu chu vi là 2\pi R, thì độ dài mỗi cung là:

\ell =\frac{2\pi R}{10^6}

• Dù \ell có là số vô tỉ, điều đó chẳng cản trở việc nó tồn tại và tất cả các cung đều bằng nhau.

Ta xác định chúng bằng góc ở tâm, không cần thước đo.

3. Còn trong bài toán lập trình: “chia đều cho 10^6 điểm” nghĩa là gì?

Trong đề bài, người ta còn làm mọi thứ dễ hơn nữa:

• Không làm hình tròn liên tục, mà chỉ làm vòng tròn rời rạc với 10^6 điểm.
• Tức là:

• Có tập các vị trí:

0,1,2,\dots ,10^6-1

• Quy ước là chúng nằm trên một vòng tròn và “cách đều nhau” theo nghĩa là khoảng cách giữa hai vị trí kề nhau = 1 đơn vị rời rạc.
• Không cần biết chu vi là bao nhiêu, bán kính là bao nhiêu.

Trong lập trình, ta chỉ quan tâm:

• Khoảng cách cung tròn giữa vị trí x và y là:

d(x,y)=\min (|x-y|,\ 10^6-|x-y|)

• Chứ không ai bắt bạn đi đo độ dài thật.

Câu “chia đều cho 10^6 điểm” trong đề là mô tả cấu trúc, không phải yêu cầu vật lý.

4. Vậy câu hỏi của bạn: “Liệu có thật sự tồn tại hình tròn như thế không?”

Trả lời ngắn gọn:

• Trong hình học:
  Có. Bất kỳ hình tròn nào cũng có thể được chia thành 10^6 cung bằng nhau bằng cách dùng góc ở tâm 2\pi /10^6. Không có mâu thuẫn nào.
• Trong mô hình rời rạc (bài lập trình):
  Ta chỉ giả sử có vòng tròn với 10^6 điểm đánh số 0 đến 10^6-1. Đây là mô hình toán học, không cần “vẽ ngoài đời”. Nên càng không có mâu thuẫn.

Sự “lạ” của bạn xuất phát từ việc vô thức yêu cầu:

“Chu vi phải chia được thành các đoạn đo được đẹp bằng đơn vị thực tế.”

Nhưng toán học thì không bị ràng buộc bởi “dụng cụ đo” như vậy.

1. “Chu vi hình tròn” trong toán học liên tục

Chu vi thật của hình tròn là:

C=2\pi R

• \pi là số vô tỉ
• Vì vậy không máy tính nào có thể biểu diễn chính xác chu vi
• Máy tính chỉ có thể xấp xỉ bằng số thực dấu phẩy động

👉 Kết luận đúng:

Máy tính không thể tính chính xác tuyệt đối chu vi hình tròn vì \pi là vô tỉ.

👉 Nhưng kết luận sai:

“Máy tính không thể tìm ra sai số nhỏ nhất của chu vi hình tròn.”

Vì “sai số nhỏ nhất” không tồn tại trong toán học, chứ không phải vì máy tính yếu.

🌟 2. Vì sao “sai số nhỏ nhất” không tồn tại?

Giả sử bạn muốn xấp xỉ chu vi:

C=2\pi R

Bạn có thể dùng:

• 3.14
• 3.141
• 3.1415
• 3.14159
• 3.14159265358979
• …

Bạn luôn có thể tăng số chữ số thập phân → sai số giảm mãi, nhưng không bao giờ đạt 0.

Toán học gọi đây là:

Không tồn tại sai số nhỏ nhất, vì với bất kỳ sai số ε > 0, ta luôn có thể tìm được xấp xỉ tốt hơn.

Vậy nên không phải máy tính không làm được, mà là bản thân bài toán không có “sai số nhỏ nhất” để tìm.

🌟 3. Nhưng bài toán “trạm phát sóng” KHÔNG liên quan đến chu vi thật

Đề bài không yêu cầu:

• tính chu vi thật
• tính độ dài cung thật
• tính bán kính thật
• tính sai số thật

Nó chỉ dùng một mô hình rời rạc:

• Có 10^6 điểm đánh số 0 → 10^6-1
• Khoảng cách giữa hai điểm là số nguyên
• Không có chu vi thật
• Không có bán kính thật
• Không có độ dài cung thật

👉 Vì vậy không có sai số nào để tính.

Đây là bài toán rời rạc, không phải hình học thực.

/////////////////////////

HƯỚNG DẪN CHẤM MÔN TIN HỌC

Bài I. Mật khẩu (Số học) (5,0 điểm)

Thuật toán đề xuất:

              Duyệt các số x = l ® r, kiểm tra x có phải là số đặc biệt mà Nam có thể nhận làm mật khẩu hay không.

              Cần sử dụng sàng nguyên tố để tăng tốc độ kiểm tra x và tổng chữ số của x có phải là số nguyên tố hay không.

Chương trình minh hoạ bằng ngôn ngữ lập trình C++:

#include<bits/stdc++.h>

#define N 10000000

using namespace std;

int nt[N];

int l, r;

void sangnt(int n)

{

              fill(nt + 2, nt + n + 1, 1);

              for( int i = 2; i*i

                           if (nt[i] == 1)

                                         for( int j = i*i; j

}

Int tongcs( int x)

{

              int s = 0;

              While( x > 0)

              {

                           s += x%10;

                           x /= 10;

              }

              return s;

}

int main()

{

              freopen(“password.inp”,”r”, stdin);

              freopen(“password.out”,”r”, stdout);

              cin >> l >> r;

              sangnt(r);

              for( int x = 1; x

                           if (nt[x] == 1 && nt[tongcs(x)] == 1)

                                         cout << x << “ “;

              return 0;

}

Bài II. Mật mã (Duyệt) (3,0 điểm)

Thuật toán đề xuất:

              Duyệt xâu, tạo ra các xâu con chứa các chữ số có thể lưu vào mảng hoặc set để đếm số phần tử khác nhau.

Chương trình minh hoạ bằng ngôn ngữ lập trình C++:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1001;

string s;

int imam[MAXN];

int main()

{

              ios::sync_with_stdio(false);

              cin.tie(nullptr);

               if (fopen("mm.inp", "r"))

              {

                           freopen("mm.inp", "r", stdin);

                           freopen("mm.out", "w", stdout);

              }

              cin >> s;

              for (int i = 0; i < (int)s.size(); i++)

{

                           if (s[i] >= 'a' && s[i] <= 'z') continue;

                           int broj = 0;

                           int j = i;

                           for (; j < (int)s.size() && s[j] >= '0' && s[j] <= '9'; j++)

{

                                         broj *= 10;

                                         broj += s[j] - '0';

                           }

                            imam[broj] = 1;

                            i = j - 1;

              }

              int rj = 0;

               for (int i = 0; i < MAXN; i++)

{

                           rj += imam[i];

              }

              cout << rj << endl;

              return 0;

}

Bài III. Virus (Quy hoạch động) (3,0 điểm)

Thuật toán đề xuất:

              Tạo một dãy fibonaci như sau: bảng 1

              Tiến hành khảo sát qua từng ngày phát triển của virus với ngày thứ 0 là n các thể virus: bảng 2

              Qua khảo sát sau mỗi ngày số virus ở các mức (level) = một số fibonaci nhân với n.

              Các số fibonaci sau ngày thứ k sẽ là các số fibonaci ở vị trí chẵn (các ô được bôi màu ở bảng 1 trừ số fibonaci đầu tiên bằng 1 ở vị trí lẻ).

              Vậy ý tưởng giải bài toán là tính tổng các số fibonaci ở vị trí chẵn và cộng thêm số thứ nhất cho đến khi đủ k ngày, sau đó kết quả bài toán bằng tổng vừa tính nhân với n.

Chương trình minh hoạ bằng ngôn ngữ lập trình C++:

#include<bits/stdc++.h>

#define K 200000

#define MOD 10000000007

#define ll long long

using namespace std;

ll F[K + 2], ans;

int nt[N];

int n, k;

int main()

{

              freopen(“flashback.inp”,”r”, stdin);

              freopen(“flashback.out”,”r”, stdout);

              cin >> n >> k;

              F[1] = F[2] = 1;

              ans = 2;

              for(int i = 3; i

              {

                           F[i] = (F[i-1] + F[i-2])%MOD;

                           if  (i % 2 == 0) ans = (ans + F[i]) % MOD;

              }

              Cout << (ans * n) % MOD;

              return 0;

}

Bài IV. Vườn cây (Duyệt bằng đệ qui) (5,0 điểm)

Thuật toán đề xuất:

              Xây dựng một hàm backtrack(u, v) thể hiện đang ở tại ô (u, v):

              Xét ô (u₁, v₁) kề với (u, v):

• Một đoạn dây được ngăn cách giữa hai ô (u₁, v₁) và (u, v) nếu thoả mãn những điều kiện sau:

+ Ô (u₁, v₁) chưa đi qua;

+ Hai ô (u₁, v₁) và (u, v) có giá trị khác nhau.

• Nếu 2 ô (u₁, v₁) và (u, v) thoả mãn thì sẽ tăng kết quả 1 đơn vị. Sau đó đánh dấu ô (u, v) đã đi qua bằng giá trị -1.
• Để thực hiện tiếp tục đi từ ô (u, v) sang ô (u₁, v₁) kề cạnh nhau thì ô (u₁, v₁) phải thoả mãn những điều kiện sau:

+ Ô (u₁, v₁) phải nằm trong bảng;

+ Ô (u₁, v₁) là ô chưa đi qua;

+ Hai ô (u₁, v₁) và (u, v) có giá trị giống nhau.

• Nếu ô (u₁, v₁) thoả mãn các điều kiện trên thì sẽ gọi đệ qui backtrack(u₁, v₁) để đi đến ô (u₁, v₁).

Trong hàm main(), sau khi đọc dữ liệu cho mảng a[i][j], thì duyệt lại mảng a[i][j]. Nếu a[i][j] > 0 thì có nghĩa là ô (i,j) chưa đi qua (vì nếu a[i][j] = -1 thì đã đi qua), khi đó sẽ gọi hàm backtrack(i, j)  để thực hiện đi từ ô này.

Chương trình minh hoạ bằng ngôn ngữ lập trình C++:

#include<bits/stdc++.h>

#define N 100

using namespace std;

int tx[ ] = {-1, 0, 1, 0};

int ty[ ] = {0, 1, 0, -1};

int a[N + 3] [N + 3];

int m, n, ans;

bool insize( int u, int v)

{

              return (1

}

void backtrack(int u, int v)

{

              for (int k = 0; k < 4; k++)

              {

                           int u1 = u + tx[k], v1 = v + ty[k];

                           if (a[u1][v1] != -1 && a[u1][v1] != a[u][v]   ans++;

              }

              a[u][v] = -1;

              for (int k = 0; k < 4; k++)

              {

                           int u1 = u + tx[k], v1 = v + ty[k];

                           if (insize(u1, v1) && a[u1][v1] != -1 && a[u1][v1] = = a[u][v]   backtrack(u1, v1);

              }

}

int main()

{

              freopen(“vuoncay.inp”,”r”, stdin);

              freopen(“vuoncay.out”,”r”, stdout);

              cin >> m >> n;

              for (int i = 0; i

                           for (int j = 0; j> a[i][j];

              for (int i = 0; i

                           for (int j = 0; j

                                         if (a[i][j] > 0)  backtrack(i, j);

              cout << ans;

              return 0;

}

Bài V. Trạm phát sóng (Tìm kiếm nhị phân) (4,0 điểm)

Thuật toán đề xuất:

Dùng thuật toán tìm kiếm nhị phân.

-   Sắp xếp dãy vị trí  trạm thu sóng theo thứ tự tăng dần.

-    Thực hiện tìm kiếm nhị phân giá trị khoảng cách  để tính số trạm phát sóng cần thiết nếu khoảng cách tối đacho phép là .

Chương trình minh hoạ bằng ngôn ngữ lập trình C++:

#include<bits/stdc++.h>

using namespace std;

const int maxN=1010;

const int chu_vi=999999;

int n, k,kq=1000000;

int a[maxN];

void docdl()

{

cin>>n;

              for (int i=1; i>a[i];

              sort(a+1, a+n+1);

              cin>>k;

}

int kt(int x)

{

              int best=n;

              int duongkinh=x*2;

               int xp=1;

              while (xp

{

                           int cnt=1;

                           int kt=a[xp];

                           int i=xp+1;

                           while(i

{

                                        if (a[i]>kt)

{

                                                      cnt++;

                                                      kt=a[i]+duongkinh;

                           }

                           i++;

                           }

                           best=min(best,cnt);

                           xp++;

              }

              return best;

}

void xuli()

{

              int l=-1;

              int r=1000000;

              while (r>l+1)

{

                           int x=(l+r)/2;

                           if (kt(x)>k) {l=x;} else r=x;

              }

              cout<<r;

}

int main()

{

              ios::sync_with_stdio(false);

              cin.tie(nullptr);

              if (fopen("tps.inp", "r"))

              {

                           freopen("tps.inp", "r", stdin);

                           freopen("tps.out", "w", stdout);

              }

              docdl();

              xuli();

//  ghikq();

}

---------------HẾT---------------