Subconjunts amb productes iguals P87148


Statement
 

pdf   zip

html

Us donen n fraccions diferents a1/b1, …, an/bn, amb 1 ≤ ai, bi ≤ n. Heu de trobar dos subconjunts I, J ⊆ {1, …, n}, diferents i sense elements comuns, tals que

 
∏
i ∈ I
 
ai
bi
   =  
 
∏
j ∈ J
 
aj
bj
 .

Per exemple, si les fraccions donades són 2/1, 5/3, 1/2, 1/4, 2/4 and 3/6, una solució possible és 3/6 · 1/2 = 1/4.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 105, seguida de les n fraccions.

Sortida

Per a cada cas, si hi ha solució, escriviu-ne qualsevol en dues línies, una per a cada banda de la igualtat, amb el nombre de termes seguit d’aquests termes en qualsevol ordre. Seguiu estrictament el format de l’exemple de sortida. Si no hi ha solució, escriviu una sola línia amb la paraula NO.

Public test cases

  • Input

    6 2/1 5/3 1/2 1/4 2/4 3/6
3 1/2 3/2 3/1
1 1/1
4 1/4 2/3 4/1 4/2

    Output

    2 1/2 2/1
0
1 3/2
2 3/1 1/2
1 1/1
0
0
2 4/1 1/4
    • Information
    Author
    Félix Moreno
    Language
    Catalan
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++