Đề thi Olympic 30/4 môn tin học khối 10 năm 2015

Đặng Minh Tiến

Đề thi Olympic 30/4 môn tin học khối 10 năm 2015

Tổng quan đề thi

STTTÊN BÀITÊN CHƯƠNG TRÌNHDỮ LIỆU VÀOKẾT QUẢ
1Đặt trạm phủ sóngMOBI.*MOBI.INPMOBI.OUT
2Tam giác cânTGCAN.*TGCAN.INPTGCAN.OUT
3Mạng ĐiệnMANGDIEN.*MANGDIEN.INPMANGDIEN.OUT

Trong đó, dấu * thay cho PAS, C hoặc CPP.

Bài 1: Đặt trạm phủ sóng

Nhà cung cấp dịch vụ viễn thông Mobi đã khảo sát số lượng người sẽ dùng dịch vụ trên một con đường thẳng mới được xây dựng và đánh dấu lại những vị trí trên con đường này. Đầu con đường được đánh tọa độ bắt đầu từ 0. Tại vị trí có tọa độ X (đơn vị chiều dài) có số lượng người sẽ sử dụng dịch vụ là Y. Trước mắt, nhà cung cấp dịch vụ cần đặt một trạm phát sóng có bán kính phủ sóng là K đơn vị chiều dài để phủ sóng cho một số người sử dụng dịch vụ trên con đường này.

Yêu cầu: Bạn hãy xác định vị trí đặt trạm phát sóng sao cho trạm có thể phục vụ được số lượng người sử dụng nhiều nhất có thể.

Dữ liệu: cho trong file văn bản MOBI.INP có cấu trúc như sau:

  • Dòng đầu tiên ghi hai số nguyên N và K (0<N ≤106, 0<K≤2*106), trong đó N là số điểm dân cư đã được đánh dấu, K là bán kính phủ sóng của trạm.
  • Trong N dòng tiếp theo, dòng thứ i (i=1..N) ghi hai số nguyên X[i] và Y[i] cho biết tại vị trí X[i] có số lượng người dùng là Y[i] (0≤ X[i] ≤106, 0≤Y[i] ≤104). Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản MOBI.OUT một số nguyên cho biết số người dùng nhiều nhất sẽ được phục vụ.

Ví dụ:

MOBI.INPMOBI.OUTGiải thích
4 3

7 4

15 10

2 2

1 5

11Chọn vị trí trạm tại X=4. Như vậy có thể phủ sóng đến các vị trí có toạ độ 1, 2, 7. Số lượng người sử dụng lớn nhất là 11.

Lời giải bài 1:

https://kienthuc24h.com/dat-tram-phu-song-olympic-3042015-tin-hoc-10/

Bài 2: Tam giác cân

Tam giác cân là tam giác có ít nhất 2 cạnh có độ dài bằng nhau. Cho dãy gồm N số nguyên dương: a1, a2, …, aN. Hãy tính số bộ 3 chỉ số (i, j, k), với 1 ≤ i < j < k ≤ N sao cho 3 số ai, aj, ak là độ dài 3 cạnh của một tam giác cân.

Dữ liệu: Cho trong file văn bản TGCAN.INP có:

  • Dòng đầu ghi số nguyên N (3 ≤ N ≤ 500000).
  • Dòng tiếp theo ghi N số hạng của dãy, mỗi số đều không vượt quá 105. Các số hạng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản TGCAN.OUT một số nguyên, là số tam giác cân tìm được.

 

Ví dụ:

TGCAN.INPTGCAN.OUT
8 5 3 2 9 5 4 9 522

 

Ràng buộc:

  • 40% số test ứng với 40% số điểm của bài ứng với N < 103
  • 70% số test ứng với 70% số điểm của bài ứng với N ≤ 105

Bài 3:  Mạng Điện

Để đảm bảo việc cung cấp điện cho các công ty trong một khu công nghiệp, ban quản lý khu công nghiệp lên kế hoạch xây dựng thêm một nhà máy nhiệt điện X. Chỉ có một công ty (bất kì trong khu công nghiệp) sẽ đuợc truyền tải điện từ nhà máy X. Chi phí cho kết nối từ nhà máy nhiệt điện X đến công ty này là không đáng kể. Một công ty được xem là có nguồn điện ổn định nếu nó có kết nối đến nhà máy nhiệt điện X hay nó có kết nối đến một công ty khác có nguồn điện ổn định. Dựa trên chi phí kết nối giữa các công ty do nhóm khảo sát thực hiện, ban quản lý muốn cân nhắc hai giải pháp kết nối ít chí phí nhất để tất cả các công ty trong khu công nghiệp có nguồn điện ổn định.

Yêu cầu:  Cho biết trước chi phí kết nối giữa các công ty. Hãy xác định tổng chi phí kết nối nhỏ nhất S1 và nhỏ thứ hai S2 giữa các công ty sao cho tất cả các công ty đều có nguồn điện ổn định, (có thể S1=S2 khi có hai cách kết nối giữa các công ty mà chi phí kết nối nhỏ nhất bằng nhau). Giả sử rằng luôn tìm được hai cách kết nối khác nhau để các nhà máy có nguồn điện ổn định.

Dữ liệu: Cho trong file văn bản MANGDIEN.INP. Dòng đầu là hai số nguyên N, M (3≤ N ≤100) lần luợt là số công ty và số kết nối đã được khảo sát giữa các công ty.  M dòng tiếp theo, mỗi dòng chứa 3 số nguyên Ai, Bi, Ci cho biết để kết nối hai công ty Ai, Bi  thì cần chi phí Ci (1≤Ci≤1000). Các công ty được đánh số từ 1 đến N.

Kết quả: Ghi ra file văn bản MANGDIEN.OUT hai số nguyên S1và S2 trên một dòng. Hai số cách nhau một khoảng trắng.

 

MANGDIEN.INPMANGDIEN.OUT
5 6

1 3 1

2 3 1

3 4 1

3 5 1

2 5 5

4 5 2

4 5

 Hết

Lời giải bài 2 và 3:

Lời giải đề thi Olympic 30/4 môn tin học khối 10 năm 2015

Lời giải đề thi Olympic 30/4 môn tin học khối 10 năm 2015

Giám thị không giải thích gì thêm. Thí sinh không được sử dụng tài liệu.

11 thoughts on “Đề thi Olympic 30/4 môn tin học khối 10 năm 2015”

      • #include
        using namespace std;
        long long d[1000000];
        long long a[1000000];
        long long c[1000000];
        int main() {
        long long i,n,hieu,j,z;
        long long t=0;
        cin>>n;
        hieu=0;
        for(i=1; i>a[i];
        d[a[i]]++;
        }

        sort(a+1, a+1+n);
        c[a[n]]=0;
        for(i=a[n]-1;i>=1;i–)
        {
        c[i]=c[i+1]+d[2*i+1];
        }

        for(i=1; i2)
        {
        z=(d[i]*(d[i]-1)*(d[i]-2))/6;
        t=t+(d[i]*(d[i]-1)/2)*(n-d[i]-c[i])+z;
        }
        else
        if((d[i]>1)&&(d[i]<=2)) {t=t+(d[i]*(d[i]-1)/2)*(n-2-c[i]);}

        }
        cout<<t;
        }

        Trả lời

    • Hi em, em có thể tham khảo về cây khung trong tài liệu giáo khoa chuyên tin hoặc trên mạng nha. cây khung và đường đi ngắn nhất là 2 dạng bài rất quan trọng trong các kì thi, vì thế hãy nắm chắc phần này. nếu em rành và hiểu về dijkstra thì nên học Prim , còn không em có thể học kruskal cho đơn giản. tuy nhiên thì prim dpt là n^2, còn kruskal là m log m nên còn tùy trường hợp mà dùng. nhưng đơn giản nhất em cứ dùng kruskal là được

      Trả lời

    • Bạn ơi, test bài 2 (Tam giác cân) chính xác là 22 nhé bạn.
      Mình đã viết lại code để kiểm tra và kết quả chính xác là 22 nha.
      Bạn vui lòng kiểm tra lại đáp án của bạn nhé 😀

      #include 
using namespace std;

int main()
{
    int n, a[500000], dem=0;
    cin >> n;

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

    for (int i=0; i
      Trả lời

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *