4001 - NNeNerNerdNerdsNerdsoNerdson

Created by V Copa UPR - Manuel Alejandro Diaz Perez
Added by Kino (2018-05-21)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Let s be a string of characters, h(s) is the number of characters of s.

Let S be a set of strings:
  • P(S) is the set of all different strings (with at least one letter) that are prefixes of some string in S.
  • w(S,s) is the number of strings in S that have s as a prefix.
  • W(S) is the sum of w(S, s) for every string s in S.
  • H(S) is the sum of h(s) for every string s in S.
Given a set Q of N different strings, we need to find a subset S of Q that minimizes the following function F:
F (S) = | W (P (S)) - H (P (S)) |
Sea s una cadena de caracteres, h(s) es la cantidad de caracteres de s.
Sea S un conjunto de cadenas:
- P(S) es el conjunto de todas las cadenas diferentes (con al menos una letra) que son prefijos de alguna cadena en S.
- w(S,s) es la cantidad de cadenas en S que tienen a s como prefijo.
- W(S) es la suma de w(S,s) para toda cadena s en S.
- H(S) es la suma de h(s) para toda cadena s en S.

Dado un conjunto Q de N cadenas diferentes, se necesita encontrar un subconjunto S de Q que minimice la siguiente funcion F:
F(S) = | W( P(S) ) - H( P(S) ) |

Let s be a string of characters, h(s) is the number of characters of s.

Let S be a set of strings:
  • P(S) is the set of all different strings (with at least one letter) that are prefixes of some string in S.
  • w(S,s) is the number of strings in S that have s as a prefix.
  • W(S) is the sum of w(S, s) for every string s in S.
  • H(S) is the sum of h(s) for every string s in S.
Given a set Q of N different strings, we need to find a subset S of Q that minimizes the following function F:
F (S) = | W (P (S)) - H (P (S)) |

Input specification

The first line contains an integer N (N <= 75311), the number of strings in the set Q. Each of the next N lines contains a string, the strings of the set Q. It is guaranteed that all strings will be different, will be composed only of lowercase letters of the English alphabet and the sum of the lengths of all the strings will be less than or equal to 75311.
La primera línea contiene un entero N (N <= 75311), la cantidad de cadenas en el conjunto Q. Cada una de las proximas N líneas contiene una cadena de caracteres, las cadenas del conjunto Q. Está garantizado que todas las cadenas serán diferentes, estarán compuestas solo por letras minúsculas del alfabeto inglés y la suma de las longitudes de todas las cadenas sera menor o igual 75311.
;jsessionid=6A8660FB94DC08762104A704C1069D61
The first line contains an integer N (N <= 75311), the number of strings in the set Q. Each of the next N lines contains a string, the strings of the set Q. It is guaranteed that all strings will be different, will be composed only of lowercase letters of the English alphabet and the sum of the lengths of all the strings will be less than or equal to 75311.

Output specification

The output consists of a single line with two integers separated by spaces, the values ​​of y W( P(S) ) and H( P(S) ), if there are several solutions that minimize the function F, print the values ​​of the one that maximize W( P(S) ), and if there are still several solutions, print the values ​​of the one that minimizes H( P(S) ).
La salida consiste de una sola línea con dos enteros separados por espacios, los valores de  y W( P(S) ) y H( P(S) ), de haber varias soluciones que minicen la funcion F, imprima los valores de aquella que maximice W( P(S) ), y si aun existen varias soluciones, imprima los valores de aquella que minimice H( P(S) ).
;jsessionid=6A8660FB94DC08762104A704C1069D61
The first line contains an integer N (N <= 75311), the number of strings in the set Q. Each of the next N lines contains a string, the strings of the set Q. It is guaranteed that all strings will be different, will be composed only of lowercase letters of the English alphabet and the sum of the lengths of all the strings will be less than or equal to 75311.

Sample input

1
alejandra

Sample output

45 45

Hint(s)