Siqnallar üçün körpülər#3250
'Ah, yox, onlar bunu yenidən etdilər', deyə Vafərləndiyanın çip istehsalı zavodunun baş dizayneri qışqırdı. Yenə də marşrutlaşdırma mühəndisləri siqnalları çipdəki iki funksional blokun portları arasında elə qarışdırdılar ki, onlar hər yerdə kəsişir. Məhsulun buraxılışının son mərhələsi gedir və marşrutlaşdırmanı açmaq artıq çox bahadır. Bunun əvəzinə mühəndislər siqnallar üçün körpülər yaratmalı oldular, üçüncü ölçüyə çıxaraq, heç bir iki siqnalın kəsişməməsi üçün. Körpü yaratmaq çətin bir əməliyyatdır, buna görə də mümkün qədər az siqnalın körpü şəklində keçirilməsi arzuolunandır. Siqnalların öz-özünə kəsişmədən silikon lövhədə birləşdirilə biləcək maksimum sayını tapmaq üçün kompüter proqramı tələb olunur. Unutmayın ki, funksional blok minlərlə siqnal portuna sahib ola bilər, buna görə də bu məsələnin həlli üçün proqram yazmaq lazımdır. Belə bir tapşırığa hazırsınızmı?
Şəkil 1. Solda: iki blokun portları siqnalların təsvirini həyata keçirir (4,2,6,3,1,5). Sağda: üçdən çox siqnal silikon səthdə bir-birinə kəsişmədən hərəkət edə bilməz. Nöqtəli xətlərlə işarələnmiş siqnallar körpü yaratmalıdır.
Tipik vəziyyət 1-ci şəkildə təsvir edilmişdir. İki funksional blokun portları yuxarıdan aşağıya doğru 1-dən p-ə qədər nömrələnmişdir. Siqnalların təsviri 1-dən p-ə qədər olan rəqəmlərin permutasiyası ilə verilir, burada i-ci rəqəm sol tərəfdəki i-ci portun sağ tərəfdə qoşulduğu portun nömrəsini göstərir. İki siqnal kəsişir, əgər onların müvafiq portlarını birləşdirən seqmentlər kəsişirsə.
Birinci sətir testlərin sayını n ehtiva edir. Hər bir test, iki funksional blokda portların sayını p (p < 40000) ehtiva edən bir sətirlə başlayır. Sonra siqnalların təsvirini əks etdirən p sətir gəlir: i-ci sətir sol tərəfdəki blokun i-ci portu ilə qoşulan sağ tərəfdəki portun nömrəsini ehtiva edir.
Hər bir test üçün silikon səthdə kəsişmədən ötürülə biləcək maksimum siqnal sayını ayrıca bir sətirdə çıxarın.
Nümunə 1