Em 2007, o turismo espacial está apenas acessível a poucos
milionários. Mas mesmo com bilhetes a custarem 20 milhões de dólares,
a agência espacial russa tem já a sua agenda cheia de viagens marcadas
até 2009! Em poucos anos, desde que em 2001 Dennis Tito se tornou o
primeiro "turista" a pagar para visitar o espaço (no caso a Estação
Espacial Internacional), as coisas já mudaram muito e existem planos
para mudar muito mais.
Trabalhando na ATEP (Agência de Turismo Espacial Portuguesa), estás encarregado de ajudar a fazer uns estudos de mercado. A ATEP está prestes a terminar uma pequena nave com capacidade para levar apenas um turista espacial, e quer maximizar o seu lucro. O esquema de funcionamento que pretendem implementar é muito simples: quando um cliente quer viajar, indica à ATEP quanto está disposto a pagar por dia de estadia no espaço e quantos dias pretende. Quando a nave está na Terra, a ATEP escolhe o cliente que paga mais por dia de estadia (se existirem vários clientes a pagar um mesmo valor máximo, deve ser escolhido aquele que fez o pedido mais cedo). Depois de efectuada a viagem pelo tempo pedido, a nave regressa à Terra, e escolhe novamente o cliente que paga mais por dia, continuando assim sucessivamente até que todos tenham sido servidos. Se, quando a nave chegar à Terra, não existir nenhum cliente para servir, espera que venha um pedido de alguém, servindo-o imediatamente.
A ATEP quer perceber se este esquema de funcionamento resulta, e está muito interessada em saber quanto tempo cada cliente fica à espera no nosso planeta até ser servido.
Para perceberes melhor como funciona o esquema da ATEP, vê este exemplo:
| Nome do Cliente | Dinheiro que paga (milhões de euros) |
Tempo de viagem (dias - inclui ida e volta) |
Tempo em que o pedido chegou (dias) |
|---|---|---|---|
| Belmiro | 100 | 20 | 5 |
| Amorim | 300 | 10 | 10 |
| Berardo | 500 | 99 | 17 |
Imagina que a nave começa a operar no dia 6. Nessa altura apenas existe o pedido do Belmiro (tinha chegado no dia 5). Portanto, o Belmiro partiu com um tempo de espera de 1 dia. A nave leva-o e demora 20 dias até voltar, chegando portanto no dia 26. Nessa altura, já a ATEP tem em mão os pedidos do Amorim e do Berardo. Quem paga mais é o Berardo, e portanto a nave leva-o, fazendo com que ele tenha esperado precisamente 9 dias. A viagem demora 99 dias e a nave regressa precisamente no dia 125 para servir o Amorim, que esteve à espera 115 dias.
Serás capaz de ajudar a ATEP?
Escreve um programa simula o esquema de funcionamento pretendido e para um conjunto de pedidos dados, descobre quanto tempo cada cliente fica à espera para ser servido, tendo em conta o dia em que o pedido chegou, quanto dinheiro por dia estavam dispostos a pagar e quanto tempo de viagem pretendiam.
Na primeira linha de input vem um número inteiro C, indicando o dia em que a ATEP começa a operar a nave (1 ≤ C ≤ 500000).
Segue-se uma linha com um único número inteiro N, indicando o número de clientes a servir (1 ≤ N ≤ 50000)
Seguem-se N linhas, descrevendo as ofertas dos clientes, vindo estas linhas já ordenadas por ordem crescente da chegada do pedido (nunca chegam dois pedidos de clientes no mesmo dia). Cada uma das linhas tem o seguinte formato: NOME DINHEIRO DURAÇÃO TEMPO_CHEGADA
O output é constituído por N linhas, uma para cada cliente, descrevendo o tempo que cada cliente esperou para ser atendido, no formato NOME DINHEIRO TEMPO_ESPERA (TEMPO_ESPERA é um número inteiro que diz quantos dias esperou o cliente).
A lista dos clientes deve vir ordenada por ordem decrescente do dinheiro pago por dia (a ATEP é gananciosa e quer saber primeiro quanto tempo esperam os "melhores" clientes). Caso existam vários clientes a pagar o mesmo, deve aparecer primeiro no output o cliente que chegou mais cedo.
6 3 Belmiro 100 20 5 Amorim 300 10 10 Berardo 500 99 17
Berardo 500 9 Amorim 300 115 Belmiro 100 1
1 4 Manuel 200 3 3 Joaquim 100 3 4 Maria 150 3 5 Conceicao 250 3 6
Conceicao 250 0 Manuel 200 0 Maria 150 4 Joaquim 100 8