CCC '15 J4 - Wait Time - Olympiads Online Judge

CCC '15 J4 - Wait Time

Points: 5

Time limit: 2.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2015 Stage 1, Junior #4

You exchange text messages with your friends. Since you receive so many messages, you want to measure how long your friends have to wait for your replies.

Your message device records each received and sent message in order using the following two kinds of entries:

R $X$ ~X~ indicates a message was received from a friend numbered $X$ ~X~;
S $X$ ~X~ indicates a message was sent to a friend numbered $X$ ~X~.

Your message device sends and receives messages instantaneously, and for each consecutive pair of entries described above, either

a single entry W $X$ ~X~ is recorded in between them indicating they occur $X$ ~X~ seconds apart, or
there is no entry between them and they occur one second apart

Several rules of message etiquette are always followed:

the only messages you send are replies to messages that you have received;
you send at most one reply to any message from any particular friend;
your friends do not send a subsequent message until you have replied to their previous message.

The wait time for a message is the time that passes between when you receive it and the time you reply to it. If a friend $X$ ~X~ received a reply to each message they sent, the total wait time for friend $X$ ~X~ is the sum of all wait times for all messages from friend $X$ ~X~. Otherwise, the total wait time for friend $X$ ~X~ is $-1$ ~-1~.

Your job is to determine the total wait time for each friend.

Input Specification

The input consists of the integer $M$ ~M~ ( $1 \le M \le 20$ ~1 \le M \le 20~), followed by $M$ ~M~ lines, where each line consists of one character (W, R, or S), followed by a space, followed by an integer $X$ ~X~ ( $1 \le X \le 100$ ~1 \le X \le 100~). These $M$ ~M~ lines are the entries described above (in order).

Output Specification

Output one line for each friend that sent a message in the form $X$ ~X~ $T$ ~T~ where $X$ ~X~ is a friend number and $T$ ~T~ is the total wait time for friend $X$ ~X~. The lines are in increasing order of the friend numbers.

Sample Input 1

5
R 2
R 3
W 5
S 2
S 3

Output for Sample Input 1

2 6
3 6

Explanation of Output for Sample Input 1

Friend $2$ ~2~ sends a message at time $0$ ~0~ and Friend $3$ ~3~ sends a message at time $1$ ~1~. Friend $2$ ~2~ receives a reply at time $6$ ~6~ and Friend $3$ ~3~ receives a reply at time $7$ ~7~.

Sample Input 2

14
R 12
W 2
R 23
W 3
R 45
S 45
R 45
S 23
R 23
W 2
S 23
R 34
S 12
S 34

Output for Sample Input 2

Explanation of Output for Sample Input 2

For Friend $12$ ~12~, a message is received at time $0$ ~0~ and replied to at time $13$ ~13~. For Friend $23$ ~23~, two messages are exchanged, with the first message having a wait time of $6$ ~6~ seconds and the second message having a wait time of $2$ ~2~ seconds. For Friend $34$ ~34~, a message is received at time $10$ ~10~ and replied to at time $12$ ~12~. Friend $45$ ~45~ sends a message which is never replied to.

Comments

2

stampixel commented on April 4, 2022, 10:11 p.m.

Can someone explain how the wait time in the first line of the second output be "13" seconds? I am a bit confused.

1

Ericsson commented on Jan. 4, 2023, 5:07 a.m.

From my understanding: You add all of the lines together excluding the two lines that are repetitive. So you will be adding "R 12" "W 2", "R 23", "W 3", "R 45", "W 2", "S 23", "R 34", which will be: (1 + 2 + 1 + 3 + 1 + 2 + 1 + 1 = 12). And when it gets to the "S 12", it turned 13 and which is why the waiting time is 13.

1

trinm3005 commented on Nov. 8, 2021, 2:23 p.m.

I'm confused by the example inputs/outputs because in the first when we have R 3, W 5 in between r2 and s2 we get 6, which is what you'd expect if we only looked at the ones in between them but in the second example we get -1 for 45 when there is nothing between the two, shouldn't it be 0?

4

Badmode commented on Nov. 8, 2021, 11:55 p.m.

If a friend $X$ ~X~ received a reply to each message they sent, the total wait time for friend $X$ ~X~ is the sum of all wait times for all messages from friend . Otherwise, the total wait time for friend $X$ ~X~ is $-1$ ~-1~.

In the second sample, friend $45$ ~45~ did not recieve a reply for their second message.

5

Dav_Did commented on Dec. 13, 2020, 6:47 p.m.

My friend would find that so useful

11

tappbros commented on Sept. 12, 2020, 9:37 p.m.

Either you're really popular or your messaging electronic is really bad. You choose.

0

shinigamiking100 commented on Feb. 19, 2017, 4:24 p.m.

In the sample output, it shows "2 6" and "3 6" yet the explanation states that it should be "2 6" and "3 7".

(This is for sample output 1)

0

Kirito commented on Feb. 19, 2017, 4:47 p.m.

This typo was present on the official PDF as well. (Waterloo double check your work plz -.- )

It has been fixed (at least on our site).

14

JJ_G4M3R commented on Nov. 28, 2018, 4:29 a.m.

I don't believe it is a typo. When a reply was sent to friend 3, it was time 7. The only reason the output is "3 6" is because the message from friend 3 was received at time 1 (first message counts as time 0). This logic carries through to the explanation of sample input 2.

0

felixzhang25 commented on Oct. 11, 2018, 1:12 a.m.

Yeah, on wcipeg it still says:

Explanation of Sample 1 Friend 2 sends a message at time 0 and Friend 3 sends a message at time 1. Friend 2 receives a reply at time 6 and Friend 3 receives a reply at time 7.

so it is probably only fixed here!!!

2

seanlee29 commented on Dec. 28, 2019, 11:42 p.m. ← edited →

No fixing required! As pointed out by JJ_G4M3R, it's correct :-)