Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PLACICPC - Placar do ICPC

Charles é o diretor de torneio do torneio regional do ICPC de Tumbolia. Sua responsabilidade é garantir que o torneio corra perfeitamento, que as regras sejam seguidas, e, claro, anunciar o placar final da competição.

De acordo com as regras do ICPC, um time com mais problemas resolvidos fica acima de um time com menos problemas resolvidos. Se dois times têm o mesmo número de problemas resolvidos, o time com a menor penalidade fica acima (no caso de os dois times terem o mesmo número de problemas resolvidos e a mesma penalidade, Charles considera eles empatados).

A penalidade total de um time é a soma da penalidade de todos problemas que o time resolveu. A penalidade de um problema é TP+EPxFA, onde TP é a penalidade de tempo para aquele problema, EP é a penalidade de erro da competição e FA é o número de tentativas frustradas de resolver o problema antes de submeter uma solução certa.

A penalidade de tempo para um problema é o tempo desde o início da competição, em minutos, que time demorou para resolver o problema. A penalidade de erro é um inteiro positivo escolhido pelo diretor do torneio, designada para premiar times que submetam soluções corretas na primeira tentativa.

Charles quer mudar a penalidade de erro do valor “padrão” de 20 minutos para esquentar as coisas. Para estudar os efeitos dessa mudança no placar final, ele quer saber o limite de penalidades de erro que não mudam as posições finais.

Em outras palavras, se o time A está na frente do time B no placar original, então A deve estar na frente de B no placar modificado; se A e B estão empatados no placar original, eles devem estar empatados no placar modificado (o placar original é aquele obtido com uma penalidade de erro de 20 minutos).

Charles está muito ocupado organizando a regional tumboliana, então ele pediu para você fazer um programa que vai calcular o limite para ele.

Entrada

A entrada contém diversos casos de teste. A primeira linha de cada caso de teste contém dois inteiros T e P separados por um espaço, indicando o número de times e o número de problemas, respectivamente (2 <= T <= 100, 1 <= P <= 10). Cada uma das próximas T linhas descreve a perfomance de um time. A descrição da performance de um time é uma linha contendo P descrições de problemas separados por um espaço em branco. Os times não são necessariamente dados na ordem da colocação final.

A descrição de cada problema é uma string “A/S”, onde A é um inteiro representando o número de tentativas que o time correspondente fez para resolver o problema (0 <= A <= 100), e S pode ser tanto “-”, se o time não resolveu o problema, ou um inteiro indicando quantos minutos o time demorou para submeter um solução correta (1 <= S <= 300). Tentativas feitas depois da primeira correta não são contadas.

O final da entrada é dado por T = P = 0.

Saída

Para cada caso de teste da entrada imprima dois inteiros positivos separados por um espaço, indicando a menor e a maior penalidades por erro que não alterariam a colocação final. Se não existir um limite superior para a penalidade por erro, imprima um “*” ao invés do limite superior.

Exemplo

Entrada
5 3
0/- 0/- 0/-
2/- 2/- 1/-
1/60 1/165 1/-
1/80 0/- 2/120
0/- 1/17 0/-
4 2
17/- 5/-
2/7 3/-
3/- 2/-
1/15 0/-
3 2
1/- 2/15
2/53 1/17
1/70 1/20
0 0

Saída
1 24
9 *
20 20

Adicionado por:Wanderley Guimarăes
Data:2008-08-09
Tempo limite:0.946s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2007

hide comments
2011-10-01 19:05:06 thiagojobson [UERN]
Suspeito que nos casos de teste S pode ser igual a 0. Tem caras na Maratona que săo mesmo muito ninjas :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.