Cuantos partidos gana cada uno? X46022


Statement
 

pdf   zip

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 nn 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 2n2n 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 nn en una primera línea. Después, hay una segunda línea con una lista de nn 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 nn 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)n\log(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++