Quants partits guanya cadascú? X46022


Statement
 

pdf   zip

Amb l’ànim de fer un gest en pro de la concòrdia i la solidaritat entre els pobles del món, i mostrar que hi han millors vies i més inòcues de solucionar conflictes, una companyia multinacional ha decidit organitzar un torneig de ping-pong entre dos equips, un format per treballadors de la companyia que son Russos, i un format per treballadors de la companyia que son Estadounidencs.

Hi han nn persones a cada equip. Cada membre d’un equip juga dues partides contra cada membre de l’altre equip. Per tant, en total cada persona haurà jugat 2n2n partides de ping-pong.

En realitat, es pot anticipar quantes partides guanyarà cadascú, perquè es coneix el nivell de cada persona com a jugador de ping-pong. Qualsevol persona sempre guanya les dues partides a qualsevol altri que tingui un nivell inferior. En canvi, quan una persona juga amb algú altri del mateix nivell, llavors guanyarà exactament una de les dues partides, i per tant perdrà l’altra.

Es tracta de calcular quantes partides guanyarà cada persona en total.

Entrada

L’entrada té varis casos. Cada cas comença amb un natural positiu nn en una primera línia. Després, hi ha una segona línia amb una llista de nn parelles (string,natural) indicant el nom i el nivell dels jugadors Russos. Després hi ha una tercera línia amb el mateix format i indicant el nom i el nivell dels jugadors Estadounidencs. Després hi ha una línia en blanc.

Sortida

Per a cada cas, la sortida té dues línies. Una primera línia amb una llista de nn parelles (string,natural) indicant el nom i el nombre de partits guanyats per cadascun dels jugadors Russos. Els noms han de venir en el mateix ordre que a l’entrada. Una segona línia té la mateixa informació i en el mateix format per als jugadors Estadounidencs. Finalment segueix una línia en blanc.

Observació

Avaluació sobre 10 punts:

  • Solució lenta: 5 punts.

  • solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost nlog⁡(n)n\log(n) i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

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
    Catalan
    Other languages
    English Spanish
    Official solutions
    C++
    User solutions
    C++