Fişierul intrare/ieşire:aliens.in, aliens.outSursăpreONI 2008 Runda 1
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie10240 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aliens

Extraterestrii sunt printre noi.

Gica fost rapit de extraterestri. Pe nava mama, el afla cate ceva despre noua civilizatie. Astfel descopera ca matematica pe care o cunosc acesti extraterestri este oarecum limitata. Studiind manualele acestora constata ca ei au descoperit doar numerele care se scriu ca produs de 2, 3 sau 5. In plus, extraterestrii cunosc numarul 1. De exemplu, extraterestrii cunosc numerele 45 sau 60, dar nu cunosc numerele 11 sau 42.
Intr-o zi, dupa o lunga convietuire armonioasa, extraterestrii se hotarasc sa il elibereze pe Gica, daca si numai daca acesta da dovada de o inteligenta deosebita. In acest scop, i se ofera N fractii de forma xi / yi (evident, toate numerele xi si yi sunt numere cunoscute de catre extraterestri) si i se cere sa aleaga anumite fractii din cele N astfel incat produsul fractiilor sa fie maxim posibil, si, in plus, acest produs sa fie numar natural.
Primind N fractii cu numaratorul si numitorul numere cunoscute de extraterestri, sa se determine fractiile care trebuiesc selectate astfel incat produsul lor sa fie numar natural si sa fie maxim posibil.

Date de intrare

Fisierul de intrare se numeste aliens.in. Prima linie a acestui fisier contine numarul N. Fiecare din urmatoarele N linii contine cate o pereche de numere cunoscute de extraterestri, identificand cate o fractie.

Date de iesire

Prima si singura linie a fisierului de iesire aliens.out contine numarul natural P, produsul maxim care se poate obtine prin inmultirea unor fractii din cele date.

Restrictii

  • 1 ≤ N ≤ 50
  • Fiecare numar din cele date nu depaseste 400 000 000
  • Fiecare fractie poate fi selectata cel mult o data
  • Se garanteaza ca exista cel putin o solutie

Exemplu

aliens.inaliens.out
6
4 15
16 25
30000 729
5 4
10 30
75 2
30

Explicatie

Se selecteaza fractiile 16/25, 5/4 si 75/2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content