Eliminació per parells P84545


Statement
 

pdf   zip

html

Considereu un conjunt C amb 2n naturals (possiblement repetits), un subconjunt S de C amb n nombres, i una k entre 0 i n. Heu de fer n parells amb els nombres de C, de manera que cada nombre aparegui a un parell. Després, de k d’aquests parells us en quedeu el mínim nombre (o un dels dos, si són iguals), i dels altres nk parells us en quedeu el màxim nombre (o un dels dos, si són iguals). El resultat final ha de ser S.

Per exemple, si n = 3, C = { 1, 2, 3, 4, 4, 6 }, S = { 1, 4, 4 }, i k = 1, podem quedar-nos amb min(1, 6) = 1, max(3, 4) = 4, i max(2, 4) = 4.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i k, seguits d’una línia amb els 2n nombres de C, seguida s’una línia amb els n nombres d’S. Poseu suposar 1 ≤ n ≤ 105, 0 ≤ kn, que els nombres donats es troben entre 1 i 108, i que S és un subconjunt de C.

Sortida

Escriviu una línia per a cada cas. Si no es pot aconseguir S a partir de C amb la k donada, escriviu “NO”. Altrament, escriviu "SI", seguit dels vostres n parells. Els k primers parells han de ser els dels mínims, i els altres nk els dels màxims. A part d’això, podeu escriure els parells en qualsevol ordre, tant internament com entre ells. Si hi ha més d’una solució, trieu la que vulgueu, però seguiu estrictament el format dels exemples.

Puntuació

  • Cas A:   Casos on k = 0.  45% Punts 
  • Cas B:   Resta de casos.  55% Punts 
Public test cases
  • Input

    3 1
    1 2 3 4 4 6
    1 4 4
    1 0
    1 100000000
    100000000
    1 0
    1 100000000
    1
    5 2
    10 9 8 7 6 5 4 3 2 1
    2 5 7 9 10
    3 1
    42 42 42 42 42 42
    42 42 42
    

    Output

    SI  1 6  3 4  2 4
    SI  100000000 1
    NO
    SI  2 6  5 8  7 1  9 3  10 4
    SI  42 42  42 42  42 42
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++