Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1474. Deadlock detector
Полный переборОлимпиадные задачи на английском языке
| 24/06/2010 | Лето 2010 дорешивание (11D) |
| 16/07/2010 | Лето 2010 - 11 (D) |
Ограничения: время – 4s/8s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Resource sharing is an important problem in parallel programming.
When parallel tasks must use common resource, such as input/output channel, they serialize their access by using locks.
Two basic locking primitives are provided:
- LOCK `r` – marks resource as locked by the calling task. If the resource is already locked by the same task, it does nothing. If it is locked by a different task, calling task is blocked (i.e. pauses execution and waits) until the resource is unlocked.
- UNLOCK `r` – unlocks given resource if it is locked by the current task, and does nothing otherwise.
After the execution of the last locking primitive of the task, all resources locked by that task are unlocked.
Locking guarantees that only a single task can access the resource at a time. However, carelessly
written programs may still lead to some unfortunate situations. If task `A` has already locked resource `P` and tries
to lock `Q`, while task `B` has already locked `Q` and tries to lock `P`, they will both wait endlessly.
This condition is called "deadlock".
Your program must, given lock/unlock sequences executed by two parallel tasks while accessing `M` resources, determine
whether a deadlock is possible between them.
Input file format
First line of input file contains integers `N_1\ N_2\ M`. Following lines contain `N_1` locking primitives called by
the first task, then `N_2` primitives called by the second task, in the order of calling.
Each primitive is located on a separate line and consists of a string LOCK or UNLOCK followed by
one or more spaces and a resource number `r` (`1\ ≤\ r\ ≤\ M`).
Output file format
Output file must contain integers `D_1\ D_2`, designating that deadlock can occur when the first task is trying to
execute primitive number `D_1` (`1\ ≤\ D_1\ ≤\ N_1`) while the second task is trying to execute primitive
number `D_2` (`1\ ≤\ D_2\ ≤\ N_2`).
If there is more than one possible deadlock, output the one with minimal `D_1`. If there is still more then one,
output the one with minimal `D_2`. If the deadlock is not possible, output file must contain a single 0 (zero).
Constraints
`1\ ≤\ N1,\ N2\ ≤\ 5000`, `1\ ≤\ M\ ≤\ 100`.
Sample Input 1
2 2 2 LOCK 1 LOCK 2 LOCK 2 LOCK 1
Sample Output 1
2 2
Sample Input 2
3 3 5 LOCK 5 LOCK 2 LOCK 3 LOCK 5 LOCK 3 LOCK 2
Sample Output 2
0
