How many games does each person win? X46022


Statement
 

pdf   zip

html

With the aim of doing something in favor of harmony and solidarity for the peoples in the world, and to show that there are better ways to solve conflicts, a multinational company has decided to organize a ping-pong (table tennis) tournament between two teams, one consisting of Russian employees, and another consisting of employes from the USA.

There are n players on each team. Each player plays two matches against each member of the other team. Therefore, in total each player will play 2n ping-pong matches.

Actually, we can predict in advance how many matches each player will win, since we know the level of each employee as a ping-pong player. Any employee always wins the two matches against any other with an inferior level. In contrast, when someone plays with another player of the same level, then he/she wins exactly one of the two matches, therefore loosing the other.

Input

The input consists of several cases. Each case starts with a natural number n in one line. The second line contains a list of n pairs (string, natural number) with name and level of each of the Russian players. The third line, with the same format, lists the USA players. Finally, there is a blank line.

Output

For each case, the output has two lines. In the first, there is a list of n pairs (string, natural number) showing the name and number of matches won by each of the Russian players. The names have to go in the order in which they were read from the input. A second line contains the same information and with the same format but for the USA players. After that, a blank line comes.

Observation

Evaluation over 10 points:

  • Slow solution: 5 points.
  • Fast solution: 10 points.

A fast solution is correct, has cost nlog(n) and passes both public and private test cases. A slow solution is not fast, but it is correct and passes the public test cases.

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