Mikroprosessor tapşırığı

Məşhur bir mikroprosessor şirkəti sizdən onların kompüter çiplərində bəzi dəyişdirilə bilən komponentləri (vidjetləri) yerləşdirməyə kömək etməyinizi xahiş edib. Hər çipin dizaynı N \times N ölçülü kvadrat yerlərdən ibarətdir. Hər yerə yalnız bir komponent yerləşdirilə bilər və siz mümkün qədər çox vidjet yerləşdirməyə çalışmalısınız.

Müasir prosessor dizaynları əlbəttə ki, mürəkkəbdir. Təəssüf ki, sizin bir neçə məhdudiyyətiniz var:

• Bəzi yerlər deaktiv olunub.

• Bəzi yerlər artıq digər komponentlər tərəfindən tutulub və vidjetlər üçün istifadə oluna bilməz.

• Sxemin üfüqi və şaquli kənarlarına birləşdirilmiş paralel yaddaş yolları mövcuddur və onların ötürmə qabiliyyəti yükü balanslaşdırılmalıdır. Buna görə də, birinci sətirdə nə qədər komponent varsa, birinci sütunda da eyni sayda komponent olmalıdır; ikinci sətirdə nə qədər varsa, ikinci sütunda da eyni qədər olmalıdır və s. Komponent sayına həm çipdə artıq yerləşdirilmiş komponentlər, həm də əlavə olunacaq vidjetlər daxildir.

• Həmçinin, güc təchizatı hər bir sətirin və sütunun sonuna birləşdirilib. Lokal qızmalardan qaçmaq üçün, istənilən sətir və ya sütunda çipdəki ümumi komponentlərin ən çoxu $A/B$ hissəsi yerləşdirilə bilər.

Çipin spesifikasiyası $N$ sətir və $N$ simvoldan ibarət olur, burada '.' açıq yeri, '/' deaktiv olunmuş yeri, 'C' isə artıq komponentlə tutulmuş yeri göstərir. Məsələn:

CC/.. ./.// ..C.C /.C.. /./C/

Əgər bir sətir və ya sütunda ən çox $3/10$ komponent ola bilərsə, bu 5 \times 5 ölçülü çipdə əlavə edə biləcəyiniz maksimum vidjet sayı $7$-dir. Aşağıdakı kimi bir yerləşmə mümkündür; burada 'W' vidjetin açıq yerə əlavə olunduğunu göstərir.

CC/W. W/W// W.C.C /.CWW /W/C/