# Chuyên Hà Tĩnh 2024
link nộp bài (nhấn vào tham gia tổ chức để nộp được bài): https://oj.vnoi.info/contest/btn_ts10_hatinh_2024
## Bài 1: PAY
### Tóm tắt:
Giá điện tiêu thụ được chia thành 4 bậc:
* Bậc 1: Với 50kWh đầu tiên, giá tiền x1 đồng
* Bậc 2: 51kWh - 100kWh, x2 đồng
* Bậc 3: 101kWh - 200kWh, x3 đồng
* Bậc 4: > 201 kWh, x4 đồng
*Yêu cầu*: Nhập vào 4 số x1, x2, x3, x4 và số y cho biết lượng điện tiêu thụ, hỏi số tiền phải trả
### Ý tưởng:
Với mỗi 1 bậc ta sẽ tính riêng ra và cộng vào kết quả
tổng quát:
```
if (bậc đang xé) {
res = (bậc trước nó * x[phía trước]) + (n - (giới hạn của bậc đang xét));
}
```
vd với x = 300
```cpp
if (n > 200) {
res = 50 * x[1] + 50 * x[2] + 100 * x[3] + (n - 200) * x[4];
}
```
Ta có giới hạn của bậc 1 là 50 nên ta:
* 50 * x[1]
Ta có giới hạn của bậc 2 là 50 nên ta:
* 50 * x[2]
Ta có giới hạn của bậc 3 là 100 nên ta:
* 100 * x[3]
Và phần còn lại là (n - 200) * x[4]
~~Nhớ để long long nhe mấy homie:)~~
Code tham khảo: https://www.ideone.com/BlzHjq
## Bài 2: COUNT
### Tóm tắt:
cho mảng a gồn n phần tử.
tìm số lượng ước dương lớn nhất của một phần tử trong mảng
### Ý tưởng:
#### sub 1:
Duyệt trâu tất cả trường hợp, độ phức tạp $O(n * max(ai))$
với max(ai) là giá trị ai lớn nhất ~ $O(n^2)$
```cpp
int res = 0;
for(int i = 1; i <= n; i++) {
int cnt = 0;
for(int j = 1; j <= a[i]; j++)
if (a[i] % j == 0)
cnt++;
res = max(res, cnt);
}
```
Code tham khảo: https://www.ideone.com/XymRcX
#### sub 2:
Cải tiến từ sub1
> Ta có nhận xét như sau: Giả sử viết n dưới dạng n = i * j với i <= j, thì max(i) = $\sqrt(n)$. Khi đó, giá trị j chắc chắn bằng $n/i$, nên i và j đều là ước của n. nên chỉ cần duyệt đến $\sqrt(n)$.
Code tham khảo:
```cpp
int res = 0;
for(int i = 1; i <= n; i++) {
int cnt = 0;
for(int j = 1; j * j <= a[i]; j++)
if (a[i] % j == 0) {
cnt++;
int t = a[i] / j;
if (t != j)
cnt++;
}
res = max(res, cnt);
}
```
Code tham khảo: https://www.ideone.com/fclJDu
#### sub 3:
Nếu bạn có xem qua sàng số nguyên tố thì có thể áp dụng vô bài này
Chuẩn bị sẵn một mảng ước với divs[i] là số lượng ước tại i
```cpp
const int N = 1e6;
for(int i = 1; i * i <= N; i++)
for(int j = i; j <= N; j+=i)
divs[j]++;
```
Vậy ta chỉ cần $O(1)$ để lấy ước ra
Code tham khảo: https://www.ideone.com/WBHBt4
## Bài 3: ESUM
### Tóm tắt:
Cho mảng a gồm n số nguyên.
Hỏi có bao nhiêu cặp (i, j) i != j mà khi ta bỏ chúng ta thì tổng của các phần tử còn lại của mảng là số chẵn
### Ý tường:
#### sub 1:
Duyệt trâu hết tất cả cách chọn cặp (i, j), độ phức tạp $O(n^2)$
```cpp
int sum = 0;
for(int i = 1; i <= n; i++)
sum += a[i];
int res = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
if (i != j) {
int tmp = a[i] + a[j];
if ((sum - tmp) % 2 == 0)
res++;
}
cout << res;
```
Code tham khảo: https://www.ideone.com/7ghiKz
#### sub 2:
> Ta có nhận xét:
> Trường hợp 1: Sum là số lẻ: ta chỉ cần loại bỏ các cặp (chẵn, lẻ)
> **Công thức là**: $m * n$
> Trưởng hợp 2: Sum là số chắn: ta phải loại bỏ các cặp (chẵn, chẵn) và (lẻ, lẻ)
> **Công thức là**: $^nC_2 + ^mC_2$
> trong đó: n: số lượng chẵn
> ㅤㅤㅤㅤ m: số lượng lẻ
Để tính tổ hợp chập 2 của một số ta có thể tính nhanh bằng công thức:
$\frac{x * (x - 1)}{2
Và kết quả tùy thuộc vào sum là chẵn hay lẻ.
Code tham khảo: https://www.ideone.com/cxhZcN
## Bài 4: EMISTA
### Tóm tắt:
Cho số nguyên n số nguyên và số nguyên k
n dòng tiếp theo cho 2 số nguyên x, y
với x là vị trí trên trục x và y là số lượng tại vị trí x
vậy với bán kính là k thì sẽ đặt tại vị trí nào để tổng các y mà x nằm trong bán kính k là lớn nhất
VD:
4 3
2 8
7 2
10 6
1 4
Với ví dụ này khi ta đặt tại x = 4 thì sẽ phủ sóng tới x1, x2, x7 nơi có số lượng là 4 + 8 + 2 = 14
Vậy đáp án là 14.
### Ý tưởng:
#### sub 1:
Đầu tiên ta sẽ sort lại vị trí x theo thứ tự tăng dần
```cpp
sort(a + 1, a + n + 1);
```
Ta sẽ duyệt trâu 1000 vị trí đặt trạm và mỗi lần đặt ta sẽ kiểm trong bán kính k.
*Với sub1 ta sẽ lưu x và y dưới dạng ```a[x] = y``` do x <= $10^3$ nên có thể lưu dưới dạng mảng
```cpp
int res = 0;
for (int i = k + 1; i <= 1000; i++) {
int tmp = 0;
for (int j = i - k; j <= i + k; j++)
tmp += a[j];
res = max(res, tmp);
}
```
Code tham khảo: https://www.ideone.com/PmvSsF
#### sub 2:
Ta cũng sẽ sort lại mảng theo x
Sử dụng 2 con trỏ để tìm vị trí bên phải cuối cùng mà khoảng cách giữa vị trí trái cùng và vị trí phải cùng <= 2 * k + 1 và có tổng là lớn nhất
```cpp
int res = 0;
int r = 2;
int tmp = 0;
for (int i = 1; i <= n; i++) {
if (!tmp)
tmp += a[i].se;
if (r <= i)
r = i + 1;
while (r <= n && a[r].fi <= (a[i].fi + 2 * k)) {
tmp += a[r].se;
r++;
}
res = max(res, tmp);
tmp -= a[i].se;
}
cout << res;
```
Ta sẽ không cần reset lại biến r (trừ trường hợp r <= i) và tmp do mỗi lần tiến lên i ta sẽ bỏ phần phía trước (nếu khi đã bỏ ở lần trước mà tmp = 0 thì sẽ cộng số lượng tại a[i]) và dồn r lên để tính tiếp.
Code tham khảo: https://www.ideone.com/X4nDJS
#### sub 3:
sub 3 chính là một bài trong Olympic 30/4 2015 lớp 10 [MOBI]
Ta sẽ sử dụng cửa sổ trượt để giải quyết subtask này
```cpp
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
a[x] = y;
len = max(len, x);
}
```
sub này có x <= $10^6$ nên có thể lưu trực tiếp trên mảng
```cpp
int window = 0;
for (int i = 0; i < k * 2 + 1; i++)
window += a[i];
int res = window;
for (int i = k + 1; i <= len - k; i++) {
window -= a[i - k - 1];
window += a[i + k];
res = max(res, window);
}
}
```
mỗi lần ta sẽ trượt trên đoạn (2 * k + 1), bỏ phần đầu và cộng vào phần mới thêm.
Code tham khảo: https://www.ideone.com/i6Sm2I
Sign in with Wallet
Connect another wallet