15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường

 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
 8860 7150 2124 6392 8793 1597 1998 
 90 7369 4107 9352 3415 1660 4548 
 1909 6119 6018 287 9613 2838 1851 
 2293 2627 7871 4557 2859 7842 7099 
 6689 7481 5328 6657 8778 8566 1075 
 7996 2249 1290 9944 9748 6448 4057 
 3792 9322 171 1297 6988 4008 3923 
 5708 4535 9003 2908 830 3180 1270 
 6784 8019 1012 7867 9487 9374 9272 
 1146 2001 5523 8886 4449 4668 9499 
 8821 2168 3986 8820 2825 1537 7362 
 9641 3835 3135 9159 7171 8119 3226 
 6052 8799 4966 4890 743 5747 4746 
 3842 2425 262 9222 5027 5488 34 4631 
 1407 8524 8615 2002 7965 7483 521 
 9940 7347 5563 6312 3619 8737 6309
  . .
 35 . .
Bài 3. (7.0 điểm) MEGA: gồm có 40 test; mỗi test 0,175 điểm, thời gian 1 giây, bộ nhớ 1024 MB
 TEST MEGA.INP MEGA.OUT
 1 5 5 5 11
 YYGYG
 1 2
 5 1
 3 4
 3 2
 5 4
 2 3 2 5 0
 YGG
 1 2
 3 1
  . .
 40 . .
Lưu ý: Trường hợp bài làm thí sinh bằng điểm nhau, Hội đồng chấm thi, Tổ chấm thống nhất điều chỉnh 
thời gian bài thi của thí sinh để xếp giải.
 ---------------HẾT---------------
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
 ĐỀ SỐ 5
 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TRƯỜNG LỚP 11
 TỈNH BÌNH ĐỊNH Môn thi: TIN HỌC
 (Đề thi gồm có 04 trang) Thời gian: 150 phút (không kể thời gian phát đề)
 Ngày thi: 
TỔNG QUAN ĐỀ THI
 Tên tệp chương Tên tệp dữ liệu Thời 
Bài Tên bài, điểm Tên tệp dữ liệu ra
 trình vào gian
 Dãy phiến đá bí 
1 DAYBIAN.* DAYBIAN.INP DAYBIAN.OUT 1,0 giây
 ẩn (5đ)
2 Hộp quà (5đ) HOPQUA.* HOPQUA.INP HOPQUA.OUT 1,0 giây
3 Thử thách (5d) THUTHACH.* THUTHACH.INP THUTHACH.OUT 1,5 giây
 Trò chơi giải mật 
4 MATTHU.* MATTHU.INP MATTHU.OUT 1,0 giây
 thư (5d)
* Chú ý:
 • Phần mở rộng tên tệp chương trình theo ngôn ngữ lập trình của thí sinh (.pas; .cpp; .py).
 • Khi chấm thi có xét đến thời gian xử lý bài toán của của chương trình nên thí sinh không sủ 
 dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm.
 • File input và output ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến file 
 input và output.
 • Bộ nhớ cần dùng cho mỗi test của chương trình không quá 1024MB.
Bài 1: Dãy phiến đá bí ẩn
Thiên An , một nhà khảo cổ học trẻ, vừa khám phá một ngồi đền cổ ẩn chứa kho báu bị phong ấn. Để mở 
kho báu, Thiên An cần giải mã một dãy mật mã dựa trên các phiến đá được đánh số từ 1 đến , mỗi 
phiến đá được khắc một giá trị nguyên 푖. Một dãy phiến đá được gọi là bí ẩn nếu đó là một phiến đá 
hoặc một dãy phiến đá liên tiếp có tổng các giá trị khắc trên đó đúng bằng một con số thần kỳ 퐾. Theo 
cuộn giấy cổ, kho báu sẽ được mở nếu Thiên An tính đúng số lượng các dãy phiến đá bí ẩn.
Dữ liệu vào: Đọc từ tệp văn bản DAYBIAN.INP có cấu trúc:
 • Dòng đầu tiên chứa hai số nguyên và 퐾 1 ≤ ≤ 2 × 105,|퐾| ≤ 109 , trong đó là số 
 lượng phiến đá, 퐾 là con số thần kỳ.
 9
 • Dòng thứ hai chứa số nguyên 1, 2,, | 푖| ≤ 10 ,푖 = 1.. là các giá trị được khắc trên 
 từng phiến đá.
 • Các số trên mỗi dòng cách nhau bởi một dấu cách.
 • Dữ liệu vào đảm bảo luôn tìm thấy ít nhất một dãy phiến đá thỏa điều kiện đề bài.
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
Dữ liệu ra: Ghi ra tệp văn bản DAYBIAN.OUT một số nguyên duy nhất, biểu thị số lượng các dãy phiến 
đá liên tiếp có tổng giá trị ghi trên đó bằng 퐾.
DAYBIAN.INP DAYBIAN.OUT Giải thích
 Có 2 dãy phiến đá liên tiếp có tổng bằng 4 là: + Dãy: 3, 2, -2, 1 
64 -232-215 2
 + Dãy: -2, 1, 5
3-449 681900-
 1 Có 1 dãy phiến đá có tổng bằng -449 là: + Dãy: -449
449
 Có 2 dãy phiến đá liên tiếp có tổng bằng 23 là: + Dãy: 23
523 1-2 23617 2
 + Dãy: 6, 17
Ràng buộc:
 • Có 50% số điểm thỏa mãn điều kiện: ≤ 2 × 103;
 • Có 50% số điểm thỏa mãn điều kiện: 2 × 103 < ≤ 2 × 105.
Bài 2: Hộp quà
Sắp tới, câu lạc bộ Nhân ái của An có chuyến đi từ thiện tại các tỉnh vùng cao phía Bắc. Để chuyến đi 
mang lại nhiều giá trị tốt đẹp, An cùng câu lạc bộ đã chuẩn bị nhiều sách vở, các thiết bị điện tử hỗ trợ 
học tập và thức ăn ngon. Ngoài ra, An còn chuẩn bị một số hộp quà để tặng cho các em nhỏ.
Siêu thị gần nhà An đang bán hộp quà. Các hộp quà được đánh số từ 1 đến , trong đó, hộp quà thứ 
푖(푖 = 1.. ) có giá 푖 nghìn đồng và chứa 푖 viên kẹo.
An muốn mua hộp quà để tăng cho em. Yêu cầu của An là với mỗi hộp quà tặng cho em thứ 
푖(푖 = 1.. ) phải chứa ít nhất 푖 viên kẹo. Vì kinh phí có hạn, An chỉ có thể tặng cho mỗi em một hộp quà 
duy nhất (dĩ nhiên, mỗi hộp quà chỉ được tặng cho một em).
Hãy xác định An có thể mua hộp quà thỏa mãn yêu cầu trên hay không. Nếu có, tính tổng số tiền tối 
thiểu mà An cần chi trả để mua hộp quà.
Dữ liệu vào: Đọc từ tệp văn bản HOPQUA.INP có cấu trúc:
 • Dòng thứ nhất chứa 2 số nguyên và (1 ≤ ≤ ≤ 2 × 105).
 • Dòng thứ hai chứa số nguyên, số nguyên thứ 푖(푖 = 1.. ) là giá tiền và số viên kẹo của gói 
 9
 kẹo thứ 푖(1 ≤ 푖 ≤ 10 ).
 • Dòng thứ ba chứa số nguyên, số nguyên thứ 푖(푖 = 1.. ) là số viên kẹo ít nhất mà An mong 
 9
 muốn người thứ 푖 nhận được (1 ≤ 푖 ≤ 10 ).
 • Các số trên mỗi dòng cách nhau bởi một dấu cách.
Dữ liệu ra: Ghi ra tệp văn bản HOPQUA.OUT một số nguyên duy nhất biểu thị số tiền ít nhất An phải trả 
nếu mua được, nếu không mua được hãy ghi -1 .
Ví dụ:
HOPQUA.INP HOPQUA.OUT Giải thích
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
42 Trong trường hợp này mua được món quà thứ 1 và thứ 2 
3454 7 (hoặc thứ 1 và thứ 4). Món quà thứ 1 tặng cho người thứ 
14 nhất, món quà thứ 2 (hoặc thứ 4) tặng cho người thứ 2.
33
111 -1 Không mua được.
100000100000100000
Ràng buộc:
 • Có 70% số điểm thỏa mãn điều kiện: 1 ≤ ≤ ≤ 2 × 104;
 • Có 30% số điểm thỏa mãn điêu kiện: 2 × 104 < ≤ ≤ 2 × 105.
Bài 3: Thử thách
Vua Thiên Trạch mở hội kén rể cho công chúa Thái Tuyết xinh đẹp. Nhà vua rất yêu thương con gái nên 
muốn tìm một chàng phò mã thông minh và đầy lòng kiên nhẫn. Nhà vua đưa ra một số thử thách, mỗi 
thử thách được mô tả như sau:
Cho trước ba số nguyên dương 퐾, và , các chàng trai phải loại bỏ tất cả các số chia hết cho hoặc 
trong dãy số vô hạn gồm các số nguyên dương liên tiếp 1,2,3,4,, sau đó xác định số ở vị trí thứ 퐾 trong 
dãy các số còn lại sau khi loại bỏ.
Chàng trai nào thực hiện được các thử thách của nhà vua một cách chính xác và nhanh nhất sẽ cưới công 
chúa Thái Tuyết làm vợ.
Dữ liệu vào: Đọc từ tệp văn bản THUTHACH.INP có cấu trúc:
 • Dòng đầu tiên chứa một số nguyên (1 ≤ ≤ 105) là số lượng thử thách mà nhà vua đưa ra.
 • dòng tiếp theo, mỗi dòng chứa ba số nguyên 퐾, , (1 ≤ 퐾, , ≤ 109) mô tả một thử thách.
 • Các số trên mỗi dòng cách nhau bởi một dấu cách.
 dòng, biểu thị kết quả của từng thử thách (giá trị của số ở vị trí thứ 퐾 trong dãy sau khi loại bỏ).
Ví dụ:
THUTHACH.INP THUTHACH.OUT Giải thích
 - Với 퐾 = 2, = 2, = 4, dãy còn lại sau khi bị loại bỏ: 1, 3, 
2
 3 5, 7, 9, ...
224
 2 - Với 퐾 = 2, = 3, = 4, dãy còn lại sau khi bị loại bỏ: 1, 2, 
234
 5, 7, 10, ...
 - Với 퐾 = 10, = 2, = 5, dãy còn lại sau khi bị loại bỏ: 1, 3, 
2
 23 7, 9, 11, 13, 17, 19, 21, 23, ...
1025
 22 - Với 퐾 = 15, = 3, = 9, dãy còn lại sau khi bị loại bỏ: 1, 2, 
1539
 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, ...
Ràng buộc:
 • Có 50% số điểm thỏa mãn điều kiện: ,퐾, , ≤ 100;
 • 50% số điểm còn lại không có ràng buộc gì thêm.
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
Bài 4: Trò chơi giải mật thư
Thành là một bí thư Đoàn có niềm đam mê chinh phục các trò chơi với những con số. Sắp tới ngày Hội 
Thanh niên 26/3, Thành chuẩn bị trò chơi giải mật thư cho các trại sinh với quy tắc như sau: Các trại sinh 
phải giải mật thư bằng cách xử lý một dãy số nguyên không âm gồm phần tử 1, 2,, . Để giải 
mật thư, các trại sinh cần thực hiện thao tác trên dãy số , có thể gồm ba loại sau:
 • Thao tác loại 1(1 ) : Tính và ghi ra tổng các phần tử trong đoạn từ đến 
 ( + +1 +  + .
 • Thao tác loại 2(2 푤) : Biến đổi mỗi phần tử 푖 trong đoạn từ đến (푖 = .. ) thành 
 푖mod푤(mod là phép chia lấy dư).
 • Thao tác loại 3(3 ) : Gán giá trị = .
Kết quả sau quá trình giải mật thư là dãy các số tương ứng với các yêu cầu của thao tác loại 1. Trại sinh 
nào giải được mật thư chính xác nhất sẽ được quà của Ban Tổ chức.
Dữ liệu vào: Đọc từ tệp văn bản MATTHU.INP có cấu trúc:
 • Dòng đầu tiên chứa hai số nguyên dương và (1 ≤ , ≤ 105) lần lượt là số lượng phần tử 
 của dãy và số thao tác.
 9
 • Dòng thứ hai chứa số nguyên 1, 2,, (1 ≤ 푖 ≤ 10 ,푖 = 1.. ) là các giá trị ban đầu của 
 dãy .
 • dòng tiếp theo, mỗi dòng mô tả một trong ba thao tác sau:
 • Loại 1: 1 (1 ≤ ≤ ≤ ).
 • Loại 2: 2 푤 1 ≤ ≤ ≤ ,1 ≤ 푤 ≤ 109 .
 • Loại 3: 3 (1 ≤ ≤ ,1 ≤ ≤ 109).
 • Các số trên mỗi dòng cách nhau bởi một dấu cách.
Dữ liệu ra: Ghi ra tệp văn bản MATTHU.OUT gồm:
 • Với mỗi thao tác loại 1 , ghi ra tổng các phần tử trong đoạn từ đến ( + +1 +  + ), 
 mỗi giá trị trên một dòng riêng biệt.
 MATTHU.INP MATTHU.OUT Giải thích
 55 - Thao tác thứ , dãy trở thành: 1,5,0,2,1
 14
 15324
 2353 2 - Thao tác thứ , dãy trở thành: 1,5,6,2,1
 336 - Thao tác thứ , kết quả là: + + + = ퟒ
 - Thao tác thứr 4, dãy trở thành: 1,1,0,2,1
 - Thao tàc thứ , kết quả là: 푰 + 푰 + 휽 = 
Ràng buộc:
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
• Có 30% số điểm thỏa mãn điều kiện: , ≤ 1000;
• Có 30% số điểm thỏa mãn điều kiện: Dữ liệu vào không có thao tác loại 2 và 3 .
• Có 20% số điểm thỏa mãn điều kiện: 푤 = 2 trong tất cả các thao tác loại 2 .
• 20% số điểm còn lại không có ràng buộc gì thêm.
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
 ĐÁP ÁN
Bài 1:
#include 
using namespace std;
int main(){
 ios::sync_with_stdio(false);
 cin.tie(NULL);
 freopen("DAYBIAN.INP","r",stdin);
 freopen("DAYBIAN.OUT","w",stdout);
 int n; long long k;
 cin>>n>>k;
 vectora(n);
 for(int i=0;i>a[i];
 unordered_map mp;
 mp[0]=1;
 long long sum=0, res=0;
 for(int i=0;i<n;i++){
 sum+=a[i];
 if(mp.count(sum-k)) res+=mp[sum-k];
 mp[sum]++;
 }
 cout<<res;
}
Bài 2:
#include 
using namespace std;
int main(){
 freopen("HOPQUA.INP","r",stdin);
 freopen("HOPQUA.OUT","w",stdout);
 int n,m;
 cin>>n>>m;
 vector> box(n);
 for(int i=0;i>box[i].first>>box[i].second;
 vector need(m);
 for(int i=0;i>need[i];
 sort(need.begin(), need.end());
 sort(box.begin(), box.end(), [](auto &a, auto &b){
 return a.second < b.second;
 });
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
 multiset ms;
 long long ans=0;
 int j=0;
 for(int i=0;i<m;i++){
 while(j=need[i]){
 ms.insert(box[j].first);
 j++;
 }
 if(ms.empty()){
 cout<<-1;
 return 0;
 }
 ans+=*ms.begin();
 ms.erase(ms.begin());
 }
 cout<<ans;
}
Bài 3:
#include 
using namespace std;
long long a,b,k;
long long cnt(long long x){
 return x - x/a - x/b + x/lcm(a,b);
}
int main(){
 freopen("THUTHACH.INP","r",stdin);
 freopen("THUTHACH.OUT","w",stdout);
 int t; cin>>t;
 while(t--){
 cin>>a>>b>>k;
 long long l=1,r=1e18,ans=0;
 while(l<=r){
 long long mid=(l+r)/2;
 if(cnt(mid)>=k){
 ans=mid;
 r=mid-1;
 }else l=mid+1;
 }
 cout<<ans<<"
";
 }
}
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
Bài 4:
#include 
using namespace std;
int n,q;
long long st[4*200005], a[200005];
void build(int id,int l,int r){
 if(l==r){ st[id]=a[l]; return; }
 int m=(l+r)/2;
 build(id*2,l,m);
 build(id*2+1,m+1,r);
 st[id]=st[id*2]+st[id*2+1];
}
void update_set(int id,int l,int r,int pos,long long val){
 if(l==r){ st[id]=val; return; }
 int m=(l+r)/2;
 if(pos<=m) update_set(id*2,l,m,pos,val);
 else update_set(id*2+1,m+1,r,pos,val);
 st[id]=st[id*2]+st[id*2+1];
}
void update_mod(int id,int l,int r,int u,int v,long long mod){
 if(l>v||r<u||st[id]<mod) return;
 if(l==r){
 st[id]%=mod;
 return;
 }
 int m=(l+r)/2;
 update_mod(id*2,l,m,u,v,mod);
 update_mod(id*2+1,m+1,r,u,v,mod);
 st[id]=st[id*2]+st[id*2+1];
}
long long query(int id,int l,int r,int u,int v){
 if(l>v||r<u) return 0;
 if(l>=u&&r<=v) return st[id];
 int m=(l+r)/2;
 return query(id*2,l,m,u,v)+query(id*2+1,m+1,r,u,v);
}
int main(){
 freopen("MATTHU.INP","r",stdin);
 freopen("MATTHU.OUT","w",stdout);
 cin>>n>>q;
 for(int i=1;i>a[i];
 build(1,1,n);
 while(q--){
 int t; cin>>t;
 if(t==1){
 int l,r; cin>>l>>r;
 DeThiHay.net 15 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 11 cấp Trường - DeThiHay.net
 cout<<query(1,1,n,l,r)<<"
";
 }else if(t==2){
 int l,r; long long x;
 cin>>l>>r>>x;
 update_mod(1,1,n,l,r,x);
 }else{
 int pos; long long x;
 cin>>pos>>x;
 update_set(1,1,n,pos,x);
 }
 }
}
 DeThiHay.net