Dominó P99218


Statement
 

pdf   zip

thehtml

Considerad una generalización del juego del dominó, en la cual las fichas pueden estar repetidas, y donde los números pueden ser arbitrariamente grandes. Dadas diversas piezas, ¿se pueden encadenar todas entre sí?

Entrada

La entrada consiste en diversos casos. Cada caso consiste en el número de piezas n, seguido de las n piezas, siguiendo el formato que se puede apreciar en los ejemplos. Suponed que n está entre 1 y 105, y que los números en las piezas están entre 0 y 109.

Salida

Para cada caso, escribid una solución cualquiera si existe, o “NO” en otro caso.

Puntuación

  • Test-1:  ‍ Entradas con n ≤ 6.  ‍10 Puntos ‍
  • Test-2:  ‍ Entradas donde ningún número aparece más de dos veces.  ‍15 Puntos ‍
  • Test-3:  ‍ Entradas donde no aparecen más de dos números diferentes.  ‍15 Puntos ‍
  • Test-4:  ‍ Entradas sin piezas dobles, sin piezas repetidas, y donde los números que aparecen son exactamente todos los contenidos entre 0 y un cierto x.  ‍25 Puntos ‍
  • Test-5:  ‍ Entradas de todo tipo.  ‍35 Puntos ‍
Public test cases
  • Input

    3  | 0 1 | 2 0 | 1 2 |
    2  | 0 1 | 1 2 |
    5  | 0 3 | 3 1 | 1 0 | 5 2 | 2 4 |
    2  | 2 0 | 1 2 |
    3  | 0 1 | 0 0 | 1 1 |
    4  | 0 1 | 0 0 | 1 0 | 1 1 |
    3  | 42 42 | 42 33 | 42 33 |
    4  | 10 20 | 20 30 | 20 10 | 10 30 |
    3  | 10 100 | 10 1000 | 10 10000 |
    1  | 1000000000 1000000000 |
    

    Output

    | 0 2 | 2 1 | 1 0 |
    | 0 1 | 1 2 |
    NO
    | 0 2 | 2 1 |
    | 0 0 | 0 1 | 1 1 |
    | 0 0 | 0 1 | 1 1 | 1 0 |
    | 33 42 | 42 42 | 42 33 |
    | 10 30 | 30 20 | 20 10 | 10 20 |
    NO
    | 1000000000 1000000000 |
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions