Igualtats i desigualtats P35144


Statement
 

pdf   zip

thehtml

Tenim un conjunt de variables que prenen valors naturals. Ens van arribant restriccions de la forma x = y, x = a i x ≠ a, on x i y són variables i a és un nombre natural. Hi ha solució per al sistema format per totes les restriccions? I si no n’hi ha, a partir de quin moment és irresoluble?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, el nombre de restriccions del sistema. A continuació vénen les n restriccions. Els noms de les variables són paraules amb lletres minúscules i dígits que comencen amb una lletra. Podeu assumir 1 ≤ n ≤ 105 i 0 ≤ a ≤ 109.

Sortida

Per a cada cas, si el sistema format per totes les restriccions té alguna solució, escriviu “yes”. Altrament, indiqueu després de quantes restriccions el sistema ja no té solució.

Public test cases

  • Input

    3
x == 0
x == 0
x != 1

2
x == 0
x == 1

3
x == 1
x != 1
x == 2

2
x != 0
x != 1

2
x != 0
x == 0

3
hola == adeu
hola == 0
adeu != 0

3
hola42hola == 0
adeu23adeu == 1
hola42hola == adeu23adeu

6
a != 100
a != 200
b != 100
b == 200
b == a
b == 300

3
x == x
x == y
y == x

    Output

    yes
no from 2
no from 2
yes
no from 2
no from 3
no from 3
no from 5
yes
    • Information
    Author
    Enric Rodriguez
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++