Cədvələ nəzarət

Şəhər meri, şəhərdə çox sayda marşrutka fəaliyyət göstərdiyi üçün sakinlərin tramvaylardan istifadə etməyi dayandırdığını müşahidə etdi. Buna görə də, şəhərdə bütün marşrut taksilərini idarə edən şirkətin yenidən təşkil edilməsi qərara alındı. Şəhərdə $N$ marşrutka dayanacağı mövcuddur və bəziləri yollarla birləşdirilib. Əgər iki dayanacaq bir yol ilə birləşdirilibsə, marşrutka əlavə dayanacaqlara ehtiyac olmadan birinci dayanacaqdan ikinciyə və əksinə gedə bilər. Heç bir dayanacaq cütü iki və ya daha çox yolla birləşdirilməyib və heç bir yol bir dayanacağı özü ilə birləşdirmir. Marşrutka yolundakı bütün dayanacaqlarda dayanır. Marşrutların sayını azaltmaq əmri verildikdən sonra şirkət yalnız üç və ya daha çox fərqli dayanacaqdan ibarət olan və marşrutka bir dayanacaqdan bir dəfə keçməyən dövrə marşrutlarını saxlamağa qərar verdi. Bundan əlavə, hər hansı bir cüt marşrut ən azı bir yolla fərqlənməlidir. Şirkət, gəlirli biznesdə mövqelərini itirmək istəmədiyi üçün, bu iki tələbi ödəyən maksimum sayda marşrut yaratmağa qərar verdi. Marşrutlar $1$-dən $K$-yə qədər nömrələnib ($K$ — marşrutların sayı). Hər marşrut üzrə dəqiq bir mikroavtobus hərəkət edir.

Şirkətin qarşısında duran ikinci məsələ nəzarətçilərin iş qrafikini tərtib etməkdir. Qrafik, sütunları marşrutlar, sətirləri isə nəzarətin həyata keçirildiyi vaxtlar olan bir cədvəldir. Əgər [T, I] hüceyrəsində $X$ rəqəmi varsa, bu o deməkdir ki, $I$ nömrəli marşrut üzrə hərəkət edən mikroavtobus $T$ vaxtında $X$ nömrəli dayanacaqda nəzarət üçün dayanır. Hüceyrə boş da ola bilər. Məlumdur ki, gün ərzində hər bir marşrutka hər dayanacaqda nəzarət üçün dəqiq bir dəfə dayanmalıdır, yəni hər sütunda marşrutda olan dayanacaqlar qədər boş olmayan hüceyrə var. Bundan əlavə, eyni vaxtda bir dayanacaqda iki marşrutka yoxlanılmamalıdır və təbii ki, bir marşrutka eyni vaxtda iki fərqli dayanacaqda ola bilməz. Belə bir cədvəldə minimal mümkün sətir sayını tapmaq lazımdır.