.png)
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH QUẢNG NINH
KỲ THI TUYỂN SINH VÀO LỚP 10 THPT
Môn thi: TIN HỌC CHUYÊN
Thời gian làm bài: 150 phút, không kể thời gian giao đề
(Đề thi này có 03 trang)
TỔNG QUAN ĐỀ THI
Bài
Tên bài
Tệp
chương trình
Tệp
dữ liệu
Tệp
kết quả
Bộ nhớ
(MB)
Thời gian
(giây)
Điểm
1
Ghép từ
str.*
str.inp
str.out
1024
1
3,0
2
Di chuyển
mov.*
mov.inp
mov.out
1024
1
3,0
3
Số ước
div.*
div.inp
div.out
1024
1
2,5
4
Đánh luống
dri.*
dri.inp
dri.out
1024
1
1,5
Dấu
*
được thay thế bởi
cpp
hoặc
py
của ngôn ngữ lập trình được sử dụng tương ứng là
C++
hoặc
Python
.
Hãy lập trình giải các bài toán sau:
Bài 1. Ghép từ (3,0 điểm)
An rất thích nhân vật Conan trong truyện “Thám tử lừng danh Conan”. Anh ta có thói quen gặp xâu ký
tự nào cũng thực hiện hoán đổi các cặp ký tự bất kỳ để tạo thành những cụm từ “
CONAN
”.
Cho một xâu ký tự
𝑠
, hãy giúp An tính xem có thể tạo được tối đa bao nhiêu cụm từ “
CONAN
” bằng cách
hoán đổi các cặp ký tự bất kỳ.
Ví dụ với xâu ký tự
𝑠 =
“
CBONANACONENAN
”, sau khi thực hiện hoán đổi các ký tự ở các cặp vị trí
(
1, 2
)
,
(
13, 11
)
ta được
𝑠 =
“
BCONANACONANEN
” chứa
2
cụm từ “
CONAN
” và không có cách hoán
đổi nào khác tạo ra nhiều hơn
2
cụm từ “
CONAN
”.
Dữ liệu: Vào từ tệp văn bản
str.inp
gồm một dòng chứa xâu
𝑠
(
1 ≤
|
𝑠
|
≤ 10
5
, trong đó
|
𝑠
|
là độ dài
xâu
𝑠
) chỉ bao gồm các chữ cái tiếng Anh in hoa.
Kết quả: Ghi ra tệp văn bản
str.out
một số nguyên là câu trả lời của bài toán.
Ví dụ:
str.inp
str.out
CBONANACONENAN
2
Ràng buộc:
•
Có 20% số test ứng với 20% số điểm thỏa mãn: Xâu
𝑠
chỉ chứa các ký tự ‘
A
’, ‘
C
’, ‘
N
’, ‘
O
’ và
1 ≤
|
𝑠
|
≤ 10
;
•
40% số test khác ứng với 40% số điểm thỏa mãn:
1 ≤
|
𝑠
|
≤ 10
3
;
•
40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.
Bài 2. Di chuyển (3,0 điểm)
Trong một thành phố có
𝑚
xe ô tô điện và
𝑛
trạm sạc nằm trên một đoạn đường thẳng. Ta xem đoạn
đường này nằm trên một trục tọa độ, trong đó mỗi đơn vị là
1
km. Hiện tại, ô tô điện thứ
𝑖
(
𝑖 = 1, 2, … , 𝑚
)
ở vị trí có tọa độ
𝑎
𝑖
và trạm sạc thứ
𝑗
(
𝑗 = 1, 2, … , 𝑛
)
ở vị trí có tọa độ
𝑏
𝑗
. Mỗi xe ô tô điện cần tìm trạm
sạc gần nhất để sạc pin. Nhiệm vụ của bạn là tính khoảng cách mà mỗi xe ô tô điện cần di chuyển đến
trạm sạc gần nhất.
ĐỀ THI MINH HỌA
2
Dữ liệu: Vào từ tệp văn bản
mov.inp
. Dòng đầu tiên chứa số nguyên
𝑚
(
1 ≤ 𝑚 ≤ 10
5
)
là số lượng
xe ô tô điện trên đoạn đường. Dòng thứ hai chứa
𝑚
số nguyên
𝑎
1
, 𝑎
2
, … , 𝑎
𝑚
(
−10
9
≤ 𝑎
𝑖
≤ 10
9
)
là tọa
độ của các xe ô tô điện. Dòng thứ ba chứa số nguyên
𝑛
(
1 ≤ 𝑛 ≤ 10
5
)
là số lượng trạm sạc. Dòng thứ
tư chứa
𝑛
số nguyên
𝑏
1
, 𝑏
2
, … , 𝑏
𝑛
(
−10
9
≤ 𝑏
𝑖
≤ 10
9
)
là tọa độ của các trạm sạc.
Kết quả: Ghi ra tệp văn bản
mov.out
gồm
𝑚
dòng. Dòng thứ
𝑖
chứa một số nguyên là khoảng cách
mà xe ô tô điện thứ
𝑖
cần di chuyển đến trạm sạc gần nhất.
Ví dụ:
mov.inp
mov.out
5
2 3 5 -2 15
6
1 4 -1 2 7 9
0
1
1
1
6
Ràng buộc:
•
Có 40% số test ứng với 40% số điểm thỏa mãn:
𝑚 = 1
;
•
30% số test khác ứng với 30% số điểm thỏa mãn:
1 ≤ 𝑚, 𝑛 ≤ 10
3
;
•
30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Bài 3. Số ước (2,5 điểm)
Cho một dãy gồm
𝑛
số nguyên dương
𝑎
1
, 𝑎
2
, … , 𝑎
𝑛
. Hãy tính số lượng ước của tích tất cả các số trong
dãy. Vì kết quả có thể rất lớn, nên chỉ cần đưa ra số dư của kết quả khi chia cho
10
9
+ 7
.
Dữ liệu: Vào từ tệp văn bản
div.inp
. Dòng đầu tiên chứa số nguyên
𝑛
(
1 ≤ 𝑛 ≤ 10
5
)
là số phần tử
của dãy. Dòng thứ hai chứa
𝑛
số nguyên
𝑎
1
, 𝑎
2
, … , 𝑎
𝑛
(
1 ≤ 𝑎
𝑖
≤ 10
6
)
là các phần tử của dãy.
Kết quả: Ghi ra tệp văn bản
div.out
một số nguyên là câu trả lời của bài toán.
Ví dụ:
div.inp
div.out
3
2 6 2
8
Trong ví dụ trên, tích tất cả các số của dãy là
2 × 6 × 2 = 24
và tích này có
8
ước là
1, 2, 3, 4, 6, 8, 12, 24
.
Ràng buộc:
•
Có 20% số test ứng với 20% số điểm thỏa mãn:
𝑎
1
× 𝑎
2
× … × 𝑎
𝑛
≤ 10
6
;
•
20% số test khác ứng với 20% số điểm thỏa mãn:
𝑎
1
× 𝑎
2
× … × 𝑎
𝑛
≤ 10
12
;
•
30% số test khác ứng với 30% số điểm thỏa mãn:
𝑎
𝑖
là số nguyên tố với mọi
𝑖 = 1, 2, … , 𝑛
;
•
30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Bài 4. Đánh luống (1,5 điểm)
Mảnh vườn của Viện nghiên cứu giống và cây trồng có
𝑛
luống được đánh số từ
1
đến
𝑛
. Luống
𝑖
có độ
cao
𝑎
𝑖
so với mốc tính (
𝑎
𝑖
có thể âm hoặc dương hoặc bằng
0
với
𝑖 = 1, 2, … , 𝑛
), phù hợp với cây trồng
trên luống. Nhiệm vụ sắp tới của Viện là cung cấp cây giống cho
2
loại cây có tác dụng hỗ trợ nhau, loại
cây thứ nhất trồng trên các luống được đánh số lẻ và loại cây thứ hai trồng trên các luống được đánh số
chẵn. Vì vậy người ta phải cải tạo lại cách đánh luống để các luống ở vị trí lẻ có cùng độ cao, các luống
ở vị trí chẵn có cùng độ cao và chênh lệch độ cao giữa hai luống liên tiếp là
𝑘
.
Máy đánh luống chạy dọc theo luống và mỗi lần chạy có thể bóc đất bề mặt, giảm độ cao luống
1
đơn
vị hoặc đắp thêm đất để độ cao luống tăng thêm
1
đơn vị.
Hãy xác định số lần vận hành máy ít nhất để mảnh vườn với các luống có độ cao thỏa mãn yêu cầu mới.
3
Dữ
liệu:
Vào
từ
tệp
văn
bản
dri.inp
.
Dòng
đầu
tiên
chứa
2
số
nguyên
𝑛
và
𝑘
(
1 ≤ 𝑛 ≤ 10
5
; 0 ≤ 𝑘 ≤ 10
9
)
. Dòng thứ hai chứa
𝑛
số nguyên
𝑎
1
, 𝑎
2
, … , 𝑎
𝑛
(|
𝑎
𝑖
|
≤ 10
9
; 𝑖 = 1, 2, … , 𝑛
)
.
Kết quả: Ghi ra tệp văn bản
dri.out
một số nguyên là số lần vận hành máy ít nhất.
Ví dụ:
dri.inp
dri.out
5 1
1 2 3 -1 2
5
Hình vẽ sau minh họa cho ví dụ:
Ràng buộc:
•
Có 30% số test ứng với 30% số điểm thỏa mãn:
𝑛 ≤ 10
3
, 𝑘 ≤ 10
3
,
|
𝑎
𝑖
|
≤ 10
3
;
•
30% số test khác ứng với 30% số điểm thỏa mãn:
𝑛 ≤ 10
5
, 𝑘 ≤ 10
3
,
|
𝑎
𝑖
|
≤ 10
3
;
•
20% số test khác ứng với 20% số điểm thỏa mãn:
𝑘 = 0
;
•
20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.
-------------------------- HẾT --------------------------
-
Thí sinh không được sử dụng tài liệu;
-
Giám thị không giải thích gì thêm.
Họ và tên thí sinh: .................................................................... Số báo danh: ............................................
1
2
3
2
-1
2
2
2
1
1
+1
-
1
-
1
+2
4
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH QUẢNG NINH
HD CHẤM THI TUYỂN SINH VÀO LỚP 10 THPT
Môn thi: TIN HỌC CHUYÊN
(Hướng dẫn này có 08 trang)
I. HƯỚNG DẪN CHUNG
1.
Giám khảo nghiên cứu đề, hướng dẫn chấm, test, code;
2.
Chép bài của thí sinh vào máy chấm. Kiểm tra bài thí sinh trên giấy in và trên máy đảm bảo trùng
khớp;
3.
Thực hiện chấm bài trên máy chấm (bài thi của thí sinh được chấm trên máy tính bằng phần mềm
chấm thi Themis, bản quyền của Cục Quản lý chất lượng);
4.
Kiểm tra kết quả chấm bài (kiểm tra lại các bài có kết quả như không tồn tại bài, lỗi biên dịch,
các bài bị 0 điểm, …);
5.
Tổng hợp kết quả chấm bài của thí sinh. Điểm bài thi được xuất từ phần mềm chấm thi, không
quy tròn điểm của từng câu, điểm của bài thi;
6.
Sau khi chấm bài xong, giám khảo lưu lại toàn bộ dữ liệu của chấm thi bằng phần mềm chấm thi
Themis (Kỳ thi
→
Ghi kỳ thi), ghi ra đĩa CD và nộp cho hội đồng chấm thi để lưu.
II. ĐÁP ÁN, BIỂU ĐIỂM
Bài 1. Ghép từ (3,0 điểm)
Phân bổ điểm
•
Có 20% số test ứng với 20% số điểm thỏa mãn: Xâu
𝑠
chỉ chứa các ký tự ‘
A
’, ‘
C
’, ‘
N
’, ‘
O
’ và
1 ≤
|
𝑠
|
≤ 10
;
•
40% số test khác ứng với 40% số điểm thỏa mãn:
1 ≤
|
𝑠
|
≤ 10
3
;
•
40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.
Cấu hình bài thi
Hướng dẫn giải
Subtask 1 (20%): Xâu
𝒔
chỉ chứa các ký tự ‘
A
’, ‘
C
’, ‘
N
’, ‘
O
’ và
𝟏 ≤
|
𝒔
|
≤ 𝟏𝟎
Mỗi cách hoán đổi các cặp chữ cái của xâu s cho ta một hoán vị các ký tự của xâu
𝑠
. Vì vậy ta duyệt tất
cả các hoán vị các ký tự của xâu
𝑠
, mỗi hoán vị đó ta đếm xem có bao nhiêu từ “
CONAN
” được tạo ra và
cập nhật số từ lớn nhất.
ĐỀ THI MINH HỌA
5
Độ phức tạp thuật toán là
𝑂
(
𝑛!
)
với
𝑛 =
|
𝑠
|
.
Subtask 2 (40%):
𝟏 ≤
|
𝒔
|
≤ 𝟏𝟎
𝟑
Từ “
CONAN
” đầu tiên được xây dựng như sau:
•
Tìm một ký tự ‘
C
’ và hoán đổi nó với ký tự ở vị trí thứ nhất;
•
Tìm một ký tự ‘
O
’ và hoán đổi nó với ký tự ở vị trí thứ hai;
•
Tìm một ký tự ‘
N
’ và hoán đổi nó với ký tự ở vị trí thứ ba;
•
Tìm một ký tự ‘
A
’ và hoán đổi nó với ký tự ở vị trí thứ tư;
•
Tìm một ký tự ‘
N
’ khác và hoán đổi nó với ký tự ở vị trí thứ năm.
Ta lại tiếp tục xây dựng với từ “
CONAN
” tiếp theo. Cứ làm như vậy cho đến khi không xây dựng được
nữa thì thôi.
Độ phức tạp thuật toán là
𝑂
(
𝑛
2
)
.
Subtask 3 (40%): Không có thêm ràng buộc nào
Gọi
𝑐𝑛𝑡𝐶, 𝑐𝑛𝑡𝑂, 𝑐𝑛𝑡𝑁, 𝑐𝑛𝑡𝐴
là số ký tự ‘
C
’, ‘
O
’, ‘
N
’, ‘
A
’ trong xâu
𝑠
. Khi đó số từ “
CONAN
” tối đa có
thể tạo ra là:
min {𝑐𝑛𝑡𝐶, 𝑐𝑛𝑡𝑂, ⌊
𝑐𝑛𝑡𝑁
2
⌋ , 𝑐𝑛𝑡𝐴}
Độ phức tạp thuật toán là
𝑂
(
𝑛
)
.
Bài 2. Di chuyển (3,0 điểm)
Phân bổ điểm
•
Có 40% số test ứng với 40% số điểm thỏa mãn:
𝑚 = 1
;
•
30% số test khác ứng với 30% số điểm thỏa mãn:
1 ≤ 𝑚, 𝑛 ≤ 10
3
;
•
30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Cấu hình bài thi
Hướng dẫn giải
Subtask 1 (40%):
𝒎 = 𝟏
Vì chỉ có
1
xe ô tô điện nên duyệt mọi khoảng cách từ ô tô đến các trạm sạc để tìm khoảng cách nhỏ
nhất. Câu trả lời của bài toán sẽ là
min
𝑗=1,2,…,𝑛
(|𝑎
1
− 𝑏
𝑗
|)
.
6
Độ phức tạp thuật toán là
𝑂
(
𝑛
)
.
Subtask 2 (30%):
𝟏 ≤ 𝒎, 𝒏 ≤ 𝟏𝟎
𝟑
Với mỗi xe ô tô điện
𝑖
, ta duyệt mọi khoảng cách từ ô tô này đến các trạm sạc để tìm khoảng cách nhỏ
nhất. Do đó khoảng cách từ xe ô tô điện
𝑖
đến trạm sạc gần nhất là
min
𝑗=1,2,…,𝑛
(|𝑎
𝑖
− 𝑏
𝑗
|)
.
Độ phức tạp thuật toán là
𝑂
(
𝑚 × 𝑛
)
.
Subtask 3 (30%): Không có thêm ràng buộc nào
Thuật toán 1:
Sắp xếp các xe ô tô điện theo tọa độ tăng dần (cần lưu lại chỉ số của các ô tô này) và cũng sắp xếp các
trạm sạc theo tọa độ tăng dần.
Sau đó ta duyệt lần lượt các xe ô tô điện theo thứ tự sắp xếp. Với mỗi xe ô tô điện
𝑖
(chú ý chỉ số
𝑖
này
là theo thứ tự sắp xếp), ta tìm trạm sạc
𝑙
bên trái gần nhất và trạm sạc
𝑟
bên phải gần nhất. Khi đó khoảng
cách từ xe ô tô điện này đến trạm sạc gần nhất là
min
(
𝑎
𝑖
. 𝑓𝑖𝑟𝑠𝑡 − 𝑏
𝑙
, 𝑏
𝑟
− 𝑎
𝑖
. 𝑓𝑖𝑟𝑠𝑡
)
, trong đó
𝑎
𝑖
. 𝑓𝑖𝑟𝑠𝑡
là tọa độ của xe ô tô điện thứ
𝑖
. Việc tìm
𝑙, 𝑟
không phải bắt đầu lại từ đầu mà tiếp tục kế thừa việc tìm
kiếm ở bước trước.
Vì ta cần phải trả lời cho các ô tô theo thứ tự ban đầu, nên ta cần phải lưu lại các câu trả lời này, tức là
𝑎𝑛𝑠
[
𝑎
𝑖
. 𝑠𝑒𝑐𝑜𝑛𝑑
]
= min
(
𝑎
𝑖
. 𝑓𝑖𝑟𝑠𝑡 − 𝑏
𝑙
, 𝑏
𝑟
− 𝑎
𝑖
. 𝑓𝑖𝑟𝑠𝑡
)
, trong đó
𝑎
𝑖
. 𝑠𝑒𝑐𝑜𝑛𝑑
là chỉ số ban đầu của xe ô
tô điện.
Ngoài ra để đảm bảo mọi xe ô tô điện luôn có
2
trạm sạc ở bên trái và bên phải, ta sẽ thêm vào hai trạm
sạc “giả” ở vị trí
𝑏
0
= −∞
và
𝑏
𝑛+1
= +∞
.
int m, n;
pair<int, int> a[100001];
long long b[100002];
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i].first;
a[i].second = i;
}
sort(a + 1, a + 1 + m);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> b[i];
sort(b + 1, b + 1 + n);
b[0] = -1e18;
b[n + 1] = 1e18;
int ans[100001];
for (int i = 1, l = 0, r = 0; i <= m; i++) {
while (b[l + 1] <= a[i].first)
l++;
while (b[r] < a[i].first)
r++;
ans[a[i].second] = min(a[i].first - b[l], b[r] - a[i].first);
}
for (int i = 1; i <= m; i++)
cout << ans[i] << "\n";
Độ phức tạp thuật toán là
𝑂
(
𝑛. log
2
𝑛
)
.
Thuật toán 2:
Tương tự như thuật toán 1, nhưng để tìm trạm sạc ở bên trái và bên phải gần nhất cho mỗi xe ô tô điện
ta sử dụng thuật toán tìm kiếm nhị phân. Vì vậy các ô tô không cần sắp xếp theo tọa độ, chỉ có các trạm
sạc cần sắp xếp theo tọa độ và đưa ra được ngay câu trả lời cho mỗi xe ô tô điện.
int m, n, a[100001];
long long b[100002];
7
cin >> m;
for (int i = 1; i <= m; i++)
cin >> a[i];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> b[i];
sort(b + 1, b + 1 + n);
b[0] = -1e18;
b[n + 1] = 1e18;
for (int i = 1; i <= m; i++) {
int r = upper_bound(b + 1, b + 1 + n, a[i]) - b, l = r - 1;
cout << min(a[i] - b[l], b[r] - a[i]) << "\n";
}
Độ phức tạp thuật toán là
𝑂
(
𝑛. log
2
𝑛
)
.
Bài 3. Số ước (2,5 điểm)
Phân bổ điểm
•
Có 20% số test ứng với 20% số điểm thỏa mãn:
𝑎
1
× 𝑎
2
× … × 𝑎
𝑛
≤ 10
6
;
•
20% số test khác ứng với 20% số điểm thỏa mãn:
𝑎
1
× 𝑎
2
× … × 𝑎
𝑛
≤ 10
12
;
•
30% số test khác ứng với 30% số điểm thỏa mãn:
𝑎
𝑖
là số nguyên tố với mọi
𝑖 = 1, 2, … , 𝑛
;
•
30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Cấu hình bài thi
Hướng dẫn giải
Subtask 1 (20%):
𝒂
𝟏
× 𝒂
𝟐
× … × 𝒂
𝒏
≤ 𝟏𝟎
𝟔
Tích của các số trong dãy không vượt quá
10
6
. Với ràng buộc này, ta có thể tính tích của các số trong
dãy trực tiếp và sau đó tính số ước của tích này theo cách đơn giản.
Độ phức tạp thuật toán
𝑂
(
𝑎
1
× 𝑎
2
× … × 𝑎
𝑛
)
.
Subtask 2 (20%):
𝒂
𝟏
× 𝒂
𝟐
× … × 𝒂
𝒏
≤ 𝟏𝟎
𝟏𝟐
Tích của các số trong dãy không vượt quá
10
12
. Vẫn có thể sử dụng phương pháp tính trực tiếp tích và
sau đó đếm ước bằng cách nhanh hơn (duyệt một nửa số ước đến căn bậc
2
của tích).
Độ phức tạp thuật toán là
𝑂(
√
𝑎
1
× 𝑎
2
× … × 𝑎
𝑛
)
.
Subtask 3 (30%):
𝒂
𝒊
là số nguyên tố với mọi
𝒊 = 𝟏, 𝟐, … , 𝒏
Ta biết rằng nếu số tự nhiên
𝑛 > 1
có dạng phân tích ra thừa số nguyên tố
𝑛 = 𝑝
1
𝛼
1
. 𝑝
2
𝛼
2
… 𝑝
𝑘
𝛼
𝑘
, thì số
8
ước của
𝑛
là
(
𝛼
1
+ 1
)(
𝛼
2
+ 1
)
…
(
𝛼
𝑘
+ 1
)
.
Vì vậy ta gọi
𝑐𝑛𝑡
[
𝑖
]
là số phần tử trong dãy có giá trị bằng
𝑖
(
𝑖 = 1, 2, … , 10
6
)
. Vì vậy câu trả lời của bài toán là:
(
𝑐𝑛𝑡
[
1
]
+ 1
)(
𝑐𝑛𝑡
[
2
]
+ 1
)
…
(
𝑐𝑛𝑡
[
10
6
]
+ 1
)
mod
(
10
9
+ 7
)
trong đó
mod
là phép chia lấy số dư (giống phép
%
trong
C++
).
Độ phức tạp thuật toán là
𝑂
(
𝑛
)
.
Subtask 4 (30%): Không có thêm ràng buộc nào
Ta làm giống như subtask 3 nhưng cần phân tích các
𝑎
𝑖
ra thừa số nguyên tố.
Để phân tích nhanh các
𝑎
𝑖
ra thừa số nguyên tố, ta cần tính trước
𝑙𝑒𝑎𝑠𝑡_𝑝𝑟𝑖𝑚𝑒[𝑖]
là ước nguyên tố nhỏ
nhất của số
𝑖
(
𝑖 = 2, 3, … , 10
6
)
. Mảng
𝑙𝑒𝑎𝑠𝑡_𝑝𝑟𝑖𝑚𝑒[𝑖]
được xây dựng bằng thuật toán sàng nguyên tố
Eratosthenes sửa đổi.
const int MOD = 1e9 + 7;
int least_prime[1000001], cnt[1000001];
for (int i = 2; i <= 1e6; i++) least_prime[i] = i;
for (int i = 2; i * i <= 1e6; i++)
if (least_prime[i] == i) {
for (int j = i * i; j <= 1e6; j += i)
if (least_prime[j] == j) least_prime[j] = i;
}
memset(cnt, 0, sizeof(cnt));
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
while (a > 1) {
cnt[least_prime[a]]++;
a /= least_prime[a];
}
}
long long ans = 1;
for (int i = 1; i <= 1e6; i++) ans = ans * (cnt[i] + 1) % MOD;
cout << ans << "\n";
Độ phức tạp thuật toán là
𝑂 (𝑛.ln(ln
√
𝑛))
.
Bài 4. Đánh luống (1,5 điểm)
Phân bổ điểm
•
Có 30% số test ứng với 30% số điểm thỏa mãn:
𝑛 ≤ 10
3
, 𝑘 ≤ 10
3
,
|
𝑎
𝑖
|
≤ 10
3
;
•
30% số test khác ứng với 30% số điểm thỏa mãn:
𝑛 ≤ 10
5
, 𝑘 ≤ 10
3
,
|
𝑎
𝑖
|
≤ 10
3
;
•
20% số test khác ứng với 20% số điểm thỏa mãn:
𝑘 = 0
;
•
20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.
Cấu hình bài thi
9
Hướng dẫn giải
Subtask 1 (30%):
𝒏 ≤ 𝟏𝟎
𝟑
, 𝒌 ≤ 𝟏𝟎
𝟑
,
|
𝒂
𝒊
|
≤ 𝟏𝟎
𝟑
Ta có thể tóm tắt bài toán như sau. Cho một dãy số
𝑎
1
, 𝑎
2
, … , 𝑎
𝑛
và một số
𝑘
. Trong mỗi hành động, ta
có thể thêm hoặc bớt một phần tử đi
1
. Yêu cầu của bài toán là tìm số hành động tối thiểu để dãy số có
một trong hai dạng sau:
•
ℎ, ℎ + 𝑘, ℎ, ℎ + 𝑘, …
•
ℎ, ℎ − 𝑘, ℎ, ℎ − 𝑘, …
Xét mỗi giá trị của
ℎ ∈
[
−3000; 3000
]
, ta tính số hành động để dãy số có một trong hai dạng trên. Cập
nhật số hành động tối thiểu là câu trả lời của bài toán.
long long ans = 1e18;
for (int h = -3000; h <= 3000; h++) {
// TH1: h, h + k, h, h + k, ...
long long sum1 = 0;
for (int i = 1; i <= n; i++)
if (i % 2 == 1)
sum1 += abs(a[i] - h);
else
sum1 += abs(a[i] - (h + k));
// TH2: h, h - k, h, h - k, ...
long long sum2 = 0;
for (int i = 1; i <= n; i++)
if (i % 2 == 1)
sum2 += abs(a[i] - h);
else
sum2 += abs(a[i] - (h - k));
ans = min({ans, sum1, sum2});
}
cout << ans << "\n";
Độ phức tạp thuật toán là
𝑂
(
6000 × 𝑛
)
.
Subtask 2 (30%):
𝒏 ≤ 𝟏𝟎
𝟓
, 𝒌 ≤ 𝟏𝟎
𝟑
,
|
𝒂
𝒊
|
≤ 𝟏𝟎
𝟑
Ta cải tiến thuật toán trong subtask 1.
Trong subtask 2 ràng buộc của
𝑘
và
𝑎
𝑖
là giống subtask 1, nhưng số luống
𝑛
trong subtask 2 thì lớn hơn.
Vì vậy để xử lý độ cao của các luống, ta dùng kỹ thuật đếm phân phối. Gọi
𝑐𝑛𝑡1
[
𝑖
]
, 𝑐𝑛𝑡2
[
𝑖
]
là số luống
có độ cao
𝑖
ở hàng vị trí lẻ và chẵn tương ứng.
map<int, int> cnt1, cnt2;
for (int i = 1; i <= n; i++)
if (i % 2 == 1)
10
cnt1[a[i]]++;
else
cnt2[a[i]]++;
long long ans = 1e18;
for (int h = -3000; h <= 3000; h++) {
// TH1: h, h + k, h, h + k, ...
long long sum1 = 0;
for (auto [u, v]: cnt1)
sum1 += abs(u - h) * v;
for (auto [u, v]: cnt2)
sum1 += abs(u - (h + k)) * v;
// TH2: h, h - k, h, h - k, ...
long long sum2 = 0;
for (auto [u, v]: cnt1)
sum2 += abs(u - h) * v;
for (auto [u, v]: cnt2)
sum2 += abs(u - (h - k)) * v;
ans = min({ans, sum1, sum2});
}
cout << ans << "\n";
Độ phức tạp thuật toán là
𝑂
(
6000
2
)
.
Subtask 3 (20%):
𝒌 = 𝟎
Trong subtask này
𝑘 = 0
, tức là san tất cả các luống cao bằng nhau.
Gọi độ cao của luống sau khi san bằng là
ℎ
. Số lần san sẽ là:
∑
|
𝑎
𝑖
− ℎ
|
𝑛
𝑖=1
Tổng này nhận giá trị nhỏ nhất khi
ℎ
bằng phần tử trung vị của dãy
𝑎
𝑖
, tức là
ℎ
là phần tử chính giữa
dãy sau khi đã sắp xếp tăng dần.
Có 2 cách để lấy phần tử phần tử trung vị của dãy
𝑎
𝑖
:
•
Cách 1: Sắp xếp dãy các giá trị
𝑎
𝑖
theo thứ tự tăng. Phần tử trung vị là
𝑎
⌊
𝑛+1
2
⌋
. Độ phức tạp là
𝑂
(
𝑛. log
2
𝑛
)
;
•
Cách 2: Dùng hàm
nth_element(first, nth, last)
sắp xếp lại các phần tử trong phạm
vi
[
𝑓𝑖𝑟𝑠𝑡, 𝑙𝑎𝑠𝑡
)
theo cách mà phần tử thứ
nth
sẽ là phần tử nhỏ thứ
nth
. Các phần tử khác không
được đảm bảo sẽ sắp xếp, nhưng tất cả các phần tử trước
nth
sẽ nhỏ hơn hoặc bằng phần tử tại
nth
và tất cả các phần tử sau
nth
sẽ lớn hơn hoặc bằng phần tử tại
nth
. Độ phức tạp
𝑂
(
𝑙𝑎𝑠𝑡 − 𝑓𝑖𝑟𝑠𝑡
)
.
nth_element(a + 1, a + (n + 1) / 2, a + 1 + n);
long long sum = 0;
for (int i = 1; i <= n; i++)
sum += abs(a[i] - a[(n + 1) / 2]);
cout << sum << "\n";
Độ phức tạp thuật toán là
𝑂
(
𝑛
)
.
Subtask 4 (20%): Không có thêm ràng buộc nào
11
Bây giờ ta xét bài toán tổng quát.
Trường hợp các luống có dạng
ℎ, ℎ + 𝑘, ℎ, ℎ + 𝑘, …
Nếu ta lấy độ cao tất cả các luống ở vị trí lẻ cộng
thêm
𝑘
thì bài toán cần giải tương đương với bài toán san bằng với các giá trị
𝑎
𝑖
mới (như trường hợp
của subtask 3).
Trường hợp các luống có dạng
ℎ, ℎ − 𝑘, ℎ, ℎ − 𝑘, …
Nếu ta lấy độ cao tất cả các luống ở vị trí lẻ trừ đi
𝑘
thì bài toán cần giải tương đương với bài toán san bằng với các giá trị
𝑎
𝑖
mới (như trường hợp của
subtask 3).
// TH1: h, h + k, h, h + k, ...
long long b[100001];
for (int i = 1; i <= n; i++)
if (i % 2 == 1)
b[i] = a[i] + k;
else
b[i] = a[i];
nth_element(b + 1, b + (n + 1) / 2, b + 1 + n);
long long sum1 = 0;
for (int i = 1; i <= n; i++)
sum1 += abs(b[i] - b[(n + 1) / 2]);
// TH2: h, h - k, h, h - k, ...
for (int i = 1; i <= n; i++)
if (i % 2 == 1)
b[i] = a[i] - k;
else
b[i] = a[i];
nth_element(b + 1, b + (n + 1) / 2, b + 1 + n);
long long sum2 = 0;
for (int i = 1; i <= n; i++)
sum2 += abs(b[i] - b[(n + 1) / 2]);
cout << min(sum1, sum2) << "\n";
Độ phức tạp thuật toán là
𝑂
(
𝑛
)
.
-------------------------- HẾT --------------------------