Cuantos partidos gana cada uno? X46022


Statement
 

pdf   zip

html

Con el ánimo de hacer un gesto en pro de la concordia y la solidaridad entre los pueblos del mundo, y mostrar que hay mejores vias y más inocuas de solucionar conflictos, una compañía multinacional ha decidido organizar un torneo de ping-pong entre dos equipos, uno formado por trabajadores de la compañía que son Rusos, y otro formado por trabajadores de la compañía que son Estadounidenses.

Hay n personas en cada equipo. Cada miembro de un equipo juega dos partidas contra cada miembro del otro equipo. Por tanto, en total cada persona habrá jugado 2n partidas de ping-pong.

En realidad, se puede anticipar cuantas partidas ganará cada uno, porque se conoce el nivel de cada persona como jugador de ping-pong. Qualquier persona siempre gana las dos partidas a qualquier otra que tenga un nivel inferior. En cambio, cuando una persona juega con alguien del mismo nivel, entonces ganará exactamente una de las dos partidas, y por tanto perderá la otra.

Se trata de calcular cuantas partidas ganará cada persona en total.

Entrada

La entrada tiene varios casos. Cada caso comienza con un natural positivo n en una primera línea. Después, hay una segunda línea con una lista de n parejas (string, natural) indicando el nombre y el nivel de los jugadores Rusos. Después hay una tercera línea en el mismo formato e indicando nombre y nivel de los jugadores Estadounidenses. Finalmente hay una línea en blanco.

Salida

Para cada caso, la salida tiene dos líneas. Una primera línea con una lista de n parejas (string, natural) indicando el nombre y el número de partidos ganados por cada uno de los jugadores Rusos. Los nombres deben aparecer en el mismo orden que en la entrada. Una segunda línea tiene la misma información y en el mismo formato para los jugadores Estadounidenses. Finalmente sigue una línea en blanco.

Observación

Evaluación sobre 10 puntos:

  • Solución lenta: 5 puntos.
  • Solución rápida: 10 puntos.

Entendemos como solución rápida una que es correcta, de coste nlog(n) y capaz de superar los juegos de pruebas públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de pruebas públicos.

Public test cases

  • Input

    8
Victoria 2 Danyl 3 Irina 7 Denis 3 Alexey 6 Xenia 8 Sofia 2 Polina 1
Matthew 2 Joseph 7 Karen 2 Daniel 2 Thomas 2 John 5 Anthony 8 Michael 7

10
Elizaveta 3 Artyom 4 Sofia 2 Konstantin 2 Ivan 7 Alexander 6 Daria 5 Nikita 5 Nikolai 5 Adelina 6
John 1 Barbara 8 Robert 5 Jessica 6 Richard 8 Anthony 4 Matthew 7 James 1 Mary 5 Elizabeth 4

5
Xenia 1 Svetlana 8 Artyom 6 Alexey 5 Arina 4
Michael 2 Jennifer 6 Betty 6 Anthony 5 Sandra 5

8
Alexander 7 Denis 8 Mikhail 3 Polina 6 Xenia 2 Danyl 6 Anastasia 3 Daria 7
Christopher 6 Linda 7 Lisa 5 Michael 4 John 8 Richard 6 Elizabeth 4 Mary 5

14
Danyl 7 Konstantin 6 Svetlana 2 Sofia 5 Elena 2 Natalia 8 Victoria 4 Daria 8 Nikolai 2 Polina 1 Vera 4 Alexey 4 Adelina 5 Dmitry 4
Linda 7 Thomas 5 Sandra 7 Patricia 2 Betty 6 Karen 4 Jennifer 1 David 5 Daniel 4 Charles 3 Lisa 5 Michael 4 Jessica 2 William 2

11
Vera 3 Anastasia 5 Elizaveta 1 Sergey 2 Victoria 1 Maksim/Maxim 8 Alexander 6 Konstantin 6 Svetlana 1 Nikita 3 Denis 3
Sarah 2 Mary 5 Joseph 1 Robert 5 Matthew 4 Michael 3 James 5 Barbara 5 David 7 Elizabeth 3 Sandra 2

14
Konstantin 6 Alexey 2 Xenia 8 Sergey 5 Svetlana 5 Anastasia 4 Yevgeny 8 Alexander 1 Danyl 6 Daria 7 Elizaveta 3 Nadezhda 5 Sofia 6 Elena 2
Lisa 3 Daniel 7 Christopher 3 James 5 Anthony 1 Jessica 3 Sarah 2 Linda 3 Matthew 3 Patricia 8 Susan 3 Michael 4 Sandra 1 Thomas 8

8
Alexey 6 Denis 6 Vera 4 Sofia 2 Daria 7 Konstantin 2 Ivan 8 Arina 2
Mary 2 Jennifer 4 Robert 7 David 3 Elizabeth 6 Richard 8 Nancy 8 Anthony 7

7
Alexander 3 Sergey 6 Mikhail 3 Nikita 7 Roman 5 Arina 4 Polina 2
Thomas 6 Michael 1 Richard 2 Barbara 7 Elizabeth 6 James 3 Sandra 7

7
Artyom 1 Svetlana 6 Elena 4 Daria 7 Maksim/Maxim 3 Elizaveta 2 Alexey 5
Jennifer 6 Thomas 5 Daniel 6 Elizabeth 2 Robert 1 Betty 5 Sarah 4

5
Anastasia 1 Alexey 5 Elena 3 Elizaveta 4 Sergey 3
Mary 4 Anthony 8 Jennifer 1 Betty 7 Lisa 6

5
Arina 8 Artyom 4 Danyl 8 Maksim/Maxim 5 Nikita 3
Michael 1 Christopher 7 Barbara 6 Joseph 3 Nancy 8

12
Xenia 5 Maksim/Maxim 6 Ivan 1 Anastasia 8 Victoria 6 Daria 3 Natalia 1 Irina 1 Alexander 3 Konstantin 4 Nadezhda 2 Vera 1
Barbara 3 Jessica 2 William 2 Matthew 3 Jennifer 1 Robert 8 Michael 1 Charles 4 Christopher 8 Karen 2 Joseph 4 Daniel 2

11
Polina 6 Yevgeny 6 Artyom 7 Denis 8 Sofia 7 Konstantin 6 Nikita 8 Maksim/Maxim 2 Elena 6 Roman 3 Irina 2
Jennifer 1 John 7 David 6 Matthew 3 Michael 1 Christopher 2 Daniel 8 Susan 6 Anthony 6 William 2 Thomas 4

6
Denis 2 Alexey 8 Svetlana 1 Vera 6 Adelina 2 Sergey 7
Karen 6 Mary 2 Richard 7 Nancy 4 Sarah 3 Joseph 5

9
Elizaveta 3 Nadezhda 7 Yevgeny 8 Irina 7 Sergey 1 Nikita 8 Roman 2 Nikolai 8 Natalia 1
Linda 7 Elizabeth 3 Nancy 1 Joseph 7 Lisa 8 Michael 6 David 5 Sarah 5 Susan 4

13
Nadezhda 2 Irina 8 Alexey 4 Victoria 8 Artyom 7 Dmitry 2 Daria 4 Elizaveta 8 Adelina 4 Mikhail 1 Konstantin 7 Danyl 3 Anastasia 7
Sandra 6 Lisa 8 Linda 7 Susan 4 Mary 4 Betty 4 Daniel 8 Elizabeth 6 William 6 Thomas 3 Jennifer 8 David 3 Matthew 6

7
Nikolai 3 Yevgeny 5 Vera 3 Danyl 5 Roman 3 Alexey 4 Irina 5
Jennifer 8 Sandra 2 Joseph 5 Lisa 5 James 4 Sarah 5 Daniel 6

8
Alexander 1 Nadezhda 2 Anastasia 5 Vera 4 Nikita 3 Irina 4 Sergey 3 Elizaveta 2
Christopher 7 David 6 Betty 6 Mary 8 Jennifer 5 Karen 3 Elizabeth 5 William 1

11
Nikolai 6 Nadezhda 8 Roman 3 Vera 4 Polina 1 Konstantin 6 Ivan 3 Danyl 7 Victoria 2 Maksim/Maxim 8 Anastasia 8
Patricia 1 Charles 8 Daniel 3 Karen 8 David 3 Matthew 2 Barbara 4 James 7 Elizabeth 3 Sarah 3 Sandra 2

    Output

    Victoria 4 Danyl 8 Irina 12 Denis 8 Alexey 10 Xenia 15 Sofia 4 Polina 0
Matthew 4 Joseph 13 Karen 4 Daniel 4 Thomas 4 John 10 Anthony 15 Michael 13

Elizaveta 4 Artyom 6 Sofia 4 Konstantin 4 Ivan 15 Alexander 13 Daria 10 Nikita 10 Nikolai 10 Adelina 13
John 0 Barbara 20 Robert 11 Jessica 16 Richard 20 Anthony 7 Matthew 19 James 0 Mary 11 Elizabeth 7

Xenia 0 Svetlana 10 Artyom 8 Alexey 4 Arina 2
Michael 2 Jennifer 7 Betty 7 Anthony 5 Sandra 5

Alexander 13 Denis 15 Mikhail 0 Polina 10 Xenia 0 Danyl 10 Anastasia 0 Daria 13
Christopher 8 Linda 12 Lisa 6 Michael 6 John 15 Richard 8 Elizabeth 6 Mary 6

Danyl 26 Konstantin 23 Svetlana 5 Sofia 19 Elena 5 Natalia 28 Victoria 13 Daria 28 Nikolai 5 Polina 1 Vera 13 Alexey 13 Adelina 19 Dmitry 13
Linda 23 Thomas 18 Sandra 23 Patricia 5 Betty 21 Karen 12 Jennifer 1 David 18 Daniel 12 Charles 8 Lisa 18 Michael 12 Jessica 5 William 5

Vera 8 Anastasia 16 Elizaveta 1 Sergey 4 Victoria 1 Maksim/Maxim 22 Alexander 20 Konstantin 20 Svetlana 1 Nikita 8 Denis 8
Sarah 7 Mary 15 Joseph 3 Robert 15 Matthew 14 Michael 11 James 15 Barbara 15 David 20 Elizabeth 11 Sandra 7

Konstantin 22 Alexey 5 Xenia 26 Sergey 21 Svetlana 21 Anastasia 19 Yevgeny 26 Alexander 2 Danyl 22 Daria 23 Elizaveta 12 Nadezhda 21 Sofia 22 Elena 5
Lisa 7 Daniel 23 Christopher 7 James 13 Anthony 1 Jessica 7 Sarah 4 Linda 7 Matthew 7 Patricia 26 Susan 7 Michael 9 Sandra 1 Thomas 26

Alexey 7 Denis 7 Vera 5 Sofia 1 Daria 10 Konstantin 1 Ivan 14 Arina 1
Mary 3 Jennifer 7 Robert 13 David 6 Elizabeth 10 Richard 15 Nancy 15 Anthony 13

Alexander 5 Sergey 8 Mikhail 5 Nikita 12 Roman 6 Arina 6 Polina 3
Thomas 11 Michael 0 Richard 1 Barbara 13 Elizabeth 11 James 4 Sandra 13

Artyom 1 Svetlana 12 Elena 5 Daria 14 Maksim/Maxim 4 Elizaveta 3 Alexey 8
Jennifer 11 Thomas 9 Daniel 11 Elizabeth 3 Robert 1 Betty 9 Sarah 7

Anastasia 1 Alexey 4 Elena 2 Elizaveta 3 Sergey 2
Mary 7 Anthony 10 Jennifer 1 Betty 10 Lisa 10

Arina 9 Artyom 4 Danyl 9 Maksim/Maxim 4 Nikita 3
Michael 0 Christopher 6 Barbara 6 Joseph 1 Nancy 8

Xenia 20 Maksim/Maxim 20 Ivan 2 Anastasia 22 Victoria 20 Daria 14 Natalia 2 Irina 2 Alexander 14 Konstantin 18 Nadezhda 8 Vera 2
Barbara 12 Jessica 9 William 9 Matthew 12 Jennifer 4 Robert 23 Michael 4 Charles 15 Christopher 23 Karen 9 Joseph 15 Daniel 9

Polina 15 Yevgeny 15 Artyom 19 Denis 21 Sofia 19 Konstantin 15 Nikita 21 Maksim/Maxim 6 Elena 15 Roman 9 Irina 6
Jennifer 0 John 16 David 10 Matthew 5 Michael 0 Christopher 2 Daniel 20 Susan 10 Anthony 10 William 2 Thomas 6

Denis 1 Alexey 12 Svetlana 0 Vera 9 Adelina 1 Sergey 11
Karen 7 Mary 4 Richard 9 Nancy 6 Sarah 6 Joseph 6

Elizaveta 3 Nadezhda 14 Yevgeny 17 Irina 14 Sergey 1 Nikita 17 Roman 2 Nikolai 17 Natalia 1
Linda 10 Elizabeth 7 Nancy 2 Joseph 10 Lisa 15 Michael 8 David 8 Sarah 8 Susan 8

Nadezhda 0 Irina 23 Alexey 7 Victoria 23 Artyom 19 Dmitry 0 Daria 7 Elizaveta 23 Adelina 7 Mikhail 0 Konstantin 19 Danyl 2 Anastasia 19
Sandra 14 Lisa 23 Linda 17 Susan 11 Mary 11 Betty 11 Daniel 23 Elizabeth 14 William 14 Thomas 7 Jennifer 23 David 7 Matthew 14

Nikolai 2 Yevgeny 7 Vera 2 Danyl 7 Roman 2 Alexey 3 Irina 7
Jennifer 14 Sandra 0 Joseph 11 Lisa 11 James 7 Sarah 11 Daniel 14

Alexander 1 Nadezhda 2 Anastasia 6 Vera 4 Nikita 3 Irina 4 Sergey 3 Elizaveta 2
Christopher 16 David 16 Betty 16 Mary 16 Jennifer 15 Karen 8 Elizabeth 15 William 1

Nikolai 16 Nadezhda 20 Roman 10 Vera 15 Polina 1 Konstantin 16 Ivan 10 Danyl 17 Victoria 4 Maksim/Maxim 20 Anastasia 20
Patricia 1 Charles 19 Daniel 6 Karen 19 David 6 Matthew 3 Barbara 9 James 15 Elizabeth 6 Sarah 6 Sandra 3
    • Information
    Author
    PRO1
    Language
    Spanish
    Translator
    Original language
    Catalan
    Other languages
    Catalan English
    Official solutions
    C++
    User solutions
    C++