Simulare OJI 2016 cls a 8-a | arma

This was the problem page during the contest. Access the current page here.
Time limit: 0.6s Memory limit: 8MB Input: arma.in Output: arma.out

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

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 pp, atunci un proiectil de greutate kk va ajunge exact la distanța kpk^p km (kk la puterea pp) 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 22, un proiectil de greutate 10 va distruge cartierul general al extratereștrilor situat la distanța 102=10010^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 nn, numărul atacatorilor, precum și cele nn 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 cc reprezentând cerința care trebuie să fie rezolvată (11 sau 22). Pe cea de a doua linie se află numărul natural nn, reprezentând numărul atacatorilor. Pe următoarele nn linii se află nn numere naturale, câte un număr pe o linie; pe cea de a ii-a linie dintre cele nn se află distanța față de Pământ a cartierului general al celei de a ii-a civilizații extraterestre

Date de ieșire

Dacă cerința c=1c = 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=2c = 2, atunci fișierul de ieșire arma.out va conține nn linii. Pe a ii-a linie se va scrie nivelul la care trebuie programată arma pentru a distruge cartierul general al celei de a ii-a civilizații extraterestre.

Restricții și precizări

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

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 1010, programat la nivelul 22, al doilea obiectiv cu un proiectil de greutate 9797 programat la nivelul 11, al treilea cu un proiectil de greutate 55 programat la nivelul 44, al patrulea cu un proiectil de greutate 77 programat la nivelul 99, iar ultimul cu un proiectil de greutate 33 programat la nivelul 44. Cantitatea minimă de narun necesară este 10+97+5+7+3=12210 + 97 + 5 + 7 + 3 = 122.

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

Log in or sign up to be able to send submissions!