# Chuyen Quang Tri 2024-2025
Link chấm thử: https://codeforces.com/gym/527480/
## Bài 1: Đèn chiếu sáng
### Tóm tắt đề bài:
Cho 1 bảng n * m. Cho một hình vuông có kích thước k * k, tìm số lượng hình vuông nhỏ nhất để fill đầy bảng
### Ý tưởng
Đây là một bài toán về toán học, có thể dễ dàng nhận thấy vì giới hạn bài tới 10^9 cho từng n, m, k
-> Không thể giải bằng các phương pháp duyệt thông thường
Như ta thấy để đặt số lượng cần thiết thì ta cần n (hoặc m) / k
Nhưng sẽ có trường hợp dư ra như *ví dụ 2*:
```10 9 3```
Như vậy ta chỉ cần cộng thêm **1** vào phần dư của phép chia n (hoặc m) / k
==> Công thức tổng quát là:
```cpp
res = (a / k) + ((a % k) ? 1 : 0)
```
với **a** là hàng hoặc cột (n || m)
có thể sử dụng toán tử ba ngôi để tính nhanh phần dư hoặc có thể sử dụng câu điều kiện:
```cpp
if (a % k != 0)
res++;
```
Code tham khảo: https://www.ideone.com/qra9uv
## Bài 2: Tạo số
### Tóm tắt đề bài
Cho sâu S chỉ gồm các kí tự nằm trong 1 trong 3 loại kí tự {+, -, =}
Có quy tắc:
* Nếu dấu ' + ' thì chữ số tiếp theo sẽ +1 đơn vị chữ số kế trước đó
* Nếu là dấu ' - ' thì chữ số tiếp theo sẽ -1 đơn vị chữ số kế trước đó
* Nếu là dấu ' = ' thì chữ số tiếp theo sẽ = đơn vị chữ số kế trước đó
*Yêu cầu*: Bắt đầu từ 1 số nguyên n (n ∈ N*, n < 10). Hãy tìm ra số N gồm S + 1 chữ số và là **nhỏ nhất** nếu không có in ra số **0**
### Ý tưởng
Vì đề bài sâu S có số kí tự không quá 100 kí tự nên ta có thể dễ dàng duyệt tất cả trường hợp của đề bài
Thứ tự các bước duyệt:
* Ban đầu ta sẽ cho kết quả là một số lớn
```string ans = "9999999999999999";```
Ở đây ta sử dụng string vì N có thể có đến 100 chữ số
* Ta sẽ i duyệt từ 1 -> 9
* Ta sẽ khai báo một string tạm để lưu kết quả thử tại i
```string tmp = "";```
* Duyệt tất cả các kí tự trong sâu S
*Có thể sử dụng for auto để lấy các kí tự ra nhanh hơn so với truyền thống:*
Cách truyền thống:
```cpp
for(int j = 0; j < S.size(); j++)
if (S[j] == ...)
...
```
Việc phải viết S[j] mỗi khi cần lấy kí tự ra rất mất thời gian nhất là trong phòng thi khi mà thời gian có hạn, cũng như lúc kiểm tra lại cũng rất rối
```cpp
for (auto it : S)
if (it == ...)
...
```
Như vậy lấy phần tử ra đã nhanh hơn và nhìn code cũng đẹp hơn
*Lưu ý: việc sử dụng for auto có thể dẫn đến chấm lỗi file ở themis 1.8 trở xuống (nhưng đa số máy chấm của các kì thi thời điểm hiện tại đa số đều sử dụng themis 1.9 nên không sao)
* Ta xét với mỗi điều kiện ở đề bài:
```cpp
int num = i;
for (auto it : s) {
if (it == '+') {
num++;
tmp += num + '0';
}
else if (it == '-') {
num--;
tmp += num + '0';
}
else
tmp += num + '0';
if (tmp >= 10 || tmp < 0) {
res = ans;
continue;
}
}
```
Ban đầu kí tự đầu tiên trong xâu n của chúng ta là i hay num (khai báo riêng vì ta sẽ tính toán trực tiếp trên num nên cần tách ra để tránh các vấn đề với vòng lập chính)
Với mỗi điều kiện ta xét:
* nếu là dấu + thì ta sẽ tăng num lên 1 đơn vị và bỏ vào tmp
```tmp += num + '0'``` *trong đó* ```num + '0'``` *chính là cách đổi từ số sang kí tự*
* làm tương tự với dấu - và dấu = (dấu = thì giữ nguyên num)
* Một bẫy của bài là giá trị chỉ được nằm [0, 9] nên ta cần thêm điều kiện
```cpp
if (tmp >= 10 || tmp < 0) {
res = ans;
continue;
}
```
* và nếu như tmp của ta bé hơn res thì chỉ cần cập nhật lại res
```cpp
if (res < ans)
ans = res, chk = true;
```
* Và ta chỉ cần kiếm tra lại để in kết quả:
```cpp
if (chk)
cout << ans;
else
cout << 0;
```
Code tham khảo: https://www.ideone.com/VhmcFw
## Bài 3: Trùng nhau
### Đề bài
Cho mảng a gồm n số
Cho mảng b gồm m số
*Yêu cầu*: Tìm số lượng số lượng số trùng nhau và in ra các số đó theo thứ tự tăng dần
### ý tường:
#### Sub 1:
Ta sẽ duyệt trâu tất cả trường hợp
=> Độ phức tạp O(n * m)
Ta chỉ cần đặt 2 for và tìm tất cả phần từ giống nhau
```cpp
int res = 0;
vector<int> trace;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j]) {
res++;
trace.push_back(a[i]);
break;
}
```
Ta cần break mỗi khi tìm thấy tìm mảng b có thể có rất nhiều phần tử b[j] trùng với phần tử a[i] đang xét nên có thể gây ra sai sót.
Code tham khảo: https://www.ideone.com/3zCNkS
#### Sub 2
Chúng ta sẽ sử dụng chặt nhị phân
Nhưng Wi sẽ giới thiệu cho các bạn 2 cách code khác nhau (1 cách truyền thống và 1 cách sử dụng hàm có sẵn của C++)
Nên có thể nói nếu có "Kiến thức, Kinh nghiệm, Trải nghiệm🤓" thì đây là bài dễ nhất trong đề này =))
###### Cách 1:
Ta sẽ dung chặt nhị phân
Đây là mô phỏng thuật toán khi chạy với a[1] = 2
Và ta sẽ chạy việc tìm giá trị giống phần tử a với các phần tử của mảng b
Như ta có thể thấy sau 3 lần chạy thì đã tìm thấy giá trị giống trên ta sẽ ```return true;```
* Bước 0: Với mọi bài chặt nhị phân thì ta luôn cần phải sort lại mảng và ở đây ta cần tìm trên mảng b nên ta sẽ sort lại mảng b
```cpp
sort(b + 1, b + m + 1);
```
* Bước 1: ta cần xây dựng hàm chặt nhị phân
```cpp
bool bn_search(int x) {
int l = 1;
int r = m;
while (l <= r) {
int mid = l + r >> 1;
if (b[mid] == x)
return true;
if (b[mid] > x)
r = mid - 1;
else
l = mid + 1;
}
return false;
}
```
Vì ta chỉ cần tìm có hay không nên ta sẽ chỉ cần trả về giá trị boolean (yes/no)
```int mid = l + r >> 1``` tương đương với ```int mid = (l + r) / 2``` đây là áp dụng của xử lý bit
Việc xét b[mid] > x sẽ chặt nhỏ lại và lấy mid phần nhỏ đó
Cũng như việc làm ngược lại
sẽ chặt lên phần lớn hơn
Trong phần main ta chỉ cần gọi lại hàm bn_search:
```cpp
int res = 0;
vector<int> trace;
for (int i = 1; i <= n; i++)
if (bn_search(a[i])) {
res++;
trace.push_back(a[i]);
}
```
Code tham khảo: https://www.ideone.com/g2CY0Y
###### cách 2:
Ý tưởng như cách 1 nhưng ta không cần phải viết hàm
C++ đã cung cấp ta một hàm cực kì bá đạo là:
``` binary_search(array + 1, array + array_length + 1, element);```
Tuy nhiên hàm này chỉ trả về kiểu boolean nên một số trường hợp ta phải tự dựng hàm chặt nhị phân
```cpp
int res = 0;
vector<int> trace;
for (int i = 1; i <= n; i++)
if (binary_search(b + 1, b + m + 1, a[i]))
{
res++;
trace.push_back(a[i]);
}
```
cực kì nhanh và gọn.
* Bước 2: In kết quả:
```cpp
sort(trace.begin(), trace.end());
cout << res << endl;
for (auto it : trace)
cout << it << " ";
```
*Lưu ý:* Nhớ phải sort lại kết quả, có thể bạn quên vì test mẫu nằm ở trường hợp đã push theo thứ tự tăng dần nên dễ bị bẫy.
Code tham khảo: https://www.ideone.com/iDTw7f
## Bài 4: Độ giống nhau:
### Đề bài:
Cho mảng a gồm n số
Độ giống nhau giữa 2 số là số chữ số tương ứng giống nhau của hai số tính tương ứng theo hàng đơn vị, hàng chục, hàng trăm,...
Ví dụ:
* 69 và 68 -> có độ giống nhau là 1
* 2024 và 02 -> có độ giống nhau là 0
* 2007 và 07 -> có độ giống nhau là 2
*Yêu cầu*: Hãy tính tổng độ giống nhau của tất cả các cặp số hạng trong dãy. Hai số hạng a[i], a[j] của dãy là một cặp nếu i ≠ j.
### Ý tưởng:
#### Sub 1: duyệt trâu, đề kêu gì làm nấy
-> Độ phức tạp O(n * m * k)
trong đó k là chiều dài của phần tử dài nhất (vd: 2024 có k = 4) (max = 9)
Vì duyệt trâu nên ta sẽ xét 2 phần tử bất kì của mảng a
* Để so sánh bước đầu ta sẽ viết hàm chuyển số thành chữ
```cpp
string convert(int x) {
string res = "";
while (x > 0) {
char a = x % 10 + '0';
res = a + res;
x /= 10;
}
return res;
}
```
Có hàm của C++ chuyển thẳng sang chữ nhưng trong các kì thi không khuyên dùng hàm này vì có thể máy chấm không được
* Tiếp theo ta sẽ viết hàm kiểm tra độ giống nhau 2 kí tự
```cpp
int check(int x, int y) {
int cnt = 0;
string s1 = convert(x);
string s2 = convert(y);
if (s1.size() > s2.size())
swap(s1, s2);
while (s1.size() != s2.size())
s1 = 'x' + s1;
for (int i = 0; i < s1.size(); i++)
if (s1[i] == s2[i])
cnt++;
return cnt;
}
```
Việc swap 2 giá trị nhằm xử lý giá trị nhỏ hơn và sau đó thêm vào phía trước số nhỏ hơn kí tự 'x' bất kì (không dược là kí tự số) để đưa 2 số về chung hàng đơn vị, chục, trăm,...
```
VD:
2024 và 24
Ta sẽ swap thành 24 và 2024
Thêm 24 thành: xx24
```
Sau đó ta đi so sánh số lượng kí tự giống nhau.
* hâm main ta chỉ việc chạy 2 for và đếm số lượng đã tính
```cpp
int res = 0;
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
res += check(a[i], a[j]);
cout << res;
```
Code tham khảo: https://www.ideone.com/4aKiKH
#### sub 2: kết hợp sub 1 + sử dụng đếm phân phối
Ta thấy được a[i] <= 1000 (1 <= i <= n)
```
VD:
12 12 13 22
dem[12] = 2
dem[13] = 1
dem[22] = 1
như vậy độ giống nhau của 12 và 13 là 1
và có 2 số 12
1 số 13
=> sum = 1 * 2 * 1
= 2
công thức tổng quát: sum += check(i, j) * dem[i] * dem[j];
```
* đầu tiên ta cần chuẩn bị mảng đếm số lượng số xuất hiện
```cpp
for (int i = 1; i <= n; i++)
dem[a[i]]++;
```
Sau đó là kết hợp sub 1 với đếm phân phối:
```cpp
int res = 0;
for (int i = 1; i < 1000; i++)
for (int j = i; j <= 1000; j++) {
int sum = 0;
sum += check(i, j) * dem[i] * dem[j];
if (i == j) {
sum -= check(i, j) * dem[i];
sum /= 2;
}
res += sum;
}
cout << res;
```
nhưng có trường hợp khi xét 2 số giống nhau thì cần bớt lại 1 phần:
```cpp
if (i == j) {
sum -= check(i, j) * dem[i];
sum /= 2;
}
```
code tham khảo: https://www.ideone.com/GjE1J2
#### Sub 3:
Gọi f[i][j] là số lượng chữ số j mà nằm ở vị trí i (i = 1 -> đơn vị...)
Như vậy đáp án đề bài là tổng của các f[i][j]
```cpp
int res = 0;
for (int i = 1; i <= n; i++) {
int donvi = 1;
while (a[i] > 0) {
res += f[donvi][a[i] % 10];
f[donvi][a[i] % 10]++;
donvi++;
a[i] /= 10;
}
}
cout << res;
```
code tham khảo: https://www.ideone.com/3Dili4
Sign in with Wallet
Connect another wallet