Repeticiones, conflictos y coincidencias en una lista de personas X41925
Dada una lista de personas descritas por un identificador i un nombre, hay que calcular tres cosas:
- Repeticiones: número de parejas de personas con el mismo identificador y el mismo nombre.
- Conflictos: número de parejas de personas con el mismo identificador y diferente nombre.
- Coincidencias: número de parejas de personas con diferente identificador y el mismo nombre.
Entrada
La entrada consiste en varios casos. Cada caso empieza con un natural positivo n en una línea, que es el número de personas. Después vienen n líneas, cada una con un natural y un string, que son el identificador y el nombre de una persona. Después va una línea en blanco.
Salida
Para cada caso, la salida tiene tres naturales en una línea, el número de repeticiones, conflictos y coincidencias de la lista de personas de entrada.
Observación
Evaluación sobre 10 puntos:
- Solución lenta: 5 puntos.
- Solución rápida: 10 puntos.
Entendemos por solución rápida una que es correcta, de coste nlog(n) y que supera los juegos de prueba públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y supera los juegos de prueba públicos.
Input
3 1 joel 1 joel 0 joel 11 0 anabel 4 maria 1 anabel 1 nestor 3 maria 4 anabel 2 anabel 4 maria 4 nestor 3 anabel 2 david 18 0 rosabel 2 robert 2 joan 1 silvia 5 rosabel 5 rosabel 3 silvia 1 silvia 5 silvia 5 silvia 1 silvia 4 joel 3 david 5 rosabel 5 joel 2 rosabel 3 joan 5 silvia 5 0 silvia 0 silvia 0 silvia 0 silvia 0 silvia 7 2 desi 4 desi 5 desi 6 desi 0 desi 1 desi 6 desi 3 0 anabel 0 sandra 0 silvia 2 0 nestor 1 nestor 13 0 ferran 2 aleix 0 maxtor 0 ferran 1 cesar 1 maxtor 2 maxtor 0 cesar 1 maxtor 2 maxtor 2 cesar 2 aleix 0 aleix 10 1 maria 0 maria 4 aleix 4 aleix 1 maria 0 maria 2 aleix 4 aleix 0 aleix 2 maria 14 0 nestor 1 nestor 2 nestor 2 nestor 0 silvia 2 marisa 1 marisa 0 silvia 2 marisa 0 nestor 2 marisa 1 silvia 0 nestor 1 nestor 16 2 robert 0 robert 2 laura 0 joan 1 joan 1 robert 1 laura 2 joan 0 joan 1 robert 2 joan 0 robert 1 robert 2 robert 0 joan 2 joan 7 1 rosabel 0 rosabel 0 rosabel 2 rosabel 0 rosabel 2 rosabel 1 rosabel 7 6 nuria 4 nuria 4 nuria 5 nuria 1 nuria 5 nuria 2 nuria 15 0 nestor 0 angels 2 david 2 angels 2 nestor 1 david 1 david 0 david 2 angels 0 angels 2 angels 1 david 1 nestor 0 robert 2 robert 19 16 sandra 16 robert 7 joel 10 joel 0 robert 4 robert 13 robert 11 marisa 2 robert 11 robert 7 marisa 7 marisa 13 joel 12 marisa 1 joel 13 marisa 9 sandra 12 marisa 10 marisa 6 0 david 0 david 0 david 0 david 0 david 0 david 4 0 oscar 0 oscar 0 oscar 0 oscar 16 5 nestor 3 oscar 5 robert 5 robert 5 robert 3 cesar 0 oscar 5 angels 4 robert 6 robert 7 oscar 2 angels 4 oscar 5 cesar 2 angels 0 cesar 11 2 robert 1 ferran 3 robert 3 robert 1 ferran 0 robert 0 robert 2 robert 1 ferran 2 robert 1 robert 11 4 arisa 5 arisa 3 oscar 7 oscar 7 arisa 1 arisa 6 oscar 3 arisa 4 oscar 9 oscar 0 oscar
Output
1 0 2 1 8 13 9 21 24 10 0 0 1 0 20 0 3 0 0 0 1 4 19 13 5 3 15 9 17 21 11 24 32 5 0 16 2 0 19 7 24 17 2 8 41 15 0 0 6 0 0 4 15 18 8 3 23 0 3 25