---
# System prepended metadata

title: Giải đề HSG Tin 11 cấp Cụm HK-HBT 2022-2023

---

# Bài I. Tính tiền điện (6đ)
:::spoiler **Đề bài**
Hiện tại, tiền điện của các hộ dân sống tại Hà Nội đang được tính theo thang như sau: 

1. Bậc 1 (0 đến 50 kWh): $1678$ đồng/kWh. 
2. Bậc 2 (51 đến 100 kWh): $1734$ đồng/kWh. 
3. Bậc 3 (101 đến 200 kWh): $2014$ đồng/kWh. 
4. Bậc 4 (201 đến 300 kWh): $2536$ đồng/kWh. 
5. Bậc 5 (301 đến 400 kWh): $2834$ đồng/kWh. 
6. Bậc 6 (401 kWh trở lên): $2927$ đồng/kWh.

**Yêu cầu:**
Nhập vào số nguyên dương $N$ là số kWh mà gia đình bạn Lan đã sử dụng trong tháng 2 vừa qua. Hãy tính số tiền điện mà gia đình Lan cần phải trả. 

**Dữ liệu vào từ bàn phím:**
Gồm một số duy nhất là số nguyên dương $N$ $(1 \le N \le 10^5)$  

**Kết quả ghi ra màn hình:**
Ghi ra một số duy nhất là số tiền gia đình Lan phải trả tính theo đơn vị đồng.

**Ví dụ:**
| Input | Output   | Giải thích                  |
| ----- | -------- | --------------------------- |
| `30`  | `50340`  | Vì $30*1678=50340$          |
| `89`  | `151526` | Vì $50*1678+39*1734=151526$ |
:::

:::spoiler **Code 1 (Python)**
```python
N = int(input())
if N <= 50:
  print(N*1678)
elif N <= 100:
  print(50*1678 + (N-50)*1734)
elif N <= 200:
  print(50*1678 + 50*1734 + (N-100)*2014)
elif N <= 300:
  print(50*1678 + 50*1734 + 100*2014 + (N-200)*2536)
elif N <= 400:
  print(50*1678 + 50*1734 + 100*2014 + 100*2536 + (N-300)*2834)
else:
  print(50*1678 + 50*1734 + 100*2014 + 100*2536 + 100*2834 + (N-400)*2927)
```
:::

:::spoiler **Code 2 (Python)**
```python
N = int(input())
ans = 0

# Tiền bậc 1
x = min(50, N)
N -= x
ans += 1678 * x
# Tiền bậc 2
x = min(50, N)
N -= x
ans += 1734 * x
# Tiền bậc 3
x = min(100, N)
N -= x
ans += 2014 * x
# Tiền bậc 4
x = min(100, N)
N -= x
ans += 2536 * x
# Tiền bậc 5
x = min(100, x)
N -= x
ans += 2834 * x
# Tiền bậc 6
ans += 2927 * N

print(ans)
```
:::

# Bài II. Số khác nhau (6đ)
:::spoiler **Đề bài**
Nhập vào từ bàn phím số nguyên dương $N$. $N$ dòng tiếp theo mỗi dòng là một số nguyên dương $A_i$. 

**Yêu cầu:**
Đưa ra số lượng số khác nhau trong $N$ số đã nhập. 

**Dữ liệu vào từ bàn phím:**
- Dòng đầu tiên là số nguyên dương $N$ $(1 \le N \le 10^5)$;
- $N$ dòng tiếp theo mỗi dòng là một số nguyên dương $A_i$ $(1 \le A_i \le 10^9)$. 

**Kết quả ghi ra màn hình:**
Ghi ra một số duy nhất là số lượng số khác nhau trong $N$ số đã nhập.

**Ví dụ:**
Input:
```
3
11
2
11
```
Output:
```
2
```
Giải thích:
2 số khác nhau trong dãy đã nhập là 2 và 11.
:::

:::spoiler **Code (Python)**
```python
N = int(input())
s = set()
for i in range(N):
  x = int(input())
  s.add(x)
print(len(s))
```
:::

:::spoiler **Code (C++)**
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  set<int> s;
  for (int i = 0; i < N; ++i) {
    int x;
    cin >> x;
    s.insert(x);
  }
  cout << s.size();
}
```
:::

# Bài III. Thực hiện phép toán (5đ)
:::spoiler **Đề bài**
Nhập vào từ bàn phím một biểu thức chỉ gồm các số nguyên và các phép toán cộng (+) hoặc trừ (-).

**Yêu cầu:**
Đưa ra kết quả của biểu thức.

**Dữ liệu vào từ bàn phím:**
Gồm một dòng duy nhất là biểu thức (độ dài không quá 100 kí tự).

**Kết quả ghi ra màn hình:**
Ghi ra một số duy nhất là kết quả của biểu thức.

**Ví dụ:**
| Input        | Output |
| ------------ | ------ |
| `123+456`    | `579`  |
| `123-56+100` | `167`  |
:::

:::spoiler **Code 1 (Python)**
``` python
s = input()
print(eval(s))
```
:::

:::spoiler **Code 2 (Python)**
```python
s = input()

# Lưu vị trí của dấu
sign = []
for i, c in enumerate(s):
  if c in '-+':
    sign.append(i)

# Lưu các số theo thứ tự
num = [int(s[:sign[0]])]  # Lưu số đầu
for i in range(1, len(sign)):
  l = sign[i-1] + 1
  r = sign[i]
  # số phải nằm giữa hai dấu, tức [l, r)
  num.append(int(s[l:r]))
num.append(int(s[sign[-1]+1:]))  # Lưu số cuối

ans = num[0]
for i in range(len(sign)):
  # sign[i] là dấu đứng trước num[i+1]
  if sign[i] == '+':
    ans += num[i+1]
  else:
    ans -= num[i+1]
print(ans)
```
:::

# Bài IV. Dãy con (3đ)
:::spoiler **Đề bài**
Cho dãy số $A$ có $N$ phần tử và một số nguyên $K$.

**Yêu cầu**:
Tìm độ dài của đoạn con liên tiếp $[l, r]$ dài nhất mà tổng các phần tử $A[l]+A[l+1]+\ldots+A[r]$ chia hết cho $K$.

**Dữ liệu vào từ bàn phím:**
- Dòng đầu tiên là 2 số nguyên dương $N$ và $K$ $(1\le N\le10^5, 1\le K\le10^8)$;
- Dòng tiếp theo gồm $N$ số nguyên dương của dãy số $A$ $(1\le A_i \le 10^8)$.

**Kết quả ghi ra màn hình:**
Ghi ra một số duy nhất là độ dài lớn nhất của dãy con liên tiếp thỏa mãn yêu cầu.

**Ví dụ:**
Input:
```
5 3
1
2
3
4
5
```

Output:
```
5
```

Giải thích:
Có nhiều đoạn con có tổng chia hết cho 3: 

- Đoạn từ $3$ đến $3$ có độ dài là $1$, tổng là $3$ 
- Đoạn từ $1$ đến $2$ có độ dài là $2$, tổng là $3$ 
- Đoạn từ $4$ đến $5$ có độ dài là $2$, tổng là $9$ 
- Đoạn từ $1$ đến $3$ có độ dài là $3$, tổng là $6$ 
- Đoạn từ $2$ đến $4$ có độ dài là $3$, tổng là $9$ 
- Đoạn từ $3$ đến $5$ có độ dài là $3$, tổng là $12$ 
- Đoạn từ $1$ đến $5$ có độ dài là $5$, tổng là $15$ 

Trong các đoạn đó thì đoạn con từ $1$ đến $5$ là đoạn có tổng chia hết cho $3$ dài nhất nên đưa ra kết quả là $5$.

**Giới hạn:**
- 60% số điểm tương ứng 60% số test có $N \le 100$; 
- 20% số điểm tiếp theo tương ứng 20% số test có $100 < N \le 1000$; 
- 20% số điểm còn lại không có $1000 < N \le 10^5$.
:::

:::spoiler **Cách làm**
### Subtask 1 và 2 $(N \le 1000)$
Đơn giản là duyệt từng đoạn con, nếu tổng của đoạn con ấy chia hết cho $K$ thì cập nhật đáp án (xem code để hiểu hơn).
### Subtask 3 $(N \le 10^5)$
Sử dụng prefix sum, với $p_i$ là tổng của $i$ phần tử đầu tiên của $a$. Khi đó, $a_l+\ldots+a_r=p_r-p_{l-1}$. Nếu $p_r-p_{l-1}$ chia hết cho $K$ thì dãy con từ $l$ đến $r$ có tổng chia hết cho $K$. Sử dụng tính chất modulo: $(x+y)\bmod k = (x \bmod k + y\bmod k) \bmod k$, ta có thể đặt $p_i = p_i \bmod k$. Khi đó, dãy con thoả mãn có $p_r-p_{l-1}=0$. Đề bài hỏi dãy con dài nhất nên ta sẽ lưu vị trí xuất hiện đầu tiên và cuối cùng của từng phần tử trong prefix sum $p$.
:::

:::spoiler **Code sub 1, 2 (Python)**
``` python
n, k = map(int, input().split())
ans = 0
for l in range(n):
  s = 0
  for r in range(l, n):
    s += a[r]
  if s % k == 0:
    ans = max(ans, r-l+1)
print(ans)
```
:::

:::spoiler **Code (C++)**
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;

  int s = 0;
  map<int, pair<int, int>> mp;  // lưu vị trí xuất hiện sớm nhất và muộn nhất
  mp[0] = {0, -1};
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    s = (s + x) % k;
    if (mp.count(s)) {
      mp[s].second = i;
    } else {
      mp[s] = {i, -1};
    }
  }

  int ans = 0;
  for (auto p : mp) {
    int l = p.second.first;
    int r = p.second.second;
    if (r == -1) {
      continue;
    }
    ans = max(ans, r-l+1);
  }
  cout << ans;
}
```

:::

:::spoiler **Code (Python)**
```python
n, k = map(int, input().split())
s = 0
d = {0: [0, -1]}
for i in range(1, n+1):
  s = (s + int(input())) % k
  if s in d:
    d[s][1] = i
  else:
    d[s] = [i, -1]

ans = 0
for l, r in d.values():
  if r == -1:
    continue
  ans = max(ans, r-l+1)
print(ans)
```
:::