Trabalho Prático 3 - Menságens Assíncronas

Mensagens assíncronas Um dos grandes desafios para arquitetura de softwares distribuídos é lidar com mensagens que transitam entre diversos serviços. Um aspecto fundamental para o funcionamento adequado de um sistema com várias partes é que as mensagens enviadas por um serviço A cheguem a um serviço B de forma correta, e que o uso de memória por ambos seja o mais eficiente possível. O nosso desafio é construir um sistema que se comunique com outros sistemas (que chamaremos de sistemas externos) e esteja apto a receber e responder mensagens do modo correto. Algumas regras governam o funcionamento desse sistema: - As únicas mensagens que o sistema envia são respostas a mensagens que ele respondeu; - O sistema envia no máximo uma mensagem como resposta a uma mensagem que recebeu; - O sistema nunca enviará uma nova mensagem até que tenha recebido resposta da mensagem que enviou anteriormente. Enviar e receber mensagens em sistemas distribuídos é também conhecido como uma arquitetura voltada a eventos, e diversos softwares do mercado (como o Apache Kafka, Rabbit MQ, entre outros) trabalham com esse conceito para executar suas ações. No nosso caso, teremos três tipos de eventos: - R X, que indica que um evento foi recebido de um sistema X; - E X, que indica que o nosso sistema enviou uma mensagem a outro sistema X; - T X indicando que X segundos se passaram entre o evento anterior e o evento posterior a esse registro. Se dois registros consecutivos não possuem registros do tipo T X entre eles, exatamente 1 segundo se passou entre esses dois eventos. O Tempo de Resposta de uma mensagem é o tempo que se passa entre o recebimento da mensagem pelo nosso sistema e o envio de uma resposta por ele. O Tempo de Resposta de uma mensagem é o tempo que se passa entre o recebimento da mensagem por nosso sistema e o envio da resposta a essa mensagem por nós. Se um sistema externo recebeu respostas para todas as suas mensagens, o Tempo de Resposta Total para ele é a soma dos Tempos de Respostas para as mensagens dele; caso contrário o Tempo de Resposta Total é -1. Um requerimento fundamental para o nosso sistema é que ele aloque memória de forma dinâmica, para evitar desperdício. Por isso, todas as mensagens que chegam dos sistemas externos devem ser armazenadas dinamicamente. Dada a lista de registros de eventos do nosso sistema, sua tarefa é determinar o Tempo de Resposta Total para cada sistema externo. Entrada A primeira linha da entrada contém um inteiro N, o número de registros. Os sistemas externos são identificados por números inteiros. Cada uma das N linhas seguintes descreve um registro e contém um caractere (R, E ou T) seguido de um número inteiro X. No caso de registros dos tipos R e E o valor de X indica um sistema externo no caso do registro de tipo T, o valor de X indica o número de segundos que se passaram entre o evento anterior e o posterior. Saída Para cada sistema externo, seu programa deve produzir uma linha na saída contendo dois inteiros: o número do sistema externo e o Tempo de Resposta Total para esse sistema externo, em ordem crescente dos números dos sistemas externos. Restrições 1 ≤ N ≤ 20 1 ≤ X ≤ 100 Exemplos Entrada 5 R 2 R 3 T 5 E 2 E 3 Saída 2 6 3 6 Entrada 14 R 12 T 2 R 23 T 3 R 45 E 45 R 45 E 23 R 23 T 2 E 23 R 34 E 12 E 34 Saída 12 13 23 8 34 2 45 -1