nmint

Time limit: 0.05s Memory limit: 64MB Input: nmint.in Output: nmint.out

Fie NN un număr natural impar și p1,p2,p3,pNp_1, p_2, p_3, \cdots p_N primele NN numere prime.

Se consideră expresiile:

  • A=p1+p2+p3++pNA = \sqrt{p_1} + \sqrt{p_2} + \sqrt{p_3} + \cdots + \sqrt{p_N}
  • B=±p1±p2±p3±pNB = \pm \sqrt{p_1} \pm \sqrt{p_2} \pm \sqrt{p_3} \cdots \pm \sqrt{p_N}

Cerință

Să se determine o succesiune de NN semne {+,}\{+, -\} pentru radicalii ce formează expresia BB, astfel încât produsul ABA \cdot B, să conțină, după desfacerea parantezelor și reducerea termenilor asemena, un număr minim de termeni. De exemplu, pentru N=3N = 3 numărul minim de termeni ai produsului (2+3+5)(±2±3±5)(\sqrt{2} + \sqrt{3} + \sqrt{5}) \cdot (\pm \sqrt{2} \pm \sqrt{3} \pm \sqrt{5}) va fi 11 și se va obține când a doua expresie este (2+35)(\sqrt{2} + \sqrt{3} - \sqrt{5}), așadar succesiunea de semne este ++-.

Date de intrare

Fișierul de intrare nmint.in conține pe prima linie numărul natural impar NN, cu semnificația de mai sus.

Date de ieșire

Fişierul de ieşire nmint.out va conţine două linii. Pe prima linie se va scrie numărul minim de termeni ai produsului ABA \cdot B, iar pe a doua linie o succesiune de N caractere + și -, reprezentând semnele radicalilor din expresia B, în vederea obținerii unui număr minim de termeni pentru produsul ABA \cdot B.

Restricții și precizări

  • 3N49 9993 \leq N \leq 49 \ 999

Exemplu

nmint.in

5

nmint.out

4
+-++-

Explicație

Numărul minim de termeni ai produsului

(2+3+5+7+11)(±2±3±5±7±11)(\sqrt{2} + \sqrt{3} + \sqrt{5} + \sqrt{7} + \sqrt{11}) \cdot (\pm \sqrt{2} \pm \sqrt{3} \pm \sqrt{5} \pm \sqrt{7} \pm \sqrt{11})

după desfacerea parantezelor și reducerea termenilor asemenea este 44 și o variantă posibilă de succesiune a semnelor termenilor din a doua expresie este +-++-, caz în care a doua expresie devine (+23+5+711)(+ \sqrt{2} - \sqrt{3} + \sqrt{5} + \sqrt{7} - \sqrt{11})

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