Qraf ortadan#7256
Lisa Simpson, "Simpsonlar" cizgi filmindən tanınan bir obraz, bir gün əlaqəli, yönsüz qrafın bir zirvəsində tapılır. Lisa qrafın zirvələri arasında hərəkət edə bilər, amma yalnız hazırda olduğu zirvəni və ona birbaşa bitişik zirvələri görə bilir. Qrafı araşdırmaq üçün yanında kağız-qələm olmadığından, Lisa kömək üçün zirvələrdə qoyub-götürə biləcəyi daşlardan istifadə edir. Bir zirvədə maksimum 1000 daş saxlamaq olar, bu Lisa üçün kifayətdir. Qrafda 2-dən 500-ə qədər zirvə var.
Problem iki alt tapşırıqdan ibarətdir:
Birinci alt tapşırıqda heç bir zirvədə daş yoxdur və Lisa qrafın neçə zirvəsindən ibarət olduğunu öyrənmək istəyir.
İkinci alt tapşırıqda, başlanğıc zirvəsindən fərqli bir zirvədə bir daş qoyulur, digərlərində heç nə yoxdur. Lisa başlanğıc zirvəsindən daş yerləşən zirvəyə minimum kənar sayını (yəni ən qısa yolun uzunluğunu) tapmalıdır; hər bir kənar uzunluğu vahid sayılır.
graph prosedurunu yazın. Cari zirvə və onun qonşularında olan daş sayına görə Lisaya növbəti addımını (neçə daş qoymaq, götürmək və ya hansı bitişik zirvəyə getmək) seçməyə kömək edir; əgər cavab hazırdırsa, onu qaytarır.
graph prosedurunun reallaşdırmasını və (lazım olarsa) əlavə köməkçi kodu, lakin əsas proqramın bədəni olmadan (yəni C++ üçün main, Pascal üçün begin/end olmadan) göndərməlisiniz. Test zamanı faylınız münsiflərin hazırladığı xüsusi proqram ilə birləşdiriləcək və prosedurun düzgünlüyü orada yoxlanacaq. Prosedur aşağıdakı kimi olmalıdır:
C++:
void graph(int subproblem, int neighborsCount, int neighbors[], int ¤t, int &whereToGo, int &answer);Pascal:
procedure graph(subproblem, neighborsCount: longint; var neighbors: array of longint; var current, whereToGo, answer: longint);subproblem — alt tapşırıq nömrəsi: 1 — zirvə sayı, 2 — ən qısa yol; qraf üçün sabitdir.
neighborsCount — cari zirvəyə birbaşa qoşulanların sayı.
neighbors — neighborsCount ölçülü massiv (0-dan başlayır), qonşu zirvələrdəki daş sayı. Massivin sırası müxtəlif çağırışlarda dəyişə bilər, hətta eyni zirvə üçün belə. Daxildə massiv dəyişsə də, bu, qrafdakı vəziyyətə təsir etməz — Lisa yalnız öz yerindəki daş sayını dəyişə bilər.
current — cari zirvədəki daş sayı; prosedurda artırmaq/azaltmaq olar, lakin həddi 0–1000 pozmamaq şərtilə. Bu, həqiqi zirvədəki daş sayını da dəyişəcək.
whereToGo — başlanğıcda -1. Lisa qrafı tədqiq etməyə davam edirsə, bunu növbəti addımda getməli olduğu qonşunun daş sayı ilə dəyişin (diqqət: bu indeks deyil, dəyərdir!). Əgər massivdə eyni dəyər bir neçə dəfə varsa, Lisa onlardan birinə gedəcək, hansına getdiyini siz seçə bilmirsiniz. Əgər cavab hazırdırsa, dəyəri dəyişməyin.
answer — başlanğıcda -1. Əgər cavab hazırdırsa, bu dəyərlə əvəz edin, əks halda dəyişməyin.
Hər addımda yalnız həmin an ötürülən bilgi əsasında qərar verin. Əvvəlki çağırışların heç biri və ya proqramla qarşılıqlı təsir nəticəyə təsir etməməlidir. Prosedur deterministik olmalıdır: eyni giriş üçün eyni nəticə qaytarmalıdır.
Nümunə əsas proqram (graph_tester.cpp / graph_tester.pas) sizin faylınızla eyni qovluqda, graph.dat verilmiş strukturda olmalıdır. Proqramınızı və test faylınızı eyni qovluğa qoyun. Qiymətləndirmə proqramı fərqli ola bilər.
Birinci sətrdə 4 ədəd: zirvə sayı , kənar sayı , başlanğıc zirvə və (alt tapşırıq 2 üçün) daş olan zirvənin nömrəsi ( — birinci alt tapşırıq üçündür). Sonra sətirdə hərəsində iki ədəd — qraf kənarlarının verilməsi (zirvə nömrələri).
Bir sətr: prosedurdan alınan cavab və ya texniki tələb pozularsa səhv mesajı.
Testlər dörd blokda verilmişdir:
30 bal: 1-ci alt tapşırıq, qraf — ağac
20 bal: 1-ci alt tapşırıq, qraf — istənilən əlaqəli
10 bal: 2-ci alt tapşırıq, qraf — ağac
40 bal: 2-ci alt tapşırıq, qraf — istənilən əlaqəli
Qeyd. Əgər prosedur texniki tələbləri pozsa, cavabda icra və ya kompilyasiya xətası ola bilər. Yaddaş limiti ən azı MB-dır. Qlobal dəyişənlərdən istifadə icazəlidir.
Nümunə 1