Loop
Đề bài
Hoàng thiết kế được một con robot tự động. Nhiệm vụ của con robot là lặp lại các giá trị mà nó nhận được. Dữ liệu vào của con robot là một mảng gồm $n$ giá trị nguyên dương $a_1, a_2, \ldots, a_n$ và giá trị khóa $k \ge 2$. Robot bắt đầu ở vị trí 1 của mảng. Ở vị trí hiện tại (vị trí thứ $i$) của robot thực hiện:
- Nếu $a_i$ chia hết cho $k$ thì robot thêm $k$ giá trị $a_i / k$ vào cuối cùng của mảng rồi chuyển đến vị trí $i + 1$;
- Nếu $a_i$ không chia hết cho $k$ thì robot dừng lại, nhiệm vụ hoàn thành.
Yêu cầu: cho trước $n$, $k$ và các giá trị $a_1, a_2, \ldots, a_n$, hãy tính tổng các giá trị của mảng sau khi robot hoàn thành nhiệm vụ.
Dữ liệu
- Dòng đầu tiên gồm 2 số nguyên dương $n, k$ ($1 \le n \le 10^6$, $2 \le k \le 10^9$).
- Dòng thứ 2 gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).
Kết quả: in ra màn hình một số là kết quả tìm được.
Giới hạn
- Subtask 1: 40% số test đầu tiên có $n \le 10^3$.
- Subtask 2: 40% số test tiếp theo có $n \le 10^5$.
- Subtask 3: 20% số test còn lại không có giới hạn gì thêm.
1 2
12364 2
4 6 8 244Giải thích ví dụ 1: có 1 giá trị 12. Robot xử lí ở giá trị đầu tiên với $k = 2$, mảng trở thành 12, 6, 6. Robot xử lí giá trị thứ 2, mảng trở thành 12, 6, 6, 3, 3. Robot xử lí giá trị thứ 3, mảng trở thành 12, 6, 6, 3, 3, 3, 3. Khi robot xử lí giá trị thứ 4 (không chia hết cho $k$) nên robot dừng lại, vậy tổng của mảng sẽ là 36.
Giải thích ví dụ 2: mảng sau khi xử lí: 4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1. Tổng là 44.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
40%Cách vét cạn: làm y như đề mô tả
Bài này em có thể giải quyết theo cách làm vét cạn không? Để từ đó ta lấy nó làm công cụ kiểm tra cho tính chính xác của các cách làm khác đó mà. Bởi vì cách vét cạn luôn đảm bảo cho ra kết quả chính xác, chỉ có cái là nó chạy rất lâu thôi, thì mình có thể sinh ra các dữ liệu nhỏ đủ để nó chạy nhanh trong khoảng 1 giây, từ đó so kết quả với các cách làm tối ưu để kiểm tra độ chính xác. Anh có hướng dẫn kỹ thuật này trong bài viết Hạn chế lỗi Wrong Answer nhé.
Thì cách vét cạn của bài này đơn giản là làm theo đúng y như quy trình mà đề bài mô tả thôi. Ta có thể dùng cấu trúc dữ liệu vector để khi cần thêm dữ liệu vào thì cứ push_back vào thôi. Đầu tiên vector chứa mảng a từ input. Sau đó xét từ đầu mảng trở đi, với mỗi giá trị a[i], nếu a[i] chia hết cho $k$ thì ta thêm $k$ lần giá trị a[i] / k vào cuối vector, rồi lại xét lên a[i] tiếp theo và lặp lại quy trình. Đến khi nào gặp a[i] không chia hết cho $k$ thì dừng lại. Khi đó ta duyệt qua vector tính tổng các phần tử thì đó là đáp án.
Nhìn thì đơn giản như vậy nhưng chắc chắn đem cách này đi nộp thì không thể nào ổn, vì hãy thử nhìn xem trường hợp xấu nhất có thể xảy ra là gì? Đó là khi lúc nào a[i] cũng luôn chia hết cho $k$, ví dụ $k = 2$ và toàn bộ a[i] đều là $2^{29} = 536\,870\,912$:
- Đầu tiên mảng có $N$ phần tử. Mỗi phần tử đều chia hết cho $k$, tức là mỗi phần tử đều tạo ra thêm $k = 2$ phần tử mới. Như vậy xét hết $N$ phần tử đó thì số phần tử mới được tạo ra sẽ là $2N$.
- Tiếp tục xét hết $2N$ phần tử đó thì lại tạo ra $2^2 N$ phần tử mới; xét hết $2^2 N$ phần tử đó lại tạo ra $2^3 N$ phần tử mới, …
- Cứ như vậy liên tục đủ 29 lần, ở lần cuối cùng xét hết $2^{29} N$ phần tử thì lại tạo ra $2^{30} N$ phần tử mới, mỗi phần tử có giá trị 1. Khi xét vào phần tử đầu tiên trong đó, 1 không chia hết cho 2 nên dừng lại.
Vậy tổng số phần tử là $N \cdot (2^0 + 2^1 + 2^2 + \ldots + 2^{30})$ $= N \cdot (2^{31} - 1)$, trừ đi 1 quá nhỏ nên xem như $2^{31} \cdot N$. Đề cho $N$ tối đa là $10^6$, vì vậy tổng số phần tử lúc này sẽ cỡ $2^{31} \cdot 10^6 \approx 2.1 \cdot 10^{15}$ phần tử! Với số lượng phần tử như thế này thì chẳng thể nào lưu trữ nổi vào bộ nhớ, tức là sẽ bị lỗi MLE (Memory Limit Exceeded), và chắc chắn cũng sẽ bị TLE luôn vì ngưỡng 1 giây chỉ duyệt tối đa khoảng $10^8$ thôi, thế này gấp cả chục triệu lần rồi.
Nên cách làm vét cạn chắc chắn là không ổn với trường hợp xấu nhất này. Nhưng ta vẫn cứ cài đặt nó để lấy làm công cụ kiểm tra tính chính xác cho cách làm tối ưu như đã nói. Code này cả C++ và Python được 40/100.
Xem code vét cạn (40% điểm)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < a.size(); ++i){
if(a[i] % k == 0){
for(int j = 0; j < k; ++j){
a.push_back(a[i] / k);
}
}
else{
break;
}
}
long long sum = 0;
for(int i = 0; i < a.size(); ++i){
sum += a[i];
}
cout << sum;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
i = 0
while i < len(a):
if a[i] % k == 0:
for _ in range(k):
a.append(a[i] // k)
else:
break
i += 1
total = sum(a)
print(total)100%Cách tối ưu: nhìn ra quy luật
Đề bài cố tình đưa ra cách làm khiến ta bị rối, anh gợi ý cho em để nhìn ra điểm mấu chốt nha: nếu số a[i] chia hết cho $k$ thì viết tiếp $k$ lần giá trị a[i] / k vào cuối dãy. Em ngẫm đi, ví dụ a[i] = 10, $k = 2$ thì viết tiếp 2 lần giá trị $10 / 2 = 5$, tức là viết 2 số 5: 5 5, thì có phải tổng $k$ số a[i] / k cũng bằng đúng a[i] không? Nhìn ra được điều này là mấu chốt để em ra được cách tối ưu. Giờ xem tiếp nhé, anh sẽ cho em thấy điều vi diệu :))
Như ví dụ 2: $N = 4$, $K = 2$, mảng 4, 6, 8, 2. Đầu tiên, với từng phần tử trong mảng, em tính xem nó có thể liên tục chia cho K được bao nhiêu lần:
| a[i] | Chia liên tục cho K | Số lần |
|---|---|---|
| 4 | 4/2=2, 2/2=1, 1/2 = không chia hết | 2 |
| 6 | 6/2=3, 3/2 = không chia hết | 1 |
| 8 | 8/2=4, 4/2=2, 2/2=1, 1/2 = không chia hết | 3 |
| 2 | 2/2=1, 1/2 = không chia hết | 1 |
Vậy ta có số lần chia liên tiếp được cho $K$ của các phần tử là: 2, 1, 3, 1. Ta thấy $Min = 1$, ta cộng 1 lên cho $Min$ thì được 2. Gọi $sum$ là tổng các phần tử của mảng, $sum = 4 + 6 + 8 + 2 = 20$, thì đáp án trước mắt sẽ là $(Min + 1) \cdot sum = 2 \cdot 20 = 40$. Và $Min = 1$ đó nằm ngay tại a[2] (tính index từ 1, lấy vị trí đầu tiên đạt Min), nên có nghĩa là nó sẽ nhận thêm tổng các số trước a[2], tức là a[1] = 4, từ đó $40 + 4 = 44$ và 44 là đáp án. Đó là quy luật có thể thấy của bài này.
Để thấy rõ vì sao, em nhìn robot đi qua mảng theo từng "lượt" nhé: lượt 0 là mảng ban đầu, lượt 1 là các giá trị sinh ra từ lượt 0, lượt 2 là các giá trị sinh ra từ lượt 1, … Vì $k$ số a[i] / k có tổng bằng a[i], nên mỗi lượt robot đi trọn vẹn đều cộng thêm đúng $sum$:
| Các giá trị trong mảng (theo từng khối sinh ra từ a[1], a[2], …) | Tổng | |
|---|---|---|
| Lượt 0 | 4682 | 20 |
| Lượt 1 | 2 23 34 41 1 robot dừng ở ô gạch | 20 |
| Lượt 2 | 1 1 1 1 chỉ kịp sinh ra từ các khối đứng trước ô dừng | 4 |
| Tổng cả mảng | 44 | |
a[i] chia liên tiếp được cho $K$, $Min = \min(cnt_i)$ và $p$ là vị trí đầu tiên có $cnt_p = Min$. Các lượt từ 0 đến $Min$ đều được sinh ra đầy đủ, mỗi lượt có tổng đúng bằng $sum$; robot dừng ở lượt $Min$, tại khối sinh ra từ a[p] (vì a[p] chia được cho $K$ đúng $Min$ lần), nên lượt $Min + 1$ chỉ kịp được sinh ra từ các khối của a[1] … a[p − 1], tổng bằng a[1] + … + a[p − 1]. Vậy:Đáp án = sum · (Min + 1) + (a[1] + a[2] + … + a[p − 1])
Thử áp dụng quy luật với ví dụ 1: $N = 1$, $K = 2$, mảng là 12. Thì $12 / 2 = 6$, $6 / 2 = 3$, $3 / 2$ không chia hết, vậy 12 chia cho $K$ tối đa được 2 lần, xem như $Min = 2$, $Min + 1 = 3$, $sum = 12$ (vì chỉ có mình nó) nên $(Min + 1) \cdot sum = 3 \cdot 12 = 36$. Tại vị trí a[1] là Min, trước a[1] không có thằng nào cả nên xem như là 0. Vậy $36 + 0 = 36$, đáp án sẽ là 36.
Em nhập $k$ và mảng $a$ rồi bấm Tiếp để xem robot đi từng ô. Các số sinh ra được xếp theo từng lượt, cùng màu là cùng "họ" sinh ra từ một số $a_i$ ban đầu, cột bên phải là tổng của mỗi lượt:
Đó, anh đã chỉ cho em nhìn ra tư tưởng giải quyết. Với tư tưởng đã rõ ràng thông qua 2 ví dụ thì anh tin là sẽ rất dễ dàng cho em trong việc cài đặt. Chắc chắn là việc dùng 1 mảng lưu trữ sẽ làm cho mọi thứ dễ hơn rất nhiều (trong code, mảng a[i] lưu luôn tổng các số đứng trước vị trí $i$). Độ phức tạp thời gian là $O(N \cdot \log_K a_i)$ ($N$ nhân logarit cơ số $K$ của $a_i$), bộ nhớ $O(N)$, và full 100/100 điểm.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, x;
cin >> n >> k;
long long sum = 0;
long long Min = LLONG_MAX, idxMin;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> x;
a[i] = sum;
sum += x;
long long cnt = 0;
while(x % k == 0){
cnt++;
x /= k;
}
if(cnt < Min){
Min = cnt;
idxMin = i;
}
}
cout << sum * (Min + 1) + a[idxMin];
return 0;
}import sys
input = sys.stdin.readline
n, k = map(int, input().split())
arr = list(map(int, input().split()))
s = 0
Min = float('inf')
idxMin = -1
a = [0] * n
for i in range(n):
x = arr[i]
a[i] = s
s += x
cnt = 0
tmp = x
while tmp % k == 0:
cnt += 1
tmp //= k
if cnt < Min:
Min = cnt
idxMin = i
print(s * (Min + 1) + a[idxMin])Khi nộp: bản C++ có test chạy chậm nhất là 0.48 s, bộ nhớ nhiều nhất 10.86 MB; bản Python chậm nhất 0.40 s, bộ nhớ nhiều nhất 174.87 MB.
Thử tháchKhông dùng mảng – bộ nhớ O(1)
Anh cũng thử thách em: liệu em có thể giải quyết mà không cần dùng mảng không? Tức là chỉ cần dùng vài biến phụ thôi, độ phức tạp không gian (bộ nhớ) sẽ là $O(1)$. Ý tưởng là mỗi khi gặp một $cnt$ nhỏ hơn $Min$ hiện tại thì lưu ngay tổng các số đứng trước nó vào biến sum1, rồi mới cộng $x$ vào sum:
Xem code bộ nhớ O(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, x, temp_x;
cin >> n >> k;
long long sum = 0;
long long Min = LLONG_MAX;
long long sum1 = 0;
for(int i = 0; i < n; ++i){
cin >> x;
temp_x = x;
long long cnt = 0;
while(temp_x % k == 0){
cnt++;
temp_x /= k;
}
if(cnt < Min){
Min = cnt;
sum1 = sum;
}
sum += x;
}
cout << sum * (Min + 1) + sum1;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
if not data:
sys.exit(0)
it = iter(map(int, data))
n = next(it)
k = next(it)
s = 0
Min = float('inf')
sum1 = 0
for _ in range(n):
x = next(it)
tmp = x
cnt = 0
while tmp % k == 0:
cnt += 1
tmp //= k
if cnt < Min:
Min = cnt
sum1 = s
s += x
print(s * (Min + 1) + sum1)Khi nộp: bản C++ có test chạy chậm nhất là 0.87 s, bộ nhớ nhiều nhất 2.11 MB; bản Python chậm nhất 0.79 s, bộ nhớ nhiều nhất 145.19 MB.
Ta cũng nhận ra 1 vấn đề: cách làm full điểm có dùng mảng lại chạy nhanh hơn cách không dùng mảng gần 2 lần (con số này còn phụ thuộc vào tải của máy chấm lúc nộp nữa). Mặc dù về độ phức tạp thời gian tụi nó đều bằng nhau, nên cái này chỉ là thử thách luyện tư duy thôi, chứ đi thi thì em làm cách dùng mảng là được nhé cho đơn giản, vì bộ nhớ lúc nào cũng cho rất dư dả, không sợ bị thiếu đến mức phải tối ưu thế này đâu.
Mình đã kiểm tra cả 3 cách với 500 bộ test ngẫu nhiên so với cách mô phỏng, đều cho cùng kết quả. Với test xấu nhất tự tạo ($n = 10^6$, $k = 2$, mọi $a_i = 2^{29}$, mỗi số phải chia 29 lần) thì bản C++ chạy khoảng 0.28 giây, còn bản Python khoảng 4.6 giây; test thật trên hệ thống nhẹ hơn nên Python vẫn AC như số liệu ở trên.
Nhận xét
Đăng nhận xét