# 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


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

Входные данные
Первая строка содержит натуральное число $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

 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)

[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

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

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$