Moviments en el pla P77684


Statement
 

pdf   zip

thehtml

Teniu n vectors bidimensionals (xi, yi) i una posició objectiu (x, y). Inicialment, us trobeu a (0, 0). En ordre, heu de decidir com usar cada vector: podeu descartar-lo, sumar xi a la vostra x actual, sumar yi a la vostra y actual, o fer les dues coses. Heu d’anar fins a (x, y) almenys un cop, i acabar a (0, 0). De quantes maneres podeu fer-ho?

Entrada

L’entrada consisteix en diversos casos, cadascun amb x, y i n, seguides dels n vectors (xi, yi). Suposeu 2 ≤ n ≤ 12, i que x, y, xi i yi són enters entre −106 i 106 diferents de 0.

Sortida

Per a cada cas, escriviu el nombre de maneres d’anar fins a (x, y) almenys una vegada i tornar a (0, 0).

Observació

La solució esperada és un backtracking sense esporgar, però en la correcció manual valorarem positivament solucions més astutes.

Public test cases

  • Input

    1 -2
4
1 -2
1 100
-100 -2
-1 2

23 42
2
7 4
-1000000 1000000

20 10
4
20 10
-20 -10
20 10
-20 -10

1000000 1000000
6
1000000 1000000
1000000 1000000
1000000 1000000
-1000000 -1000000
-1000000 -1000000
-1000000 -1000000

    Output

    4
0
14
315
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++