Difference between revisions of "Problema da prefeitura em crise (sem XML)"

Revision as of 04:44, 10 June 2009

Dificuldade única

Uma prefeitura está em período de baixa arrecadação e não tem condições de fazer o pagamento integral da sua folha de pagamento.

O prefeito decidiu que iria pagar com a verba disponível somente aquelas pessoas que recebem os menores salários, pois, segundo sua interpretação, elas seriam as mais necessitadas.

Você foi contratado como consultor externo para fazer um programa que seja capaz de informar quais os funcionários que receberão salarial.

Algumas considerações:

• Não havendo possibilidade de atender todas as pessoas de uma mesma faixa salarial, a prioridade é para aquelas com maior idade. Caso ainda haja empate, a prioridade é para aquelas cujo nome venha primeiro na ordem alfabética.
• Não há homônimos na prefeitura.
• A idade sempre será um número inteiro e estará no intervalo fechado entre 18 e 100.
• O salário sempre será um número inteiro e estará no intervalo fechado entre 1 e 1000.
• As entradas não estão ordenadas.

Entrada

A entrada consistirá de vários casos de teste. Cada caso de teste é constituido por:

1. Um linha contendo um inteiro K (0<=K<=1000000) e um inteiro J (0<=J<=1000). K representa a verba disponível para o pagamento da folha. J representa o número de servidores.
2. As próximas J linhas serão apresentadas no formato:

<nome> <idade> <salario>

O nome terá no máximo 50 caracteres e não conterá espaços. A entrada termina quando K e J forem informados como zero.

Saída

A saída deverá seguir rigorosamente o exemplo abaixo, indicando para cada K o nome dos funcionários que receberão salário. Assim, para cada caso de testes deve ser gerada a seguinte saída:

• A primeira linha deve conter a cadeia "Teste N", onde N é representa o número do caso de teste começando em 1.
• As linhas seguintes são os nomes dos funcionários em ordem alfabética.
• A última linha deve ser em branco.

Exemplo

Entrada

5 5
Z 29 10
D 30 10
A 30 10
E 68 12 
C 25 5
15 5
Z 29 10
D 30 10
A 30 10
E 68 12 
C 25 5
20 5
Z 29 10
D 30 10
A 30 10
E 68 12 
C 25 5
25 5
Z 29 10
D 30 10
A 30 10
E 68 12 
C 25 5
35 5
Z 29 10
D 30 10
A 30 10
E 68 12 
C 25 5
50 5
Z 29 10
D 30 10
A 30 10
E 68 12 
C 25 5
0

Saída

Teste 1
C

Teste 2
A
C

Teste 3
A
C

Teste 4
A
C
D

Teste 5
A
C
D
Z

Teste 6
A
C
D
E
Z