Simulare OJI 2016 cls a 8-a | arma

În anul $2214$ a izbucnit primul război interstelar. Pământul a fost atacat de către $n$ civilizații extraterestre, pe care le vom numerota pentru simplicitate de la $1$ la $n$.

Pentru a se apăra, pământenii au inventat o armă specială ce poate fi încărcată cu proiectile de diferite greutăți, fabricate dintr-un material special denumit narun. Dacă arma este programată la nivelul $p$, atunci un proiectil de greutate $k$ va ajunge exact la distanța $k^p$ km ($k$ la puterea $p$) față de Pământ și dacă în acel punct se află cartierul general al unui atacator, acesta va fi distrus. De exemplu, dacă arma este programată la nivelul $2$, un proiectil de greutate 10 va distruge cartierul general al extratereștrilor situat la distanța $10^2 = 100$ km de Pământ.
Arma poate fi încărcată cu proiectile de diferite greutăți, dar cum narunul este un material foarte rar și foarte scump, pământenii vor să folosească proiectile cât mai ușoare pentru a distruge cartierele generale inamice.

Cerință

Cunoscându-se $n$, numărul atacatorilor, precum și cele $n$ distanțe până la cartierele generale ale acestora, să se scrie un program care determină:

1. Cantitatea minimă de narun necesară pentru a distruge toate cartierele generale inamice;
2. Nivelurile la care trebuie programată arma, pentru a distruge fiecare cartier general inamic cu o cantitate minimă de narun.

Date de intrare

Fișierul de intrare arma.in conține pe prima linie un număr natural $c$ reprezentând cerința care trebuie să fie rezolvată ($1$ sau $2$). Pe cea de a doua linie se află numărul natural $n$, reprezentând numărul atacatorilor. Pe următoarele $n$ linii se află $n$ numere naturale, câte un număr pe o linie; pe cea de a $i$-a linie dintre cele $n$ se află distanța față de Pământ a cartierului general al celei de a $i$-a civilizații extraterestre

Date de ieșire

Dacă cerința $c = 1$, atunci pe prima linie a fișierului arma.out va fi scris un număr natural reprezentând cantitatea minimă de narun necesară distrugerii tuturor cartierelor generale inamice.

Dacă cerința este $c = 2$, atunci fișierul de ieșire arma.out va conține $n$ linii. Pe a $i$-a linie se va scrie nivelul la care trebuie programată arma pentru a distruge cartierul general al celei de a $i$-a civilizații extraterestre.

Restricții și precizări

• $1 \leq n \leq 10 \ 000$;
• Distanțele până la cartierele generale inamice sunt numere naturale nenule $\leq 2 \cdot 10^9$;
• Pentru $50$% dintre teste cerința este $1$.

Exemplul 1

arma.in

1
5
100
97
625
40353607
81

arma.out

122

Exemplul 2

arma.in

2
5
100
97
625
40353607
81

arma.out

2
1
4
9
4

Explicație

Primul cartier general se poate distruge cu un proiectil de greutate $10$, programat la nivelul $2$, al doilea obiectiv cu un proiectil de greutate $97$ programat la nivelul $1$, al treilea cu un proiectil de greutate $5$ programat la nivelul $4$, al patrulea cu un proiectil de greutate $7$ programat la nivelul $9$, iar ultimul cu un proiectil de greutate $3$ programat la nivelul $4$. Cantitatea minimă de narun necesară este $10 + 97 + 5 + 7 + 3 = 122$.

Nivelurile sunt în ordine: $2 \ 1 \ 4 \ 9 \ 4$