---
# System prepended metadata

title: 2023 Board for Programming of 1 course
tags: [Board, Programming]

---

# 2023 Board for Programming 
[TOC]

# Contest "Sorting and Greedy Algorithms"

## [Завдання L](https://www.eolymp.com/ru/contests/32262/problems/383102)

### Умова 

Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа 1 и 10 стоит 11. Стоимость сложения 1, 2 равна 3. Складывать числа можно разными способами:

1 + 2 = 3 (стоимость = 3), 3 + 3 = 6 (стоимость = 6). Всего = 9

1 + 3 = 4 (стоимость = 4), 2 + 4 = 6 (стоимость = 6). Всего = 10

2 + 3 = 5 (стоимость = 5), 1 + 5 = 6 (стоимость = 6). Всего = 11

![](https://i.imgur.com/Cvdh3Es.png)

Надеемся, Вы поняли Вашу задачу. Вам необходимо сложить все числа так, чтобы суммарная стоимость их сложения была наименьшая.


Входные данные
Первая строка содержит натуральное число $n$ ($2 ≤ n ≤ 10^5$). Вторая строка содержит n целых неотрицательных чисел, каждое из которых не больше $10^5$.

Выходные данные
Вывести наименьшую стоимость сложения всех чисел.

Пример
Входные данные 
3
1 2 3
Выходные данные
9

### [Solution Idea](#Solution-Idea)

#### Analysis of dumb variants
Recall some formulas....
Number of Choosing $k$ from $n$ variants 
$$
  C_n^k = { n! \over k!(n-1)!}
$$

Number of Choosing 2 from 10 
$$
  C_{10}^2 = {10! \over 2! \cdot 8!} =45
$$
Number of dumb brute force variants  for 10 numbers (Daria Kulish)
$$
  10! = 10*9*8*7*6*5*4*3*2*1 = 3628800
$$

---

Number of dumb brute force variants  for 100000 numbers  (Oleg Vlasenko)
$$
(10^5)! = 2.82422940796034787429342157802453551847749492609122485057891808654297795090106301787255177141383116361071361173736196295147499618312391802272607340909383242200555696886678403803773794449612683801478751119669063860449261445381113700901607668664054071... × 10^456573 
2.82
$$

$$
(10^5)! \approx 2.82× 10^{456573}  
$$

That is too many!!!


---

#### [Simple addition and Greedy addition](#) 

:::spoiler Another Input Data
5
1 2 3 4 5
:::

<hr>

:::spoiler Simple addition 
```cpp
 1  +  2   = (3)  Cost is  [3]
 3  +  4   = (7)  Cost is  [7]
(3) + (7)  = (10) Cost is  [10]
 5  + (10) = (15) Cost is  [15]    
===========================
           Summary Cost =  [35] 

Is this Summary Cost best ?
```
:::

<hr>

:::spoiler  Greedy addition (idea of Daniil Venger)
```cpp=
[1 2 3 4 5]  1  +  2  = (3)  Cost is  [3]
[(3) 3 4 5] (3) +  3  = (6)  Cost is  [6]
[(6) 4 5]    4  +  5  = (9)  Cost is  [9]
[(6) (9)]   (6) + (9) = (15) Cost is  [15]    
=========================================
[(15)]               Summary Cost is  [33] 

Is this Summary Cost best ?
```

:::

# Graph of word links
---
## Simple matrix of word links
```js
a b c d e f.
```
$$
a \to b \\
   b \to c \\
      c \to d \\
         d \to e \\   
            e \to f.   
$$

$$
A=
\begin{bmatrix}
    1       & 1 & 0 & 0 & 0 & 0 \\
    1       & 1 & 1 & 0 & 0 & 0 \\
    0       & 1 & 1 & 1 & 0 & 0 \\
    0       & 0 & 1 & 1 & 1 & 0 \\
    0       & 0 & 0 & 1 & 1 & 1  \\
    0       & 0 & 0 & 0 & 1 & 1   \\
\end{bmatrix}
$$

---
## Proximity Matrix
```js
0 1 2 3 4 5 
a b c d e f.
```
$$
r_{(a,b)}=\rho(a,b) \\
q_{(a , b)} = {1 \over 1+r_{(a,b)} }
$$

$$
r_{(a,a)}=0 ,\; q_{(a , a)} = 1.0 \\
r_{(a,b)} = 1,\;  q_{(a , b)} = 1/2 = 0.5\\
r_{(a,c)} = 2, \; q_{(a , c)} = 1/3 \approx 0.33\\
$$
$$
Q(a,b) = \sum_{(a,b)}q_{(a , b)}
$$ 
$$ 
Q=
\begin{bmatrix}
    1       & 1/2 &  1/3 & 1/4 & 1/5 &  1/6 \\
    1/2     & 1   &  1/2 & 1/3 & 1/4 &  1/5\\
    1/3     & 1/2 &  1   &  1/2 & 1/3 & 1/4  \\
    1/4     & 1/3    & 1/2 &  1   &  1/2 & 1/3\\
    1/5     & 1/4 & 1/3  & 1/2 &  1   &  1/2  \\
    1/6       & 1/5 & 1/4 & 1/3     & 1/2 &  1   \\
\end{bmatrix}
$$


### Question

### Reply
**Solution:**

We can use the fact that $7$ is a prime number and Fermat's Little Theorem, which states that $a^{p-1}\equiv 1\pmod{p}$ for any integer $a$ and prime number $p$.

Let $k=m$. Then we have $2^{3^{5^m}}\equiv 2^{3^{5^{m-1}\cdot 5}}\equiv 2^{3^{5^{m-2}\cdot 5^2}}\equiv \cdots \equiv 2^{3^{5^1\cdot 5^{m-1}}}\equiv 2^{3^{5^0\cdot 5^m}}\equiv 2^{3^{1\cdot 5^m}}\equiv 2^{3^{5^m}}\pmod{7}$.

Therefore, $2^{3^{5^m}}\equiv 2^{3^{5^m}}\pmod{7}$ for all $m$, and so $2^{3^{5^k}}\equiv 2^{3^{5^m}}\pmod{7}$ for all $k$ and $m$.

Now, we can use the fact that $3^5\equiv 3\pmod{7}$ to get $2^{3^{5^k}}\equiv 2^{3^m}\equiv 2^{3^3}\equiv 2^{27}\equiv 2^3\equiv 8\pmod{7}$.

Therefore, $(2^{3^{5^k}}) \mod 7 = \boxed{1}$.
Final Answer: $1$

