ESTAC - Estacionamento
Um estacionamento utiliza um terreno em que os veículos têm que ser guardados em fila única, um atrás do outro. A tarifa tem o valor fixo de R$ 10,00
por veiculo estacionado, cobrada na entrada, independente de seu porte e tempo de permanência. Como o estacionamento é muito concorrido, nem todos os veículos que chegam ao estacionamento conseguem lugar para estacionar.
Quando um veículo chega ao estacionamento, o atendente primeiro determina se há vaga para esse veículo. Para isso, ele percorre a pé o estacionamento, do início ao fim, procurando um espaço que esteja vago e tenha comprimento maior ou igual ao comprimento do veículo. Para economizar seu tempo e energia, o atendente escolhe o primeiro espaço adequado que encontrar; isto é, o espaço mais próximo do iníıcio.
Uma vez encontrada a vaga para o veículo, o atendente volta para a entrada do estacionamento, pega o veículo e o estaciona no começo do espaço encontrado. Se o atendente não encontrar um espaço adequado, o veículo não entra no estacionamento e a tarifa não é cobrada. Depois de estacionado, o veículo não é movido até o momento em que sai do estacionamento.
O dono do estacionamento está preocupado em saber se os atendentes têm cobrado corretamente a tarifa dos veículos estacionados e pediu para você escrever um programa que, dada a lista de chegadas e saídadas de veículos no estacionamento, determina o faturamento total esperado.
Entrada
A entrada é composta por diversos casos de teste. A primeira linha de um caso de teste contém dois números inteiros C
e N
que indicam respectivamente o comprimento em metros do estacionamento e o número total de eventos ocorridos (chegadas e saídas) de veículos). Cada uma das N
linhas seguintes descreve uma chegada ou saída. Para uma chegada de veículo, a linha contém a letra ‘C’
, seguida de dois inteiros P
e Q
, todos separados por um espaço em branco. P
indica a placa do veículo e Q
o seu comprimento. Para uma saída de veículo, a linha contém a letra ‘S’
seguida de um inteiro P
, separados por um espaço em branco, onde P
indica a placa do veículo. As ações são dadas na ordem cronológica, ou seja, na ordem em que acontecem.
No início de cada caso de teste o estacionamento está vazio. No arquivo de entrada, um veículo sai do estacionamento somente se está realmente estacionado, e a placa de um veículo que chega ao estacionamento nunca é igual a placa de um veículo já estacionado.
Saída
Para cada caso de teste seu programa deve imprimir uma linha contendo um número inteiro representando o faturamento do estacionamento, em reais.
Restrições
1 ≤ C ≤ 1000
1 ≤ N ≤ 10000
1 ≤ Q ≤ 100
1000 ≤ P ≤ 9999
Exemplos
Entrada 10 7 C 1234 5 C 1111 4 C 2222 4 C 4321 3 S 1111 C 2002 6 C 4321 3 30 10 C 1000 10 C 1001 10 C 1002 10 S 1000 S 1002 C 1003 20 S 1001 C 1004 20 S 1004 C 1005 30 20 10 C 1234 20 C 5678 1 S 1234 C 1234 20 C 5678 1 S 1234 C 5678 1 C 1234 20 C 5555 1 S 5678 Saída 30 50 40
Added by: | Wanderley Guimarăes |
Date: | 2012-05-26 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Primeira fase da Maratona de Programaçăo - 2011 |