Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
Friendly Queue
Question:
In the university there are queues everywhere. You have queue
for the photocopy office, queue in the canteen. This is why
the students got used to the idea of friendly queue. In a friendly
queue, to optimize the time, it is accepted by everybody that
if one has a friend in the queue, he or she can give the money
to the friend and the things get faster.
If he has a friend in the queue he gives money
to the front most friend. And, his waiting time
is his friends current position in the queue.
If there is no friend in the queue, he goes to the end of queue.
And, his waiting time is the number of
people before him (plus 1 for himself).
Question: Write a program that finds
the minimum total waiting for the given list of people.
Input specification
You will be first given three numbers: the number of students (n)
(which represent student IDs from 1 to n), the number of friend
pairs (m), and the number of students (k) who come to (or leave from)
the queue where 0 ≤ (n, m, and k) ≤ 2000.
Then, in the following m lines, you will be given pairs of
student IDs (the friends list). In the following k lines,
you will be given
- a letter 'N' and the ID of person coming to the queue
- or a letter 'R': the front person leaving from the queue.
Output specification:
Show the mimimum total waiting time for all students.
Sample Input I
10 5 6
2 1
4 2
6 5
8 1
1 6
N 7
N 6
N 1
N 4
R
N 2
|
Sample Output I
10
|
Explanation: There are 10 people, and 5
pairs of friends. Then,
- Firstly Student 7 comes. Because there is no one in the
queue (he is the first one), he has to wait only for himself.
- Then, Student 6 comes. He doesn't have any friend in the queue,
and he goes to the end of queue. He will wait for (one student
plus one for himeself) 2.
- Then Student 1 comes. 6 is his friend. So, he gives the money
to him, and leaves from the queue. He waits for two units time.
(one person before them, wait:2).
- And, Student 4 comes. He does not have a friend in the queue,
So he goes to the end of queue. (has to wait for 3).
- After the arrival of 4, the front most student leaves.
- Student 2 arrives. He has a friend (4) in the queue.
He gives money to his friend. And waits 2 units time
(the current position of his friend).
Then, the total waiting time is 10.
(7 waits 1),
(6 waits 2), (1 waits 2),(4 waits 3), and (2 waits 2).
Для отправки решений необходимо выполнить вход.
|