Eliminació per parells P84545
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 n−k 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 ≤ k ≤ n, 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 n−k 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
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
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++