# Chuyên An Giang 2024 - 2025
các bạn có thể chấm thử test tại đây (đây không phải offical test): https://codeforces.com/group/Cv4vM6diPP/contest/528600
## Câu 1:
### Tóm tắt:
Cho tọa độ 3 điểm a, b, c. Hỏi ba điểm đó có tạo thành tam giác vuông không?
### Ý tưởng:
#### sub1:
Nếu bạn không biết cách tính khoảng cách thì có thể sử dụng phương pháp tham sau đây:
* Chúng ta chỉ cần tìm cặp (x, x') và cặp (y, y') bất kì mà nó bằng nhau
VD:
```1 1 5 1 1 7```
Thì ta có thể tìm được cặp (ax, cx) và (ay, by) mà nó bằng nhau
```cpp
bool check(point a, point b, point c) {
if (a.y == b.y && a.x == c.x)
return true;
return false;
}
int main() {
...
if (check(a, b, c) || check(a, c, b) || check(b, a, c) || check(b, c, a) || check(c, a, b) || check(c, b, a))
cout << "TAM GIAC VUONG";
else
cout << "KHONG PHAI TAM GIAC VUONG";
}
```
Chúng ta sẽ xét 3! cách chọn bộ ba a, b, c
Chỉ cần một bộ ba nào đó thỏa mãn thì có nó là tam giác vuông
*bonus thêm:* ~~lúc mình code dòng if kiểm tra thì mình có sử dụng chương trình sinh hoán vị để cho ngầu~~=)))
Các bạn có thể thao khảo=))
```cpp
#include <bits/stdc++.h>
using namespace std;
int x[] = {0, 1, 2}, cnt;
string S = "abc";
int main() {
cout << "if (";
do {
cnt++;
cout << "check(";
for (int i = 0; i < 3; i++) {
cout << S[x[i]];
if (i != 2)
cout << ", ";
}
if (cnt != 6)
cout << ") || ";
} while (next_permutation(x, x + 3));
cout << "))";
}
```
Để làm màu thoi mấy ní vô thi đừng có ngựa như tui nhe=))
Code tham khảo: https://www.ideone.com/9JO4Oa
#### Sub 1 (cách khác):
* Ta sẽ đi tính khoảng cách giữa các cạnh và dùng công thức Pythagoras để kiểm tra tam giác vuông.
Công thức tính khoảng các giữa 2 cạnh: $\sqrt{(b.x-a.x)^2 + (b.y-a.y)^2}$
```cpp
double dist(point a, point b) {
return abs(sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y)) * 1.00);
}
```
* Sau đó ta đi tìm các cạnh dài nhất (giả định làm cạnh huyển) và 2 cạnh còn lại
*chỉ cần if/else đơn giản*
* Cuối cùng ta đi kiểm tra tam giác đó phải tam giác vuông không với công thức: $ch^2 = cv1^2 + cv2^2$
*trong đó:
ch: cạnh huyển
c1: cạnh vuông 1
c2: cạnh vuông 2*
```cpp
int x = round(ch);
int y = round(cv1 + cv2);
if (x == y)
cout << "TAM GIAC VUONG\n";
else
cout << "KHONG PHAI TAM GIAC VUONG\n";
```
Code tham khảo: https://www.ideone.com/LvqYVf
#### sub 2 (riel)
Do admin contest mới chỉnh lại nên mình chia sẻ cách code sub bonus của admin nhé ;)
Có 1 bài tương tự như vậy: https://oj.vnoi.info/problem/pravo
Code tham khảo: https://www.ideone.com/2rjFHm
## Bài 2:
### Tóm tắt:
Viết chương trình tính S = 1 + 3 + 5 + 7 + ... + (2*n - 1)
### Ý tưởng:
#### sub 1: (n <= 1e6)
Ta chỉ cần duyệt trâu các số lẻ:
```cpp
n = n * 2 - 1;
for(int i = 1; i <= n; i+=2)
res += i;
cout << res;
```
code tham khảo: https://www.ideone.com/KFy26F
#### sub 2: (n <= 1e9)
Ta sẽ sử dụng công thức $S = (n+1)^2 / 4$
Code tham khảo: https://www.ideone.com/5UEr9d
#### sub 3 (thao khảo không có trong thi) (n <= 1e18)
Chúng ta vẫn sẽ sử dụng lại công thức ở sub 2 nhưng sẽ kết hợp xử lí bignum
Trên mạng hiện nay có rất nhiều phương pháp xử lí bignum các bạn có thể tự tham khảo <3
code tham khảo: https://www.ideone.com/okUp1K
## Bài 3:
### Tóm tắt
cho xâu s
nén xâu được định nghĩa là: với các kí tự liên tiếp giống nhau sẽ gộp thành 1 (ví dụ aaaaba -> 4aba)
*Yêu cầu*: Xuất ra màn hình xâu đã nén
### Ý tưởng:
Do bài này mình đọc lộn đề nên mình tưởng aaaaba sẽ thành 5ab =)) nên dùng hash table sai
Có thể do test yếu nên mình trâu cũng được AC cả sub bonus nhưng đề chính chỉ có 256 nên có thể dư sức AC
Chúng ta sẽ duyệt xâu s
Nêu kí tự tại x == tại x + 1 thì ta sẽ duyệt đến khi nào kí tự x != x' + 1 và sau đó nhảy đến vị trí x'
Nếu 2 kí tự liên tiếp khác nhau thì sẽ in ra bình thường
```cpp
for (int i = 0; i < s.size(); i++) {
if (s[i] == s[i + 1]) {
int j = i + 1;
int cnt = 1;
while (s[j] == s[i]) {
cnt++;
j++;
}
cout << cnt << s[i];
i = j - 1;
}
else
cout << s[i];
}
```
Code tham khảo: https://www.ideone.com/5HZryr
## Bài 4:
### Tóm tắt
Cho 2 số n, m
Tìm chữ số cuối cùng của phép tính n^m
### Ý tưởng:
Bài này có 2 sub và 1 sub bonus nhưng mình thấy nếu tính được công thức thi có thể dễ dàng đấm được hết
*Mình học lỏm được cách thức khá hay các bạn có thể tham khảo:* https://www.youtube.com/watch?v=cQm__9qnXIw&list=LL&index=1&t=5s
Về cơ bản thì ta sẽ đi tìm:
* chữ số cuối cùng của n
* tính ```k = m % 4``` (nếu m % 4 = 0 thì lấy **4**)
* sau đó tính ```(n^k) mod 10``` là ra đáp án
Sẵn thì mình chia sẻ cho các bạn hàm pow mình sử dụng trong bài này:
```cpp
const int MOD = 1e9 + 7;
int muti(int a, int b) { return (1LL * a * b) % MOD; }
int Pow(int x, int y) {
int res = 1;
for (; y; y >>= 1)
{
if (y & 1)
res = muti(res, x);
x = muti(x, x);
}
return res;
}
```
Code tham khảo: https://www.ideone.com/WXXEM4
## Bài 5
### Tóm tắt:
Cho số nguyên dương n
Dãy a là là dãy gồm các số tự nhiên từ 1 -> n
Nén một dãy được định nghĩa là ta sẽ lấy phần tử thứ i + (i + 1) ... và mỗi lần như vậy mảng sẽ giảm đi một nửa, hỏi khi dãy chỉ còn 1 phần tử thì giá trị của phần tử đó là bao nhiêu.
VD: N = 4
Dãy ban đầu: 1 2 3 4
Nén lần 1: 3 5 7
Nén lần 2: 8 12
Nén lần 3: 20
*Yêu cầu*: Cho số n, tìm phần tử đã nén cuối cùng
### ý tưởng
#### sub trong đề (n <= 400)
ta sẽ kết hợp xử lí số lớn và duyệt trâu
*Ở đây mình sử dụng xử lí số lớn bằng xâu vì nó đơn giản các bạn có thể tham khảo tại đây:* https://oj.vnoi.info/post/232-obitidev
Ta cần 1 hàm để chuyển số thành xâu:
```cpp
string convert(int n) {
string res = "";
while (n > 0) {
char k = (n % 10) + '0';
res = k + res;
n /= 10;
}
return res;
}
```
Chúng ta sẽ sử dụng vector để dễ dàng quản lí chiều dài cũng như dễ xóa
```cpp
int res = 0;
vector<string> tmp;
for (int i = 1; i <= n; i++)
tmp.push_back(convert(i));
```
Ta cần convert i thành xâu vì cách xử lí số lớn này hoạt động trên xâu.
```cpp
while (tmp.size() != 1)
{
vector<string> tmp2;
for (int j = 0; j < tmp.size() - 1; j++)
tmp2.push_back(csl(tmp[j], tmp[j + 1]));
tmp = tmp2;
}
cout << chsl(tmp[0], "1000000000", "mod");
```
Như vậy khi vector tmp có số lượng phần tử còn khác một thì ta sẽ nén nó lại cho tới khi thỏa mãn.
Vì kết quả cần mod nên ta cần mod số lớn.
Code tham khảo: https://www.ideone.com/iHgD4z
#### sub bonus (n <= 1e18)
chúng ta sẽ sử dụng nghịch đảo modulo để làm bài này:
```cpp
int modulo(int a, int n) {
if (n == 0)
return 1;
int s = modulo(a, n / 2);
s = (s * s) % MOD;
if (n % 2 == 0)
return s;
else
return s * (a % MOD) % MOD;
}
int main() {
...
int s = modulo(2, n - 2);
cout << (((n + 1) % MOD) * (s % MOD)) % MOD;
}
```
Code tham khảo: https://www.ideone.com/TQvwey
Sign in with Wallet
Connect another wallet