Hi vọng bạn đã có những giờ phút vui vẻ làm 5 bài này!
Hãy thoải mái đưa ra nhận xét của bạn trong phần bình luận nhé 😊
:::spoiler [Đề bài](https://hackmd.io/@brownfox2k6/BJDwX4Qp3#A)
:::
:::spoiler [Link nộp bài](https://codeforces.com/contestInvitation/cc4a71548ef5c58cd5b3761f49ed7ddc38f13b6d)
:::
:::spoiler Final standings
:::success
[Final standings on Codeforces](https://codeforces.com/spectator/ranklist/0b207ba0542b7b3ab81f4bab76ed35df)
- Penalty: số lần submit không được 100 điểm trước khi được 100 điểm.
- Ô trống: không xét
| # | Codeforces handle | Họ và tên | Lớp | = | Pen. |
|:---:|:----------------------------------------------------------------------- |:----------------------- |:-----:|:----------:|:----:|
| 1 | [tuthanhzvn](https://codeforces.com/profile/tuthanhzvn) | Nguyễn Phạm Tú Thanh | 11A3 | **500** | 10 |
| 2 | [KhanhNguyen07](https://codeforces.com/profile/KhanhNguyen07) | Nguyễn Đức Nam Khánh | 11A4 | **500** | 29 |
| 3 | [vuhuyhoang08052008](https://codeforces.com/profile/vuhuyhoang08052008) | Vũ Huy Hoàng | 10QT2 | **500** | 34 |
| 4 | [Gracelyn](https://codeforces.com/profile/Gracelyn) | Nguyễn Nhật My | 10A1 | **475** | - |
| 5 | [EnXi](https://codeforces.com/profile/EnXi) | Cao Quang Khả | 10QT2 | **430** | - |
| 6 | [TruongGiaHuy](https://codeforces.com/profile/TruongGiaHuy) | Trương Gia Huy | 11A2 | **404.5** | - |
| 7 | [TuongQuangMinh](https://codeforces.com/profile/TuongQuangMinh) | Tưởng Quang Minh | 11A2 | **403** | - |
| 8 | [quanphuong2709](https://codeforces.com/profile/quanphuong2709) | Phương Chính Quân | 10QT2 | **400** | - |
| 9 | [DuyLees](https://codeforces.com/profile/DuyLees) | Lê Bảo Duy | 10QT1 | **325** | - |
| 10 | [vejf_20807](https://codeforces.com/profile/vejf_20807) | Phùng Nguyễn Thuỳ Quỳnh | 11A3 | **280** | - |
| 11 | [at14318](https://codeforces.com/profile/at14318) | Trần Anh Đức | 11A3 | **262** | - |
| 12 | [luxiesun](https://codeforces.com/profile/luxiesun) | Bùi Anh Kiệt | 10A5 | **107.25** | - |
| 13 | [AnhDuyNguyen](https://codeforces.com/profile/AnhDuyNguyen) | Nguyễn Anh Duy | 11A2 | **100** | 0 |
| 13 | [binhnguyen2007bk](https://codeforces.com/profile/binhnguyen2007bk) | Nguyễn Tiên Bình | 11A3 | **100** | 0 |
| 13 | [trungpham230708](https://codeforces.com/profile/trungpham230708) | Phạm Hoàng Trung | 10A1 | **100** | 0 |
| 16 | [gumballs](https://codeforces.com/profile/gumballs) | Nguyễn Tùng Lâm | 10A6 | - | - |
| 16 | [lightws](https://codeforces.com/profile/lightws) | Nguyễn Duy Anh | 10A1 | - | - |
| 16 | [mkhoa229](https://codeforces.com/profile/mkhoa229) | Mai Anh Khoa | 10A2 | - | - |
| 16 | [ax0l](https://codeforces.com/profile/ax0l) | Trần Khánh Thiện | 10A2 | - | - |
| 16 | [Rimixscari](https://codeforces.com/profile/Rimixscari) | Đỗ Thành Đạt | 10A4 | - | - |
| 16 | [Vuminh2008](https://codeforces.com/profile/Vuminh2008) | Vũ Tuấn Minh | 10A1 | - | - |
| 16 | [yenchi](https://codeforces.com/profile/yenchi) | Trần Yến Chi | 10D4 | - | - |
| 16 | [Hthinh2105](https://codeforces.com/profile/Hthinh2105) | Nguyễn Hưng Thịnh | 10A5 | - | - |
:::
:::spoiler First solves
:::success
Người đầu tiên đạt 100 điểm
**A -** [EnXi](https://codeforces.com/profile/EnXi)
**B -** [KhanhNguyen07](https://codeforces.com/profile/KhanhNguyen07)
**C -** [KhanhNguyen07](https://codeforces.com/profile/KhanhNguyen07)
**D -** [tuthanhzvn](https://codeforces.com/profile/tuthanhzvn)
**E -** [Gracelyn](https://codeforces.com/profile/Gracelyn)
:::
# [A - brownfox the First-grader](https://hackmd.io/@brownfox2k6/BJDwX4Qp3#A---brownfox-the-First-grader)
:::spoiler Hướng giải
:::success
Chắc không có gì để bàn cả. Kết quả là $\sum_{i=1}^{n}a_i$
Độ phức tạp: $\mathcal{O}(n)$ (cho việc đọc input).
:::
:::spoiler Code (Python)
```python!
n = int(input())
a = list(map(int, input().split()))
print(sum(a))
```
:::
:::spoiler Code (C++)
```cpp!
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int s = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
s += x;
}
cout << s;
}
```
:::
#### Bình luận bài A
# [B - brownfox and Arrays](https://hackmd.io/@brownfox2k6/BJDwX4Qp3#B---brownfox-and-Arrays)
:::spoiler Hướng giải
:::success
Gọi $maxb$ là phần tử lớn nhất của $b$ $(maxb=\max_{i=1}^{n} b_i)$.
Dễ thấy chỉ cần sắp xếp lại $maxb$ phần tử cuối cùng của $a$ là được. Vì nếu $maxb$ phần tử cuối cùng của $a$ đã được sắp xếp thì $\forall x \le maxb$ phần tử cuối cùng của $a$ cũng đã được sắp xếp.
Độ phức tạp: $\mathcal{O}(n \log n)$ (cho việc sắp xếp).
:::
:::spoiler Code (Python)
```python!
def readLine():
return list(map(int, input().split()))
n, m = readLine()
a = readLine()
b = readLine()
maxb = max(b)
a[n-maxb: ] = sorted(a[n-maxb: ])
for x in a:
print(x % 2017, end=' ')
```
:::
:::spoiler Code (C++)
```cpp!
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[n];
for (int &x : a) {
cin >> x;
}
int b[m];
for (int &x : b) {
cin >> x;
}
int maxb = *max_element(b, b+m);
sort(a+n-maxb, a+n);
for (int x : a) {
cout << x % 2017 << ' ';
}
}
```
:::
#### Bình luận bài B
# [C - brownfox and Geometry](https://hackmd.io/@brownfox2k6/BJDwX4Qp3#C---brownfox-and-Geometry)
:::spoiler Hướng giải
:::success
Dễ thấy cách tối ưu nhất để vẽ tam giác cân $OAB$ là vẽ cạnh $AB$ đi qua điểm xa $O$ nhất.
Khi ấy $OA = OB$ $=\max_{i=1}^{n} (x_i + y_i)$ (xem phần Chứng minh).
Tiếp theo, dùng định lý Pytago để tính $AB$:
$AB=\sqrt{OA^2+OB^2}=\sqrt{2 \cdot OA^2}=OA\sqrt{2}$
Độ phức tạp: $\mathcal{O}(n)$ (cho việc đọc input).
:::
:::spoiler Chứng minh
:::success
Giả sử ta có điểm $N$ với toạ độ $x_N$, $y_N$.
Từ $N$ chiếu $NH$ và $NK$ lên $Ox$ và $Oy$ tương ứng.
Xét $\triangle BKN$ và $\triangle BOA$:
- $\angle B$ chung
- $\angle BKN=\angle BOA(=90^\circ)$
$\implies \triangle BKN\sim\triangle BOA$ (g. g)
Mà $\triangle BOA$ vuông cân tại $O$
$\implies\triangle BKN$ vuông cân tại $K$
$\implies KB=KN=x_N$
$\implies OB=OK+KB=x_N+y_N$
:::
:::spoiler Code (Python)
```python!
rside = 0
n = int(input())
for i in range(n):
x, y = map(int, input().split())
rside = max(rside, x+y)
hypotenuse = rside * 2**0.5
print(rside, rside, hypotenuse)
```
:::
:::spoiler Code (C++)
```cpp!
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int rside = 0;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
rside = max(rside, x+y);
}
double hypotenuse = rside*1.4142;
cout << rside << ' ' << rside << ' ' << hypotenuse;
}
```
:::
#### Bình luận bài C
# [D - brownfox and Algebra](https://hackmd.io/@brownfox2k6/BJDwX4Qp3#D---brownfox-and-Algebra)
:::spoiler Hướng giải
:::success
Dễ thấy:
- Những số chia hết cho $4$, $6$, $8$, $10$ cũng là những số chia hết cho $2$,
- Những số chia hết cho $6$, $9$ cũng là những số chia hết cho $3$,
- Những số chia hết cho $10$ cũng là những số chia hết cho $5$.
Tóm lại, những số chia hết cho **ít nhất một** trong các số nguyên từ $2$ đến $10$ là những số chia hết cho **ít nhất một** trong bốn số $2$, $3$, $5$ và $7$.
Đề bài toán đơn giản hơn, ta gọi $k$ là số lượng số nguyên dương từ $1$ tới $n$ mà chia hết cho **ít nhất một** trong bốn số $2$, $3$, $5$ và $7$.
Gọi $f(x)$ là số lượng số nguyên từ $1$ tới $n$ chia hết cho $x$, dễ thấy $f(x) = \left\lfloor \frac{n}{x} \right\rfloor$.
Bằng việc vẽ sơ đồ Venn hoặc áp dụng [nguyên lý bao hàm - loại trừ](https://vi.wikipedia.org/wiki/Nguy%C3%AAn_l%C3%BD_bao_h%C3%A0m-lo%E1%BA%A1i_tr%E1%BB%AB#C%C3%B4ng_th%E1%BB%A9c), ta có:
$k= \space$ $[f(2)+f(3)+f(5)+f(7)]$
$\space-[f(2\cdot3)+f(2\cdot5)+f(2\cdot7)+f(3\cdot5)+f(3\cdot7)+f(5\cdot7)]$
$\space+[f(2\cdot3\cdot5)+f(2\cdot5\cdot7)+f(3\cdot5\cdot7)]$
$\space- f(2\cdot3\cdot5\cdot7)$
Kết quả của bài toán là $(n-k)\bmod 2017$.
Độ phức tạp thuật toán: $\mathcal{O}(1)$.
:::
:::spoiler Code (Python)
```python!
def divisors(n, x):
return n // x
n = int(input())
print((
n
- divisors(n, 2)
- divisors(n, 3)
- divisors(n, 5)
- divisors(n, 7)
+ divisors(n, 2 * 3)
+ divisors(n, 2 * 5)
+ divisors(n, 2 * 7)
+ divisors(n, 3 * 5)
+ divisors(n, 3 * 7)
+ divisors(n, 5 * 7)
- divisors(n, 2 * 3 * 5)
- divisors(n, 2 * 3 * 7)
- divisors(n, 2 * 5 * 7)
- divisors(n, 3 * 5 * 7)
+ divisors(n, 2 * 3 * 5 * 7)
) % 2017)
```
:::
:::spoiler Code (C++)
```cpp!
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
auto divisors = [&](int x) {
return n / x;
};
long long ans =
n
- divisors(2)
- divisors(3)
- divisors(5)
- divisors(7)
+ divisors(2 * 3)
+ divisors(2 * 5)
+ divisors(2 * 7)
+ divisors(3 * 5)
+ divisors(3 * 7)
+ divisors(5 * 7)
- divisors(2 * 3 * 5)
- divisors(2 * 3 * 7)
- divisors(2 * 5 * 7)
- divisors(3 * 5 * 7)
+ divisors(2 * 3 * 5 * 7);
cout << ans % 2017;
}
```
:::
#### Bình luận bài D
# [E - brownfox and Sum of Product of Pairs](https://hackmd.io/@brownfox2k6/BJDwX4Qp3#E---brownfox-and-Sum-of-Product-of-Pairs)
Bài này có khá nhiều cách làm hay, ở đây mình sẽ viết 2 cách.
## Cách 1
:::spoiler Hướng giải
:::success
*Giả sử chỉ số mảng $a$ bắt đầu từ $1$, còn chỉ số mảng $b$ bắt đầu từ $0$.*
Gọi $S$ là giá trị tổng cần tìm.
Giả sử mảng $a$ có $6$ phần tử, ta có $S$ bằng tổng $a_i\cdot a_j$ trên những ô $(i, j)$ được đánh dấu.
Tạo mảng $b$ có $n+1$ phần tử ($b_0$..$b_n$) với ý nghĩa: $b_i$ là tổng của $i$ phần tử đầu tiên của $a$.
Ta có:
- $b_0 = 0$ (tổng của 0 phần tử đầu tiên hiển nhiên là $0$)
- $b_i=b_{i-1}+a_i$, $\forall i \in [1, n]$
Từ đó, dễ thấy tổng của $a_l+a_{l+1}+\ldots+a_r = b_{r} - b_{l-1}$.
Do đó:
$S=a_1\cdot(b_n-b_1)+\space a_2\cdot(b_n-b_2)+\ldots+a_{n-1}\cdot(b_n-b_{n-1})$
Độ phức tạp: $\mathcal{O}(n)$
:::
:::spoiler Code (Python)
```python!
q = int(input())
for _ in range(q):
n = int(input())
a = [-1] + list(map(int, input().split()))
b = [0] * (n+1)
for i in range(1, n+1):
b[i] = b[i-1] + a[i]
s = 0
for i in range(1, n):
s += a[i] * (b[n] - b[i])
print(s)
```
:::
:::spoiler Code (C++)
```c++!
#include <iostream>
using namespace std;
#define N 100005
int q, n, a[N];
long long s, b[N];
int main() {
for (cin >> q; q--; ) {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
b[i] = b[i-1] + a[i];
}
s = 0;
for (int i = 1; i <= n-1; ++i) {
s += a[i] * (b[n]-b[i]);
}
cout << s << '\n';
}
}
```
:::
## Cách 2
:::spoiler Hướng giải
:::success
*Bạn hãy đọc hướng giải của Cách 1 trước khi tiếp tục nhé.*
Giờ ta nhân đôi $S$, tức $2S$ bằng tổng $a_i\cdot a_j$ trên những ô $(i, j)$ được đánh dấu:
Gọi $X$ là tổng của mảng $a$ ($X=\sum_{i=1}^{n}a_i$). Nhìn vào hình trên, dễ thấy:
$2S = a_1\cdot(X-a_1)+a_2\cdot(X-a_2)+\ldots+a_n\cdot(X-a_n)$
$= a1\cdot X+a_2\cdot X +\ldots+a_n\cdot X-a_1^2 -a_2^2 -\ldots-a_n^2$
$= X^2 -a_1^2 -a_2^2 -\ldots-a_n^2$
Gọi $Y$ là tổng bình phương các phần tử của mảng $a$ ($Y=\sum_{i=1}^{n}a_i^2$), ta có:
$2S = X^2 -Y$
$\implies S=\frac{X^2-Y}{2}$
Độ phức tạp: $\mathcal{O}(n)$
:::
:::spoiler Code (Python)
```python!
q = int(input())
for _ in range(q):
n = int(input())
a = list(map(int, input().split()))
x = sum(a)
s = 0
for i in range(n):
s += a[i] * (x-a[i])
print(s // 2)
```
:::
:::spoiler Code (C++)
```c++!
#include <iostream>
#include <numeric>
using namespace std;
int q, n, a[100005];
long long x, s;
int main() {
for (cin >> q; q--; ) {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
x = accumulate(a, a+n, 0ll);
s = 0;
for (int i = 0; i < n; ++i) {
s += a[i] * (x-a[i]);
}
cout << s / 2 << '\n';
}
}
```
:::
## Bonus
:::spoiler Bonus
Bạn có thể tính được tổng $a_i\cdot a_j\cdot a_k$ với mọi bộ ba $(i,j,k)$ thoả mãn $1 \le i<j<k \le n$ không?
Nói cách khác, tính $\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n}(a_i\cdot a_j\cdot a_k)$.
:::
#### Bình luận bài E
---
# Bonus 😊
:::spoiler Thực ra cả tổng dung lượng code cho cả 5 bài chưa đến 400 kí tự, bạn tin được không?
```python
# Total: 395 chars
# A (py3, 42 chars)
print(sum(map(int,[*open(0)][1].split())))
# B (py3, 99 chars)
_,a,b=[[*map(int,x.split())]for x in open(0)];k=-max(b)
for x in a[:k]+sorted(a[k:]):print(x%2017)
# C (py3, 70 chars)
print(a:=max(sum(map(int,s.split()))for s in[*open(0)][1:]),a,a*2**.5)
# D (py2, 95 chars)
n=input();print(n-n/2-n/3-n/5-n/7+n/6+n/10+n/14+n/15+n/21+n/35-n/30-n/42-n/70-n/105+n/210)%2017
# E (py3, 89 chars)
for a in[*open(0)][2::2]:*a,=map(int,a.split());x=sum(a);print(sum(y*(x-y)for y in a)>>1)
```
:::
:::spoiler Khoảng cách giữa nửa số điểm và full điểm là một dấu cách 😂
:::
:::spoiler Cái quan trọng nhất là làm sao để tìm được X thì bạn không viết 😅
:::
:::spoiler 🙏🙏🙏
:::
:::spoiler If-else đến chết...
:::
:::spoiler Chúc mừng bạn đã được full điểm sau 7749 lần submit 🥹
:::
Sign in with Wallet
Connect another wallet