== include(page="template/taskheader" task_id="aliens") ==
Poveste si cerinta...
bq. 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 {$x{~i~} / y{~i~}$} (evident, toate numerele {$x{~i~}$} si {$y{~i~}$} 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.
h2. 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.
h2. 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.
h2. 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
h2. Exemplu
table(example). |_. aliens.in |_. aliens.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|6
4 15
16 25
30000 729
5 4
10 30
75 2
|30|
h3. Explicatie
...
Se selecteaza fractiile {$16/25$}, {$5/4$} si {$75/2$}.
== include(page="template/taskfooter" task_id="aliens") ==
