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$}.

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 {$1$}, {$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.