---
# System prepended metadata

title: Tutorial of SoTL gen 6 programming team Entrance test

---

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
![](https://i.ibb.co/QNsDG3p/sol3.png)

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$.

![](https://i.ibb.co/bPX6F6f/926px-Venn-s-four-ellipse-construction-svg.png)

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.
![](https://hackmd.io/_uploads/BkkOGcFC3.png)

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:
![](https://hackmd.io/_uploads/SJLX7cYR3.png)

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 😂
![](https://hackmd.io/_uploads/rJs7kGfRh.png)
:::

:::spoiler Cái quan trọng nhất là làm sao để tìm được X thì bạn không viết 😅
![](https://hackmd.io/_uploads/H1QqUpZAh.png)
:::

:::spoiler 🙏🙏🙏
![](https://hackmd.io/_uploads/ByyERWG03.png)
:::

:::spoiler If-else đến chết...
![](https://hackmd.io/_uploads/HJWyd84A2.png)
:::

:::spoiler Chúc mừng bạn đã được full điểm sau 7749 lần submit 🥹
![](https://hackmd.io/_uploads/S1AdPuo03.png)
:::
