Pentru un număr natural N considerăm toate submulţimile nevide ale mulţimii {1, 2, 3, …, N}.
De exemplu, pentru N=3, submulţimile nevide ale mulţimii {1, 2, 3} sunt: {1} {2} {3} {1,2} {1,3} {2,3} şi {1,2,3}.
Pentru fiecare submulţime se ordonează mai întâi descrescător elementele sale, apoi valoarea maximă primeşte semnul +, valoarea următoare are semnul –, următoarea valoare + ş.a.m.d, apoi se determină suma lor.
De exemplu submulţimea {1, 2, 5, 8, 10} are asociată suma +10-8+5-2+1=6, submulţimea {4,7} are suma +7-4=3, iar submulţimea {3} are suma 3.
Cerinţă
Să se determine valoarea totală a sumelor asociate tuturor submulţimilor mulţimii {1, 2, 3, …, N}.
Date de intrare
Fişierul de intrare subsets.in conţine pe prima linie numărul natural N.
Date de ieşire
Fişierul de ieşire subsets.out conţine o singură linie pe care va fi scris un număr natural reprezentând suma totală a sumelor asociate tuturor submulţimilor mulţimii {1, 2, 3, …, N}.
Restricţii
- 1 <= N <= 30 000
- Pentru 40% din teste, N <= 25
- Pentru alte 40% din teste, 25 < N <= 1000
Exemplu
| subsets.in |
subsets.out |
Explicaţii |
3
|
12
|
Submulţimile nevide ale mulimii {1, 2, 3} sunt:
{1} cu suma asociată 1
{2} cu suma asociată 2
{3} cu suma asociată 3
{1,2} cu suma asociată 2-1=1
{1,3} cu suma asociată 3-1=2
{2,3} cu suma asociată 3–2=1
{1,2,3} cu suma asociată 3-2+1=2
Suma totală obţinută este 1+2+3+1+2+1+2=12 |
|