Đề thi HSG Tin 10 – Hà Giang – Kèm code tham khảo
Đề thi HSG Tin 10 – Hà Giang
TỔNG QUAN ĐỀ THI
| Tên bài | File chương trình | File input | File Output |
| Dãy số | CODI.* | CODI.INP | CODI.OUT |
| Khách sạn | HOTEL.* | HOTEL.INP | HOTEL.OUT |
| Mận hậu Mộc Châu | PLUMS.* | PLUMS.INP | PLUMS.OUT |
Dấu * tương ứng với đuôi .PAS hoặc .CPP khi học sinh sử dụng ngôn ngữ lập trình PASCAL hoặc C++.
Em hãy lập trình giải các bài toán sau:
Bài 1 (6,0 điểm). Dãy số
Dãy số CODI được xây dựng như sau:
- A0 = 1
- An = An-1 + CODI(An-1) với i > 0
Trong đó, CODI(x) = số lượng các ước dương của x.
Ví dụ một vài phần tử đầu tiên của dãy CODI: 1 2 4 7 9 12 18
Yêu cầu:Cho trước hai số nguyên dương A và B, đếm số lượng các phần tử trong dãy CODI thuộc đoạn [A, B] .
Dữ liệu: Vào từ tệp văn bản CODI.INP có cấu trúc như sau:
- Dòng đầu tiên chứa số nguyên dương T (T < 100.000) – Số lượng test trong file input
- T dòng sau, mỗi dòng chứa cặp A, B (1 ≤ A ≤ B ≤ 100.000).
Kết quả: Ghi ra tệp văn bản CODI.OUT:
- Gồm T dòng, mỗi dòng là kết quả của bài toán
Ví dụ:
| CODI.INP | CODI.OUT |
| 3
1 18 1 100 3000 4000 |
7
20 87 |
Subtask 1 (60%) : 0 ≤ ai ≤ 103
Subtask 2 (40%) : 0 ≤ ai ≤ 105
Bài 2 (7,0 điểm). Khách sạn
Năm 2019 được dự báo là năm nóng nhất lịch sử, mùa hè 2019 vì thế cũng được cho là khắc nghiệt nhất so với các năm trước. Do nắng nóng kéo dài lại đúng vào dịp nghỉ hè nên người dân đã đổ xô đi nghỉ dưỡng trên núi để tránh nắng nóng. Các địa điểm được yêu thích như Tam Đảo, Sapa, Mộc Châu, Đà Lạt, Ba Vì, An Giang, Thanh Hóa… Đến với những khu nghỉ dưỡng trên vùng cao ta sẽ được tận hưởng khí hậu mát mẻ, không khí trong lành, bình yên. Còn gì tuyệt vời hơn cho mùa hè này!
Trong đó, Sơn La là một tỉnh có nhiều danh lam thắng cảnh nổi tiếng, những ngọn núi hùng vĩ, nhiều món ăn đặc sản. Vì thế năm nay lượng khách du lịch đổ về Sơn La cũng tăng kỷ lục, có thời điểm dẫn đến tình trạng các khách sạn ở đây “cháy phòng”. Khách sạn Sơn La chỉ còn một phòng nên quyết định cho thuê phòng này theo hình thức thỏa thuận về giá cả. Sau khi tổng hợp các đơn đặt hàng, khách sạn nhận được n đơn đặt hàng, trong đó đơn đặt hàng thứ i đăng ký ngày bắt đầu là ai, ngày trả phòng là bi và chấp nhận trả số tiền thuê phòng là ci.
Do có nhiều đơn đặt hàng, thời gian đặt phòng lại chồng chéo nhau, số tiền khách hàng chấp nhận trả cho khách sạn cũng khác nhau nên ban quản lý khách sạn đang rất khó khăn không biết nhận lời hay từ chối khách hàng nào.
Yêu cầu: Em hãy viết chương trình giúp khách sạn nhận đơn đặt phòng sao cho lợi nhuận thu được là lớn nhất.
Lưu ý: Theo điều lệ của khách sạn, khách hàng phải trả phòng trước 12 giờ trưa, khách hàng khác có thể nhận phòng từ 12 giờ trong ngày.
Dữ liệu: Vào từ tệp văn bản HOTEL.INP có cấu trúc như sau:
+ Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 10000) thể hiện số đơn đặt hàng.
+ n dòng tiếp theo gồm 3 số nguyên ai, bi và ci. Mỗi số cách nhau một khoảng trắng. (l ≤ ai ≤ bi ≤ 100, 0 ≤ ci ≤1000).
Kết quả: Ghi ra tệp văn bản HOTEL.OUT với một số nguyên thể hiện số tiền lớn nhất mà khách sạn có thể thu được.
Ví dụ:
| HOTEL.INP | HOTEL.OUT |
| 3
1 2 8 2 3 6 4 7 6 |
20 |
| 4
1 4 5 1 3 8 3 5 4 4 6 9 |
17 |
Subtask 1 (30%) : 1 ≤ n ≤ 10, l ≤ ai ≤ bi ≤ 10, 0 ≤ ci ≤10.
Subtask 2 (30%) : 1 ≤ n ≤ 1000, l ≤ ai ≤ bi ≤ 50, 0 ≤ ci ≤100.
Subtask 3 (40%) : 1 ≤ n ≤ 10000, l ≤ ai ≤ bi ≤ 100, 0 ≤ ci ≤1000.
Bài 3. (7,0 điểm) Mận hậu Mộc Châu
Mận hậu Mộc Châu Sơn La là đặc sản của cao nguyên Mộc Châu tươi đẹp, khí hậu quanh năm mát mẻ. Mận hậu Sơn La giòn giòn, chua thanh chấm muối tôm hặc chẩm cheo thì ngon tuyệt hảo. Mận hậu giàu chất dinh dưỡng, chứa rất nhiều kali, vitamin A, sắt, vitamin B2, các vitamin nhóm B và ma giê, giàu chất sơ giúp tăng cường chức năng tiêu hóa. Một quả mận chín chuẩn có 26% vitamin C, 13% vitamin K và 11% vitamin A. Ăn mận để thanh lọc máu, nuôi dưỡng một trái tim khỏe. Mận còn giàu chất chống oxi hóa, làm sáng mắt, đẹp da, phòng tránh nguy cơ mắc các bệnh ung thư, ngăn ngừa lão hóa…. Mận Hậu có chứa axit xitric có tác dụng phòng chống mệt mỏi và chuột rút co cơ. Bên cạnh đó, lượng nước dồi dào trong mận còn giúp ổn định cơ thể nên được nhiều vận động viên chuyên nghiệp ưa chuộng.
Biết được những công dụng của Mận Hậu nên sau khi tham gia trại hè Hùng Vương, Minh đã đến siêu thị để mua k (kg) Mận về làm quà cho n người bạn thân. Trong siêu thị Mận được đóng gói sẵn trong các bao bì hút chân không, mỗi gói chứa x kg Mận (x > 0 và x là số nguyên). Bảng giá niêm yết một gói x kg Mận có giá là y VNĐ. Nếu y = -1 thì có nghĩa gói đó là hàng trưng bày và không bán. Minh quyết định sẽ mua k (kg) Mận nếu số lượng gói tối đa không vượt quá n cho n người bạn thân. Tức là Minh sẽ không mua nhiều hơn n gói Mận.
Bạn hãy lập trình tính giúp Minh số tiền ít nhất mà Minh phải bỏ ra để mua đúng k (kg) Mận về cho n người bạn.
Dữ liệu: Vào từ tệp văn bản PLUMS.INP có cấu trúc như sau:
+ Dòng đầu tiên chứa hai số nguyên dương n và k, lần lượt là số lượng bạn của Minh và lượng Mận (kg) mà Minh muốn mua.
+ Dòng thứ hai bao gồm k số nguyên y ghi cách nhau bởi một dấu cách. Trong đó, số nguyên thứ i là giá của gói ‘i’ kg (y ≤ 100). Và giá trị -1 có nghĩa là gói tương ứng sẽ không được bán. (i được tính từ 1; n, k ≤ 100).
Kết quả: Ghi ra tệp văn bản PLUMS.OUT
Số tiền ít nhất mà Minh phải bỏ ra để mua k (kg) Mận. Nếu Minh không thể mua được k (kg) Mận thì in ra -1.
Ví dụ:
| PLUMS.INP | PLUMS.OUT |
| 3 5
-1 -1 4 5 -1 |
-1 |
| 5 5
1 2 3 4 5 |
5 |
Subtask 1 (50%) : 1 ≤ n, k < 50.
Subtask 2 (50%) : 50 ≤ n, k ≤ 100.
Giải thích:
+ Trong test 1, có n = 3 người bạn, k = 5 kg Mận cần mua. Tiếp theo là giá của 5 gói (1, 2, 3, 4, 5) kg. Tuy nhiên gói 1, 2 và 5 kg không bán. Do đó chỉ còn gói 3 và 4 kg. Nên Minh không thể mua được 5 kg Mận. Vì vậy, anh ấy không thể mua quà cho những người bạn thân.
+ Trong test 2, có n = 5 người bạn, k = 5 kg Mận cần mua. Giá của các gói 1, 2, 3, 4, 5 kg tương ứng là 1, 2, 3, 4, 5. Minh có thể có nhiều cách mua để có được 5 (kg) Mận và số lượng gói ≤ 5. Minh sẽ chọn cách mua 5 gói 1 kg. Vì vậy số tiền nhỏ nhất mà Minh cần bỏ ra là 5.
Code C++ Đề thi HSG Tin 10 – Hà Giang tham khảo
Bài 1:
#include <bits/stdc++.h>
using namespace std;
long a[10000]
,t,x,y,n;
long codi(long x)
{
long d=1,i;
if(x==1) return 1;
for(i=2;i*i<=x;i++)
if(x%i==0)
{
long k=0;
while(x%i==0)
{
k++;x/=i;
}
d*=k+1;
}
if(x>1)d*=2;
return d;
}
void cbi()
{
long i;
a[0]
=1;
for(i=1; ;i++)
{
a[i] =a[i-1] +codi(a[i-1]
);
if (a[i]
> 100000) break;
}
n = i;
}
long binsrc(long l,long r,long x,bool cm)
{
long k=0;
while(r>=l)
{
long g=(l+r)/2;
if(cm==1)
{if(a[g]
>x) {k=g;r=g-1;}
else l=g+1;}
else
{
if(a[g]
<x){k=g+1;l=g+1;}
else if(a[g]
==x) return g;
else r=g-1;
}
}
return k;
}
int main()
{
freopen("CODI.INP","r",stdin);
freopen("CODI.OUT","w",stdout);
cbi();
cin>>t;
while(t--)
{
cin>>x>>y;
if(y>20000) cout<<binsrc(1000,n,y,1)-binsrc(0,n,x,0)<<endl;
else cout<<binsrc(0,n,y,1)-binsrc(0,n,x,0)<<endl;
}
return 0;
}
Bài 2:
#include <bits/stdc++.h>
using namespace std;
int m[100] ,tks[100] ,vao[100] ,ra[100] ,a[100]
;
int b[100]
;
int n,i,t,d,k,s;
void xuat()
{
int i;
d+=1;
m[d]
=0;
for(i=1;i<=k;i++)
m[d] =m[d] +tks[a[i]
];
}
void thu(int i)
{
int j;
for(j=1;j<=n;j++)
if (b[j]
==0)
{
a[i]
=j;
if (a[i] >a[i-1]
)
if (vao[a[i] ]>=ra[a[i-1]
])
if (i==k) xuat();
else
{
b[j]
=1;
thu(i+1);
b[j]
=0;
}
}
}
int main()
{
freopen("HOTEL.INP","r",stdin);
freopen("HOTEL.OUT","w",stdout);
cin>>n;
for(i=1;i<=n;i++)
cin>>vao[i] >>ra[i] >>tks[i]
;
d=0;
for(k=1;k<=n;k++)
thu(1);
t=m[1]
;
for(i=2;i<=d;i++)
if (m[i] >t) t=m[i]
;
cout<<t;
return 0;
}
Bài 3:
#include <bits/stdc++.h> using namespace std; #define task "PLUMS" using namespace std; const int MAX = 105; int N; int K; int val[MAX] ; int f[MAX] [MAX] ; int main() { ios::sync_with_stdio(false); freopen(task".inp","r",stdin); freopen(task".out","w",stdout); cin >> N >> K; for(int i = 1; i <= K; i++) { cin >> val[i] ; for(int j = 1; j <= N; j++) f[i] [j] = val[i] ; } for(int i = 2; i <= K; i++) for(int x = 2; x <= N; x++) for(int j = 1; j < i; j++) { if(f[j] [x - 1] < 0 || val[i - j] < 0) continue; int temp = f[j] [x - 1] + val[i - j] ; if(f[i] [x] < 0 || temp < f[i] [x] ) f[i] [x] = temp; } cout << f[K] [N] << endl; return 0; }
