Eksklüziv Giriş 2
Ötən ilki yarışmada qarşılıqlı istisna protokollarını öyrəndikdən sonra indi daha çətin bir problemlə üzləşirsiniz. Böyük bir müəssisə sisteminiz var və burada bir neçə eyni zamanda işləyən proseslər mövcuddur. Sistem bir neçə resursa malikdir – verilənlər bazaları, ismarış növbələri və s. Hər bir eyni zamanda işləyən proses eyni anda iki resursla işləyir. Məsələn, bir proses müəyyən bir verilənlər bazasından bir işi ismarış növbəsinə köçürə bilər, digər proses isə ismarış növbəsindən bir işi götürüb, işi yerinə yetirib nəticəni başqa bir ismarış növbəsinə yerləşdirə bilər və s.
Bütün resurslar qarşılıqlı istisna protokolları ilə eyni vaxtda girişdən qorunur, bunlar kilidlər kimi tanınır. Məsələn, müəyyən bir verilənlər bazasına giriş etmək üçün proses həmin verilənlər bazası üçün kilidi əldə edir, sonra işini yerinə yetirir və kilidi buraxır. İki proses eyni kilidi eyni anda tuta bilməz (bu qarşılıqlı istisna xüsusiyyətidir). Beləliklə, bir kilidi əldə etməyə çalışan proses, həmin kilid başqa bir proses tərəfindən alındıqda gözləyir.
Resurslarla işləyən prosesin əsas dövrü P və Q belə görünür:
"' loop forever
DoSomeNonCriticalWork()
P.lock()
Q.lock()
WorkWithResourcesPandQ()
Q.unlock()
P.unlock()
end loop "'
P və Q resursları üçün kilidlərin alınma sırası vacibdir. Proses c P.lock() ilə kilid P əldə etmiş və Q.lock() ilə kilid Q üçün gözləyirsə, bu o deməkdir ki, kilid Q başqa bir proses d tərəfindən alınmışdır. Əgər proses d işləyirsə (gözləmir), onda biz deyirik ki, uzunluğu 1 olan bir gözləmə zənciri var. Əgər d kilid Q əldə etmiş və işləyən proses e tərəfindən əldə edilmiş başqa bir kilid R üçün gözləyirsə, onda biz deyirik ki, uzunluğu 2 olan bir gözləmə zənciri var və s. Əgər bu gözləmə zəncirində hər hansı bir proses artıq proses c tərəfindən alınmış kilid P üçün gözləyirsə, onda biz deyirik ki, gözləmə zənciri sonsuz uzunluqdadır və sistem ölü vəziyyətə düşür.
Bu problem üçün biz yalnız proseslərin ilk kilidlərini tutub ikinci kilidlər üçün gözlədikləri dəyişən gözləmə zəncirləri ilə maraqlanırıq. Rəsmi olaraq:
Uzunluğu n (n >= 0) olan dəyişən gözləmə zənciri resursların R_i (0 <= i <= n+1) və fərqli proseslərin c_i (0 <= i <= n) dəyişən ardıcıllığıdır: R_0 c_0 R_1 c_1 … R_n c_n R_n_{+1}, burada proses c_i resurslar R_i və R_i_{+1 kilidlərini bu sırayla əldə edir. Dəyişən gözləmə zənciri sükut vəziyyətinə düşür, əgər }R_0 = R_n_{+1}.
Sizə hər bir prosesin işlədiyi resurslar dəsti verilir. Sizin vəzifəniz hər bir prosesin resurs kilidlərini hansı sırayla əldə etməli olduğunu müəyyən etməkdir ki, sistem heç vaxt sükut vəziyyətinə düşməsin və mümkün olan ən uzun dəyişən gözləmə zəncirinin uzunluğu minimallaşdırılsın.
Giriş verilənləri
Giriş faylının ilk sətri tək bir tam ədəd n (1 <= n <= 100) – proseslərin sayını ehtiva edir. Sonrakı n sətir hər bir prosesin ehtiyac duyduğu resursları təsvir edir. Hər bir resurs L-dən Z-yə qədər böyük ingilis hərfi ilə təyin edilir, beləliklə ən çox 15 resurs var. Prosesləri təsvir edən hər sətir iki fərqli resursu boşluqla ayırır.
Çıxış verilənləri
Çıxış faylının ilk sətrində tək bir tam ədəd m – mümkün olan ən uzun dəyişən gözləmə zəncirinin minimal uzunluğunu yazın.
Sonra n sətir yazın – hər proses üçün bir sətir. Hər sətirdə bu minimal uzunluq üçün maksimal dəyişən gözləmə zəncirini təmin etmək üçün müvafiq proses tərəfindən alınmalı olan resursları sırayla yazın. Sətirdəki resursları boşluqla ayırın. Çıxışda proseslərin sırası girişdəki sıralarına uyğun olmalıdır.